232.用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

• 232.用栈实现队列

  • 题目描述

  • 方法 1

    • 思路

    • 复杂度

    • 代码

  • 方法 2

    • 思路

    • 复杂度

    • 代码(JavaScript/C++)

题目描述

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false
说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1

思路

由于队列是 FIFI (先进先出)，而栈是 FILO (先进后出)。如果要用栈来模拟队列，则每次往模拟队列增加元素的时候，这个元素需要放在栈底，因为它是最后才会出列。

方法之一是，每次需要往模拟队列尾端 push 一个新元素时：

• 先把栈中的全部元素暂时取出

• 将新元素入栈到栈底

• 再将刚刚取出来元素重新入栈

因此我们还需要一个辅助栈来存暂时取出来的元素。

复杂度

• 时间复杂度：入列操作是 $O(n)$，每次入列时，除新增元素外，每个元素都需要分别出栈入栈 2 次 (从模拟队列的栈中弹出，压入辅助栈，再从辅助栈弹出，压入队列模拟栈)。压入、弹出操作的时间复杂度都是 $O(1)$，所以总的时间复杂度差不多是 $O(4n)$，忽略掉常数，最后得到 $O(n)$。出列操作是 $O(1)$。

• 空间复杂度：$O(n)$，n 是队列的大小，需要一个大小为 n 的栈来模拟队列，还需要一个大小为 n 的辅助空间，但总的空间复杂度还是 $O(n)$。

代码

JavaScript Code

class MyQueue {
    constructor() {
        this.stack = [];
    }

    push(x) {
        const helper = [];
        while (!this.empty()) {
            helper.push(this.stack.pop());
        }
        this.stack.push(x);
        while (helper.length) {
            this.stack.push(helper.pop());
        }
    }

    peek() {
        return this.stack[this.stack.length - 1];
    }

    pop() {
        return this.stack.pop();
    }

    empty() {
        return this.stack.length === 0;
    }
}

方法 2

思路

方法 1 是在元素入列的时候，就考虑好了它出列的顺序，但我们还可以转换一下思路，在元素需要出列的时候再来考虑这个问题，这样的话：

1. 入列时，直接 push 到栈中；

2. 出列时，由于先入列的元素在栈底，需要先把其他元素弹出，依次压入辅助栈；

3. 栈底元素弹出，出列；

4. 刚才出栈的其他元素依次从辅助栈弹出，重新压入模拟栈。

再仔细想想的话：

• 第 2 步中，辅助栈中的元素出栈顺序刚好就是队列的出列顺序；

• 所以到第 4 步的时候，我们根本没必要把元素再从辅助栈转移到模拟栈；

• 下一次 pop 操作时，直接从辅助栈弹出元素就可以了；

• 如果辅助栈中没有元素了，我们再重复第 2 步。

这样的话，我们的队列元素其实是用了两个栈来储存，所以在判断队列是否为空的时候，两个栈都要考虑进去。

复杂度

• 时间复杂度：入列是 $O(1)$，出列最差的情况就是每个元素都要从模拟栈中弹出，压入辅助栈，再从辅助栈中弹出，所以是 $O(n)$。

• 空间复杂度：$O(n)$，n 为队列大小。

代码(JavaScript/C++)

JavaScript Code

class MyQueue {
    constructor() {
        this.stack = new MyStack();
        this.helper = new MyStack();
    }

    push(x) {
        this.stack.push(x);
    }

    peek() {
        if (this.helper.empty()) {
            while (!this.stack.empty()) {
                this.helper.push(this.stack.pop());
            }
        }
        return this.helper.peek();
    }

    pop() {
        if (this.helper.empty()) {
            while (!this.stack.empty()) {
                this.helper.push(this.stack.pop());
            }
        }
        return this.helper.pop();
    }

    empty() {
        return this.stack.empty() && this.helper.empty();
    }
}

class MyStack {
    constructor() {
        this.stack = [];
    }
    push(x) {
        this.stack.push(x);
    }
    pop() {
        return this.stack.pop();
    }
    peek() {
        return this.stack[this.stack.length - 1];
    }
    empty() {
        return this.stack.length === 0;
    }
}

C++ Code

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> stack_in_;
    stack<int> stack_out_;
    void pour_to_stack_out_() {
        while (!stack_in_.empty()) {
            int top = stack_in_.top();
            stack_in_.pop();
            stack_out_.push(top);
        }
    };
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

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

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (stack_out_.empty()) { 
            pour_to_stack_out_();
        }
        int top = stack_out_.top();
        stack_out_.pop();
        return top;
    }

    /** Get the front element. */
    int peek() {
        if (stack_out_.empty()) { 
            pour_to_stack_out_();
        }
        return stack_out_.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stack_in_.empty() && stack_out_.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();
 * bool param_4 = obj->empty();
 */

更多题解可以访问：https://github.com/suukii/91-days-algorithm