栈和队列

栈和队列都是动态集合，且在其上进行DELETE操作所移除的元素都是预先设定的。 在栈stack中，被删除的是最近插入的元素：栈实现的是一种后进先出(last-in, first-out， LIFO)策略。 在队列(queue)中，被删去的总是在集合中存在时间最长的那个元素：队列实现的是一种先进先出(first-in, first-out, FIFO)策略。

简单的数组实现栈和队列. 栈 栈中包含的元素为S[1..S.top],其中S[1]是栈底元素，而S[S.top]是栈顶元素。 STATCK-EMPTY(S)

if S.top == 0 return TRUE else return FALSE

PUSH(S, x)

S.top = S.top + 1 S[S.top] = x

POP(S)

if STACK-EMPTY(S) error "underflow" else S.top = S.top - 1 return S[S.top + 1]

队列 该队列有一个属性Q.head指向队列头元素。而属性Q.tail则指向下一个新元素将要插入的位置。当Q.head=Q.tail+1时，队列是满的，此时若试图插入一个元素，则队列发生上溢。 ENQUEUE(Q, x)

if Q.head == Q.tail + 1 // 上溢检查 error "overflow" Q[Q.tail] = x if Q.tail == Q.length Q.tail = 1 else Q.tail = Q.tail + 1

DEQUEUE(Q, x)

if Q.head == Q.tail //下溢检查 error "underflow" x = Q[Q.head] if Q.head = Q.length Q.head = 1 else Q.head = Q.head + 1 return x