基本数据结构——栈和队列含python实现

栈和队列：都是动态集合 动态集合自己不保存数据，每次使用都要重新查找一遍

栈：后进先出LIFO 队列：先进先出FIFO

运用指针可以构造多种复杂的数据结构

栈

用一个数组S[1,…,n]实现一个最多可容纳n个元素的栈。该数组有一个属性S.top，这个属性指向最新插入的元素。栈中包含的元素为S[1,…,S.top]，其中S[1]是栈底元素，S.top是栈顶元素。

S.top=0:栈中不包含任何元素，表示栈是空的。要测试一个栈是否为空可以用查询操作STACK-EMPTY。如果试图对一个空栈执行弹出（POP）操作，称栈下溢（underflow）。

S.top>n:称为上溢。

栈的操作： PUSH入栈 POP出栈

栈的几种操作（PUSH和POP）用伪代码实现如下：

STACK-EMPTY (S) 1. if S.top == 0 2. return TRUE 3. else return FALSE PUSH(S,x) 1.S.top = S.top + 1 2.S[S.top] = x POP(S) 1.if STACK-EMPTY (S) 2. error"underflow" 3.else S.top = S.top -1 3. return S[S.top + 1]

以上操作的执行时间均为O(1)

用python实现：

class ArrayStack: def __init__(self): '''Create an empty stack.''' self._data = [] def __len__(self): return len(self._data) def is_empty(self): return len(self._data) == 0 def push(self,e): self._data.append(e) def pop(self): if self.is_empty(): raise Empty('Stack is empty') return self._data.pop() def top(self): if self.is_empty(): raise Empty('Stack is empty') return self._data[-1] class Empty(Exception): pass

测试：

if __name__ == '__main__': stack = ArrayStack() stack.push(3) stack.push(5) stack.push(9) print(len(stack)) print(stack.pop()) print(stack.is_empty())

结果：

3 9 False

---

队列

就像排队买饭，先排队的人买到东西先走

利用数组Q[1…n]来实现一个最多容纳n-1个元素的队列的一种方式。Q.head指向队头元素。而属性Q.tail指向下一个新元素要插入的位置。 当Q.head = Q.tail时，队列为空。初始时有Q.head = Q.tail = 1。如果试图从空队列中删除一个元素，则队列发生下溢。 当Q.head = Q.tail +1，队列是满的，若此时试图加一个元素，则队列是上溢的。

下面的伪代码，假设n = Q.length。

ENQUEUE(Q,x) 1.Q[Q.tail] = x 2.if Q.tail == Q.length 3. Q.tail = 1 4.else Q.tail = Q.tail + 1 DEQUEUE(Q) 1.x = Q[Q.head] 2.if Q.head == Q.length 4. Q.head = 1 5.else Q.head = Q.head + 1 6.return x

两种操作的执行时间都为O(1)