LeetCode（Queue)232. Implement Queue using Stacks

1.问题

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.

2. 解题思路

方法1：

1.使用了两个栈来实现队列，入队操作只需将元素加入到inStack栈中
2.出队操作需要先将inStack栈中的元素依次弹出并加入到outStack栈中
3.再从outStack栈中弹出队列头元素。由于outStack栈中的元素顺序已经反转，因此可以保证出队操作的正确性。

3. 代码

代码1：

class MyQueue {
    Stack<Integer> inStack; //定义一个输入栈inStack
    Stack<Integer> outStack; //定义一个输出栈outStack
    /** 在这里初始化你的数据结构 */
    public MyQueue() {
     //初始化两个栈
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    /** 将元素 x 推到队列的后面。 */
    public void push(int x) {
     //将元素x加入队列
        inStack.push(x);
    }
    /** 从队列前面移除元素并返回该元素。 */
    public int pop() {
     //弹出队列头元素
        peek(); //确保outStack不为空
        return outStack.pop();
    }
    /** 获取前面的元素。 */
    public int peek() {
     //返回队列头元素
        if(outStack.isEmpty()){
     //如果outStack为空，则需要将inStack中的元素依次弹出并加入到outStack中
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek(); //返回outStack的栈顶元素
    }
    /** 返回队列是否为空 */
    public boolean empty() {
     //判断队列是否为空
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

解题思路基本相同

class MyQueue {
    Stack<Integer> input = new Stack();
    Stack<Integer> output = new Stack();
    public void push(int x) {
        input.push(x);
    }
    public void pop() {
        peek();
        output.pop();
    }
    public int peek() {
        if (output.empty())
            while (!input.empty())
                output.push(input.pop());
        return output.peek();
    }
    public boolean empty() {
        return input.empty() && output.empty();
    }
}

代码比较容易理解

class MyQueue {
   Stack<Integer> s1=new Stack<Integer>();
   Stack<Integer> s2=new Stack<Integer>();
    // 将元素 x 推到队列的后面.
    public void push(int x) {
        s1.push(x);
    }
    // 移除队列前面的元素.
    public void pop() {
        if(!s2.empty())
          s2.pop();
        else{
        while(!s1.empty())
         s2.push(s1.pop());
         s2.pop();
      }
    }
    // 获取前面的元素.
    public int peek() {
        if(!s2.empty())
         return s2.peek();
        else{
        while(!s1.empty())
         s2.push(s1.pop());
        return s2.peek();
      }
    }
    // 返回队列是否为空
    public boolean empty() {
        if(s1.empty()&&s2.empty())
            return true;
        else
            return false;
    }
}