232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
 

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
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
 

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.
 

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

题目翻译：

使用两个栈实现先进先出（FIFO）队列。所实现的队列应该支持正常队列的所有功能（push，peek，pop和empty）。

实现MyQueue类：

void push（int x） 将元素x推到队列的后面。
int pop（）从队列的前面删除元素并返回它。
int peek（）返回队列的前面的元素。
boolean empty（）如果队列为空，则返回true，否则返回false。
注意：

您必须仅使用栈的标准操作，这意味着仅允许向顶部推，从顶部查看/弹出，大小和为空的操作。
根据您的语言，堆栈可能不是本机支持的。您可以使用列表或双端队列（double-ended queue）模拟堆栈，只要您仅使用栈的标准操作。

import java.util.Stack;

class MyQueue {
    // 定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    /** Initialize your data structure here. */
    // 初始化方法
    public MyQueue() {
        // 实例化栈1
        stack1 = new Stack<>();
        // 实例化栈2
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    // 将元素x推到队列的后面
    public void push(int x) {
        // 将元素x压入栈1
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    // 从队列的前面删除元素并返回该元素
    public int pop() {
        // 如果栈2为空
        if (stack2.isEmpty()) {
            // 将栈1中的元素依次弹出压入栈2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // 返回栈2的栈顶元素
        return stack2.pop();
    }

    /** Get the front element. */
    // 返回队列的前面的元素
    public int peek() {
        // 如果栈2为空
        if (stack2.isEmpty()) {
            // 将栈1中的元素依次弹出压入栈2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        // 返回栈2的栈顶元素
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    // 返回队列是否为空
    public boolean empty() {
        // 如果栈1和栈2都为空，则说明队列为空
        return stack1.isEmpty() && stack2.isEmpty();
    }
}