由两个栈组成的队列
【题目】
编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
【解答】
栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
具体实现时是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只能从这个栈弹出，记为stackPop。
因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1~5依次压入stackPush，那么从stackPush的栈顶到栈底5~1,此时一次再将5~1倒入stackPop，那么从stackPop的栈底就变成了1~5.再从stackPop弹出时，顺序就像队列一样，如图1-3所示。
听起来虽然简单，实际上必须做到以下两点。
- 如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。
- 如果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 将最先弹出，与预想的队列顺序就不一致。
import java.util.Stack; /** * 两个注意点： * 1.stackPush栈中的元素要一次性的全部添加到stackPop栈中 * 2.stackPop中不为空,不可以将stackPush栈中的元素添加到里面 */ public class TwoStackQueue { public Stack<Integer> stackPush; public Stack<Integer> stackPop; public TwoStackQueue() { this.stackPush = new Stack<Integer>(); this.stackPop = new Stack<Integer>(); } //push栈向pop栈中添加数据 public void pushToPop() { if (stackPop.empty()) { while (!stackPush.empty()) { stackPop.push(stackPush.pop()); } } } public void add(int pushInt) { stackPush.push(pushInt); pushToPop(); } public int poll() { if (stackPop.empty() && stackPush.empty()) { throw new RuntimeException("Queue is empty!"); } pushToPop(); return stackPop.pop(); } //取出栈顶的元素 public int peek() { if (stackPop.isEmpty() && stackPush.isEmpty()) { throw new RuntimeException("Queue is empty!"); } pushToPop(); return stackPop.peek(); } public static void main(String[] args) { System.out.println("-------------------------------"); TwoStackQueue twoStackQueue = new TwoStackQueue(); twoStackQueue.stackPush.push(new Integer(1)); twoStackQueue.stackPush.push(new Integer(2)); twoStackQueue.stackPush.push(new Integer(3)); twoStackQueue.stackPush.push(new Integer(4)); twoStackQueue.stackPush.push(new Integer(5)); twoStackQueue.pushToPop(); System.out.println(twoStackQueue.stackPop.peek()); // 1 twoStackQueue.add(6); System.out.println(twoStackQueue.stackPop.peek()); // 1 System.out.println(twoStackQueue.stackPop.pop()); // 1 int a = (int)twoStackQueue.stackPop.pop(); } }
class MyQueue { // 利用两个栈实现队列的基本功能 Stack<Integer> inStack; // 入栈 Stack<Integer> outStack; //出栈 // 初始化两个栈 public MyQueue() { inStack = new Stack<Integer>(); outStack = new Stack<Integer>(); } // 将元素x推到队列的末尾 public void push(int x) { inStack.push(x); } // 从队列的开头移除并返回元素 public int pop() { //判断outStack是否为空 if (outStack.isEmpty()) { // inStack栈中元素不为空，则将inStack中的元素取出压入outStack栈中 while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } int pop_element = outStack.pop(); return pop_element; } // 返回队列开头的元素 public int peek() { //判断outStack是否为空 if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } // 需要考虑一个元素的情况，比如我只做一次push，然后判空，此时，outStack栈是没有元素的，而inStack栈是有元素的，可是empty返回的是true,实际并不是true，而是false public boolean empty() { return outStack.isEmpty() && inStack.isEmpty(); } } JAVA 折叠 复制 全屏
分析：后续代码基本已经编写完成，主要在pop()操作没有考虑到对outStack栈进行是否为空的判断以及在判空的时候没有考虑到对inStack栈进行判空的操作。这两个小方面没有考虑到导致本题最终没有通过全部测试用例。
