leetCode-232:Implement Queue using Stacks

问题描述

要求用两个栈实现队列。题目链接：点我

样例输入输出

输入：[“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

输入：[“MyQueue”, “empty”]

[[], []]

输出：[null, true]

问题解法

用一个栈放置 push 的值，另一个栈放置需要 pop 或 peek 的值，每次出队列时，如果 pop 或 peek 的值的栈为空，则从存储 push 值的栈依次弹出元素放入存储 pop 或 peek 的值的栈中，然后返回栈顶元素。代码如下

class MyQueue {

    private Stack<Integer> stack;

    private Stack<Integer> bak;

    public MyQueue() {
        stack = new Stack<>();
        bak = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        fillBakStack();
        return bak.pop();
    }

    public int peek() {
        fillBakStack();
        return bak.peek();
    }

    private void fillBakStack() {
        if (bak.empty()) {
            while (!stack.empty()) {
                bak.push(stack.pop());
            }
        }
    }

    public boolean empty() {
        return stack.empty() && bak.empty();
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */