# 232.用栈实现队列

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

* [232.用栈实现队列](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#232用栈实现队列)
  * [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#题目描述)
  * [方法 1](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#方法-1)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#思路)
    * [复杂度](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#复杂度)
    * [代码](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#代码)
  * [方法 2](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#方法-2)
    * [思路](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#思路-1)
    * [复杂度](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#复杂度-1)
    * [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/pages/-MNWDoo8VoubSq0eOiCI#代码javascriptc)

## 题目描述

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

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

```javascript
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

```javascript
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

```cpp
#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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/91-days-algorithm/basic/array-stack-queue/05.implement-queue-using-stacks.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.