LeetCode.232.Implement Queue using Stacks 用栈实现队列

题目描述

232 Implement Queue using Stacks
https://leetcode-cn.com/problems/implement-queue-using-stacks/

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:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
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).

---

相似题目

58同城基础架构部中间件，一面面试题

LeetCode.剑指offer.009.用两个栈实现队列
LeetCode.232.Implement Queue using Stacks 用栈实现队列
LeetCode.225.Implement Stack using Queues 用队列实现栈

---

解题过程

两个栈EnQueueO(1)DeQueueO(n)

两个栈，一个始终是空的
EnQueue: 插入到非空栈末尾
DeQueue：非空栈顶n-1个元素pop到空栈，返回最后一个元素，再全部push回非空栈
peek: 用一个变量始终记住栈底（队头）元素，push、pop时更新，peek时直接返回

EnQueue时间复杂度 O(1)，DeQueue时间复杂度 O(n)

private static class MyQueue {
    private Deque<Integer> nonEmptyQueue;
    private Deque<Integer> emptyQueue;
    private Integer head; // 队列头

    /** Initialize your data structure here. */
    public MyQueue() {
        nonEmptyQueue = new LinkedList<>();
        emptyQueue = new LinkedList<>();
        head = null;
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (nonEmptyQueue.isEmpty()) {
            head = x;
        }
        nonEmptyQueue.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        head = null;
        int size = nonEmptyQueue.size();
        for (int i = 0; i < size - 1; i++) {
            head = nonEmptyQueue.pop();
            emptyQueue.push(head);
        }
        int ret = nonEmptyQueue.pop();
        while (!emptyQueue.isEmpty()) {
            nonEmptyQueue.push(emptyQueue.pop());
        }
        return ret;
    }

    /** Get the front element. */
    public int peek() {
        return head;
    }

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

两个栈EnQueueO(1)DeQueue摊还O(1)

EnQueue：将元素压入s1。
DeQueue：判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
peek：s2不空则取s2栈顶，否则取s1栈底，可以用一个变量记住s1栈底元素
这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。

DeQueue时间复杂度可以具体查下“摊还分析”

两个栈EnQueueO(n)DeQueueO(1)

要想 出队 时能够 O(1)，需要让栈顶始终是最先入站的元素。
EnQueue：非空栈元素再依次pop倒入空栈，新元素push到刚腾空的栈，再把另一个栈的元素挨个push进来
DeQueue：直接pop非空栈顶
peek：直接peek非空栈顶

EnQueue时间复杂度 O(n)，DeQueue时间复杂度 O(1)

---

GitHub代码

algorithms/leetcode/leetcode/_232_ImplementQueueUsingStacks.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_232_ImplementQueueUsingStacks.java

---