由两个栈组成的队列

题目

编写一个类, 用两个栈实现队列, 支持队列的基本操作(add, poll, peek).

思路

栈是FILO, 队列是FIFO.
一个栈stackPush按用户操作顺序存储, 提供入队操作.
另一个栈stackPop按照相反顺序存储, 提供出队操作.

代码实现

public class TwoStacksQueue {
  private Stack<Integer> stackPush;
  private Stack<Integer> stackPop;

  public TwoStacksQueue() {
    stackPush = new Stack<Integer>();
    stackPop = new Stack<Integer>();
  }

  /**
   * 将stackPush的元素取出并放入stackPop
   * <b>重点在于stackPop不为空， stackPush绝对不能向stackPop压入数据</b>
   * */
  private void pushToPop() {
    if (stackPop.isEmpty()) {
      while (!stackPush.isEmpty()) {
        stackPop.push(stackPush.pop());
      }
    }
  }

  /**
   * 入队
   * */
  public void add(int item) {
    stackPush.push(item);
    pushToPop();
  }

  /**
   * 出队
   * */
  public int poll() {
    if (stackPush.isEmpty() && stackPop.isEmpty()) {
      throw new RuntimeException("Your queue is empty.");
    }
    pushToPop();
    return stackPop.pop();
  }

  /**
   * 获取队首元素
   * */
  public int peek() {
    if (stackPush.isEmpty() && stackPop.isEmpty()) {
      throw new RuntimeException("Your queue is empty.");
    }
    pushToPop();
    return stackPop.peek();
  }
}