栈和队列

栈和队列都是动态集合，且在其上进行DELETE操作所移除的元素是预先设定的。在栈(stack)中,被删除的是最近插入的元素：栈实现的是一种后进先出(last-in, first-out, LIFO)策略。类似地，在队列(queue)中，被删去的总是在集合中存在时间最长的那个元素：队列实现的是一种先进先出(first-int, first-out,FIFO)策略。在计算机上实现栈和队列有几种有效方式。本节将介绍如何利用一个简单的数组实现这两种结构。

栈

栈上的INSERT操作被称为压入(PUSH),而无无素的DELETE操作称为弹出(POP)。这两个名称使人联想到现实中的栈，比如餐馆里装有弹簧的摞盘子的栈。盘子从栈中弹出的次序刚好同它们压入的次序相反，这是因为只有最上面的盘子才能被取下来。 如图10-1所示，可以用一个数组S[1..n]来实现一个最多可容纳n个元素的栈。该数组有一个属性S.top，指向最新插入的元素。栈中包含的元素为S[1..S.top]，其中S[1]是栈底元素，而S[S.top]是栈顶元素。 当S.top = 0时，栈中不包含任何元素，即栈是空的。要测试一个栈是否为空可以用查询操作STACK-EMPTY。如如试图对一个空栈执行弹出操作，则称栈下溢(underflow)，这通常是一个错误。如果S.top超过了n，则称栈上溢(overflow)。 栈的几种操作只需分别用几行代码来实现：

STACK-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]

图10-1所示为修改后的PUSH和POP操作的执行结果。三种栈操作的执行时间都为O(1)

队列

队列上的INSERT操作称为入队(ENQUENUE),DELETE操作称为出队(DEQUEUE);正如栈的POP操作一样，DEQUEUE操作也没有元素参数。队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有队头(head)和队尾(tail)，当有一个元素入队时，它被放在队尾的位置，就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在队头的那个，就像排在队伍前面等待最久的那个顾客一样。

图10-2表明利用数组Q[1..n]来实现一个最多容纳n-1个元素的队列的一种方式。该队列有一个属性Q.head指向队头元素。而属性Q.tail则指向下一个新元素将要插入的位置。队列中的元素存放在位置Q.head,Q.head + 1, … , Q.tail - 1,并在最后的位置“环绕”，感觉好像位置1坚信在位置n后形成一个环序。当Q.head = Q.tail时，队列为空。初始时有Q.head = Q.tail = 1。如果试图从空队列中删除一个元素，则队列发生下溢。当Q.head = Q.tail + 1时，队列是满的，此时若试图插入一个元素，则队列发生上溢。 在下面ENQUEUE和DEQUEUE程序中，我们省略了对下溢和上溢的检查。

ENQUEUE(Q, x) Q[Q.tail] = x if Q.tail = Q.length Q.tail = 1 else Q.tail = Q.tail + 1 DEQUEUE(Q) X = Q[Q.head] if Q.head = Q.length Q.head = 1 else Q.head = Q.head + 1 return x

图10-2所示为ENQUEUE和DEQUEUE操作的执行结果。两种操作的执行时间都为O(1)。

练习

10.1-1仿照图10-1，画图表示依次执行操作PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8)和POP(S)每一步的结果，栈S初始为空，存储于数组S[1..6]中

10.1-2说明如何在一个数组A[1..n]中实现两个栈，使得当两个栈的元素个数之各不为n时，两者都不会发生上溢。需求PUSH和POP操作的运行时间为O(1)。 判断是否溢出的条件也可以是 s1.top + 1 == s1.top

