# \[225]\[简单]\[栈]\[队列] 用队列实现栈

## 题目描述

[225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

* 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
* 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

```
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
```

提示：

* 1 <= x <= 9
* 最多调用100 次 push、pop、top 和 empty
* 每次调用 pop 和 top 都保证栈不为空

进阶：你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

## 解题思路

要把队列模拟成栈, 就要在一个新元素进入队列时, 把之前所有的元素排放在这个新元素之后, 这样在进行队列弹出时, 才能最先把这个新元素弹出, 实现对后进先出栈性质的模拟.

使用一个队列就可以完成这个操作. 在一个新元素进入队列后, 将它之前所有的队列元素出列, 然后重新加入到队列中. 由于每个元素入栈时都会进行这个操作, 可以保证每个新元素都在旧元素之前. 因此队列里元素的顺序是逆转存储的.

这样push操作的时间复杂度是$$O(n)$$, 其他操作的时间复杂度为$$O(1)$$.

![](/files/-MV4UOUq5iNmdFhOfW8A)

```python
class MyStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        raw_length = len(self.queue)
        self.queue.append(x)
        for _ in range(raw_length):
            self.queue.append(self.queue.pop(0))

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.queue.pop(0) if self.queue else None

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue[0] if self.queue else None

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/dui-lie/225-yong-dui-lie-shi-xian-zhan.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.