题目描述


请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：
输入：[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路

用两个栈来模拟队列：
入栈时，往第一个栈入；
出栈时，

  1. 如果第二个栈不为空，则直接从第二个栈出栈；
  2. 如果为空，则将第一个栈的所有元素出栈后入栈到第二个栈中，这样就实现了倒置，然后从第二个栈出栈；

例如，入队1，2，3，然后出队，再入队4，出队，整个流程如下：

  1. 将1,2,3入栈第一个栈，此时第一个栈为1,2,3
  2. 出队，按队的性质应该出1。此时第二个栈为空，于是把1,2,3出栈后入栈到第二个栈，此时第一个栈为空，第二个栈为3,2,1 （1在顶部），此时出栈即出的是1
  3. 入队4，将4入栈第一个栈，第一个栈变成了4，
  4. 出队，第二个栈不为空，出栈第二个栈的顶部元素；

代码

  1. class MyQueue {
  2.     Deque<Integer> stack1;
  3.     Deque<Integer> stack2;
  4.     /** Initialize your data structure here. */
  5.     public MyQueue() {
  6.         stack1 = new ArrayDeque<>();
  7.         stack2 = new ArrayDeque<>();
  8.     }
  10.     /** Push element x to the back of queue. */
  11.     // 入队直接入到stack1即可
  12.     public void push(int x) {
  13.         stack1.offerLast(x);
  14.     }
  16.     /** Removes the element from in front of queue and returns that element. */
  17.     // 出队时先看stack2是否为空，如果不为空，则直接从stack2出栈，因为stack2中的元素的倒置过的
  18.     // 所以出栈等价于出队
  19.     // 如果stack2为空，则将stack1中的出栈后依次入栈到stack2中，实现倒置，然后从stack2出栈
  20.     public int pop() {
  21.         if (!stack2.isEmpty()) {
  22.             return stack2.pollLast();
  23.         } else {
  24.             while (!stack1.isEmpty()) {
  25.                 int temp = stack1.pollLast();
  26.                 stack2.offerLast(temp);
  27.             }
  29.             return stack2.pollLast();
  30.         }
  31.     }
  33.     /** Get the front element. */
  34.     // peek和pop逻辑相同，只是一个是peekLast, 一个是pollLast
  35.     public int peek() {
  36.         if (!stack2.isEmpty()) {
  37.             return stack2.peekLast();
  38.         } else {
  39.             while (!stack1.isEmpty()) {
  40.                 int temp = stack1.pollLast();
  41.                 stack2.offerLast(temp);
  42.             }
  44.             return stack2.peekLast();
  45.         }
  46.     }
  48.     /** Returns whether the queue is empty. */
  49.     // 两个栈都为空，才是空
  50.     public boolean empty() {
  51.         return stack1.isEmpty() && stack2.isEmpty();
  52.     }
  53. }
  55. /**
  56.  * Your MyQueue object will be instantiated and called as such:
  57.  * MyQueue obj = new MyQueue();
  58.  * obj.push(x);
  59.  * int param_2 = obj.pop();
  60.  * int param_3 = obj.peek();
  61.  * boolean param_4 = obj.empty();
  62.  */