public class DoubleStack { private int[] arr; private int len; private int s1Top = -1; private int s2Top; public DoubleStack(int len){ if(len < 1){ throw new IllegalArgumentException("len" + len); } arr = new int[len]; this.len = len; s2Top = len; } public void s1Push(int i){ if(s1Top + 1 == s2Top){ throw new IllegalStateException("s1 stack overflow" + s1Top); } arr[++s1Top] = i; } public void s2Push(int i){ if(s1Top + 1 == s2Top){ throw new IllegalStateException("s2 stack overflow" + s2Top); } arr[--s2Top] = i; } public int s1Pop(){ if(s1Top == -1){ throw new IllegalStateException("s1 stack underflow" + s1Top); } return arr[s1Top--]; } public int s2Pop(){ if(s2Top == len){ throw new IllegalStateException("s2 stack underflow" + s2Top); } return arr[s2Top++]; } public boolean isS1Empty(){ return s1Top == -1; } public boolean isS2Empty(){ return s2Top == len; } public static void main(String[] args) { DoubleStack ds = new DoubleStack(4); ds.s1Push(4); ds.s1Push(3); ds.s2Push(1); ds.s2Push(2); // ds.s1Push(100); //overflow // ds.s2Push(200); //overflow ds.s1Pop(); ds.s2Pop(); ds.s2Pop(); ds.s1Pop(); System.out.println(ds.isS1Empty()); System.out.println(ds.isS2Empty()); } }

10.1-3仿照图10-2,画图表示依次执行操作ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q.3), DEQUEUE(Q), ENQUEUE(Q, 8)和DEQUEUE(Q)每一步的结果，队列初始为空，存储于数组Q[1..6]中 10.1-4重写ENQUEUE和DEQUEUE的代码，使之能处理队列的下溢和上溢

分析：只有在出队时才可能发生下溢 只有在入队时才可能发生上溢 public class QQueue { private int[] arr; int len; int size = 0; int head = 0; int tail = 0; public QQueue(int len){ if(len < 1){ throw new IllegalArgumentException("len" + len); } arr = new int[len]; this.len = len; } public void enQueue(int i){ if(size == len){ throw new IllegalStateException("size" + size); } arr[tail] = i; if((tail + 1) == len){ tail = 1; }else { tail++; } size++; } public void deQueue(){ if(size == 0){ throw new IllegalStateException("size" + size); } int i = arr[head]; if((head + 1) == len){ head = 1; }else { head++; } size--; } public static void main(String[] args) { QQueue q = new QQueue(3); q.enQueue(1); q.enQueue(1); q.enQueue(1); //q.enQueue(2); overflow q.deQueue(); q.deQueue(); q.deQueue(); //q.deQueue(); underflow } }

10.1-6说明如何用两个栈实现一个队列，并分析相关队列操作的运行时间。

public class TwoStackForQueue<E> { private Stack<E> s1 = new Stack<E>(); private Stack<E> s2 = new Stack<E>(); public void enQueue(E e){ s1.push(e); } public E deQueue(){ if(s1.isEmpty() && s2.isEmpty()){ throw new IllegalStateException("underflow"); } if(s2.isEmpty()){ while (!s1.isEmpty()){ E item = s1.pop(); s2.push(item); } } return s2.pop(); } public static void main(String[] args) { TwoStackForQueue<Integer> q = new TwoStackForQueue<>(); q.enQueue(1); q.enQueue(2); q.enQueue(3); System.out.println(q.deQueue()); System.out.println(q.deQueue()); System.out.println(q.deQueue()); //System.out.println(q.deQueue()); underflow } }

10.1-7 说明如何用两个队列实现一个栈，并分析相关栈操作的运行时间。

public class TwoQueueForStack<E> { private Queue<E> q1 = new LinkedList<E>(); private Queue<E> q2 = new LinkedList<E>(); public E pop(){ return q1.remove(); } public void push(E e){ while (!q1.isEmpty()){ q2.add(q1.remove()); } q1.add(e); while (!q2.isEmpty()){ q1.add(q2.remove()); } } public static void main(String[] args) { TwoQueueForStack<Integer> s = new TwoQueueForStack<>(); s.push(1); s.push(2); Integer pop = s.pop(); System.out.println(pop); System.out.println(s.pop()); } }

参考

算法导论 10.1栈和队列