用stackMin栈保存着stackData每一步的最小值

方案二的代码实现如MyStack2类所示：

public class MyStack2 { private StackstackData; private StackstackMin; public MyStack2() { this.stackData = new Stack(); this.stackMin = new Stack(); } public void push(int newNum) { if (this.stackMin.isEmpty()) { this.stackMin.push(newNum); } else if (newNum < this.getmin()) { this.stackMin.push(newNum); } else {

int newMin = this.stackMin.peek(); this.stackMin.push(newMin); } this.stackData.push(newNum); } public int pop() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty."); } this.stackMin.pop(); return this.stackData.pop(); } public int getmin() { if (this.stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty."); } return this.stackMin.peek(); } }

【点评】

方案一和方案二其实都是用stackMin栈保存着stackData每一步的最小值。共同点是所有操作的时间复杂度都为O (1)、空间复杂度都为O (n )。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。

由两个栈组成的队列

【题目】

编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。

【难度】

尉　★★☆☆

【解答】

栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。

具体实现上是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。

因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1～5依次压入stackPush，那么从stackPush的栈顶到栈底为5～1，此时依次再将5～1倒入stackPop，那么从stackPop的栈顶到栈底就变成了1～5。再从stackPop弹出时，顺序就像队列一样，如图1-3所示。

图1-3

听起来虽然简单，实际上必须做到以下两点。

1．如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。

2．如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。

违反了以上两点都会发生错误。

违反1的情况举例：1～5依次压入stackPush，stackPush的栈顶到栈底为5～1，从stackPush压入stackPop时，只将5和4压入了stackPop，stackPush还剩下1、2、3没有压入。此时如果用户想进行弹出操作，那么4将最先弹出，与预想的队列顺序就不一致。

违反2的情况举例：1～5依次压入stackPush，stackPush将所有的数据压入了stackPop，此时从stackPop的栈顶到栈底就变成了1～5。此时又有6～10依次压入stackPush，stackPop不为空，stackPush不能向其中压入数据。如果违反2压入了stackPop，从stackPop的栈顶到栈底就变成了6～10、1～5。那么此时如果用户想进行弹出操作，6将最先弹出，与预想的队列顺序就不一致。

上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢？

这个选择的时机可以有很多，调用add、poll和peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点，就不会出错。

本书的实现是在调用poll和peek方法时进行压入数据的过程。

具体实现请参看如下的TwoStacksQueue类：

public class TwoStacksQueue { public StackstackPush; public StackstackPop; public TwoStacksQueue() { stackPush = new Stack(); stackPop = new Stack(); } public void add(int pushInt) { stackPush.push(pushInt); } public int poll() { if (stackPop.empty() && stackPush.empty()) { throw new RuntimeException("Queue is empty! "); } else if (stackPop.empty()) { while (! stackPush.empty()) { stackPop.push(stackPush.pop()); } } return stackPop.pop(); } public int peek() { if (stackPop.empty() && stackPush.empty()) { throw new RuntimeException("Queue is empty! "); } else if (stackPop.empty()) { while (! stackPush.empty()) { stackPop.push(stackPush.pop()); } } return stackPop.peek(); } }