leetcode 用栈实现队列

这题以前写过，不过效率很低，看过剑指offer后突然发现用两个栈实现如此简单：

这里简单记录下，想看详细的可以参考剑指offer。

现在假设有三个元素：{a，b，c}

插入：直接插入stack1。此时stack1有{a,b,c}，stack2为空。

抛出：由于之前是直接插入stack1，队列是先进先出，所有最先被抛出的应该是a，而a在stack1中的最栈部，不能直接抛出，此时借助stack2，把stack1的元素逐个弹出并压入stack2，则此时顺序正好和之前的相反，stack1为空，stack2为{c,b,a}，这时可以弹出stack2的栈顶元素a了。

抛出a后，stack2的元素为{c,b}，如果还要抛出，直接抛出stack2的b即可。此时stack2的元素为{c}，stack1为空。

由此得出：当stack2不为空时，stack2的栈顶元素时最先进入队列的元素，直接弹出stack2的栈顶元素。当stack2为空时，把stack1的元素逐个弹出并压入stack2。

如果接下来再压入一个元素d，还是压入stack1，下次抛出时，由于stack2不为空，直接弹出栈顶元素c，c比d先进入队列，因此两个栈并不会矛盾。

截图：

leetcode 用栈实现队列

代码实现：


/**
 * @author yuan
 * @date 2019/1/30
 * @description
 */
public class MyQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    /** Get the front element. */
    public int peek() {
        if (!stack2.isEmpty()) {
            return stack2.peek();
        } else {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

   

}

leetcode 用栈实现队列

效率很不错了

leetcode 用栈实现队列

相关推荐