Implement the following operations of a queue using stacks.

    • push(x) — Push element x to the back of queue.
    • pop() — Removes the element from in front of queue.
    • peek() — Get the front element.
    • empty() — Return whether the queue is empty.

    Example:

    1. MyQueue queue = new MyQueue();
    3. queue.push(1);
    4. queue.push(2);  
    5. queue.peek();  // returns 1
    6. queue.pop();   // returns 1
    7. queue.empty(); // returns false

    Notes:

    • You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
    • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
    • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

    题意

    用栈来实现队列的功能。

    思路

    需要用到两个栈，有两种方法：

    方法1：只在stack1进行push；只在stack2进行pop和peek，当stack2空时，则将stack1中所有元素依次出栈并压入stack2中，再进行pop和peek。

    方法2：每次push新元素x时，将stack1中所有元素依次出栈并压入stack2中，将x压入stack1，再将stack2中所有元素依次出栈并压回stack1中，这样就能保证任何时候stack1要进行pop时都是先进先出。

    代码实现 - 方法1

    1. class MyQueue {
    2.     Deque<Integer> stack1;
    3.     Deque<Integer> stack2;
    5.     /** Initialize your data structure here. */
    6.     public MyQueue() {
    7.         stack1 = new ArrayDeque<>();
    8.         stack2 = new ArrayDeque<>();
    9.     }
    11.     /** Push element x to the back of queue. */
    12.     public void push(int x) {
    13.         stack1.push(x);
    14.     }
    16.     /** Removes the element from in front of queue and returns that element. */
    17.     public int pop() {
    18.         if (stack2.isEmpty()) {
    19.             while (!stack1.isEmpty()) {
    20.                 stack2.push(stack1.pop());
    21.             }
    22.         }
    24.         return stack2.pop();
    25.     }
    27.     /** Get the front element. */
    28.     public int peek() {
    29.         if (stack2.isEmpty()) {
    30.             while (!stack1.isEmpty()) {
    31.                 stack2.push(stack1.pop());
    32.             }
    33.         }
    35.         return stack2.peek();
    36.     }
    38.     /** Returns whether the queue is empty. */
    39.     public boolean empty() {
    40.         return stack1.isEmpty() && stack2.isEmpty();
    41.     }
    42. }

    代码实现 - 方法2

    1. class MyQueue {
    2.     Deque<Integer> stack1;
    3.     Deque<Integer> stack2;
    5.     /** Initialize your data structure here. */
    6.     public MyQueue() {
    7.         stack1 = new ArrayDeque<>();
    8.         stack2 = new ArrayDeque<>();
    9.     }
    11.     /** Push element x to the back of queue. */
    12.     public void push(int x) {
    13.         while (!stack1.isEmpty()) {
    14.             stack2.push(stack1.pop());
    15.         }
    17.         stack1.push(x);
    19.         while (!stack2.isEmpty()) {
    20.             stack1.push(stack2.pop());
    21.         }
    22.     }
    24.     /** Removes the element from in front of queue and returns that element. */
    25.     public int pop() {
    26.         return stack1.pop();
    27.     }
    29.     /** Get the front element. */
    30.     public int peek() {
    31.         return stack1.peek();
    32.     }
    34.     /** Returns whether the queue is empty. */
    35.     public boolean empty() {
    36.         return stack1.isEmpty();
    37.     }
    38. }