力扣刷题笔记：232.用栈实现队列（只使用栈的基本操作，很容易理解）

男娘i 2022-10-23 11:11 149阅读 0赞

## 题目： ##

232、用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

> void push(int x) 将元素 x 推到队列的末尾  
> int pop() 从队列的开头移除并返回元素  
> int peek() 返回队列开头的元素  
> boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

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

进阶：

> 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：

> 输入：  
> \[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”\]  
> \[\[\], \[1\], \[2\], \[\], \[\], \[\]\]  
> 输出：  
> \[null, null, null, 1, 1, false\]  
> 解释：  
> MyQueue myQueue = new MyQueue();  
> myQueue.push(1); // queue is: \[1\]  
> myQueue.push(2); // queue is: \[1, 2\] (leftmost is front of the queue)  
> myQueue.peek(); // return 1  
> myQueue.pop(); // return 1, queue is \[2\]  
> myQueue.empty(); // return false

提示：

> 1 <= x <= 9  
> 最多调用 100 次 push、pop、peek 和 empty  
> 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

## 题解思路： ##

队列是一种 先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）。

栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）。

为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。

**入队（push）**

一个队列是 FIFO 的，但一个栈是 LIFO 的。这就意味着最新压入的元素必须得放在栈底。为了实现这个目的，我们首先需要把 s1 中所有的元素移到 s2 中，接着把新元素压入 s1。最后把 s2 中所有的元素弹出，再把弹出的元素压入 s1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]

**出队（pop）**

直接从 s1 弹出就可以了，因为 s1 的栈顶元素就是队列的队首元素。同时我们把弹出之后 s1 的栈顶元素赋值给代表队首元素的 front 变量。  
![在这里插入图片描述][20210305090538151.png]

## 题解python代码： ##

class MyQueue:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.A = []
            self.B = []
            self.front = None
    
    
        def push(self, x: int) -> None:
            """
            Push element x to the back of queue.
            """
            while self.A:
                self.B.append(self.A.pop())
            self.A.append(x)
            while self.B:
                self.A.append(self.B.pop())
            self.front = self.A[-1]
    
    
        def pop(self) -> int:
            """
            Removes the element from in front of queue and returns that element.
            """
            t = self.A.pop()
            if self.A: self.front = self.A[-1]
            else: self.front = None
            return t
            
    
    
        def peek(self) -> int:
            """
            Get the front element.
            """
            return self.front
    
    
        def empty(self) -> bool:
            """
            Returns whether the queue is empty.
            """
            return not self.A 
    
    # Your MyQueue object will be instantiated and called as such:
    # obj = MyQueue()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.peek()
    # param_4 = obj.empty()

![在这里插入图片描述][20210305090627398.png]

> 作者：a-qing-ge  
> 链接：[https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/guan-fang-ti-jie-fang-fa-yi-pythonban-by-95l6/][https_leetcode-cn.com_problems_implement-queue-using-stacks_solution_guan-fang-ti-jie-fang-fa-yi-pythonban-by-95l6]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/implement-queue-using-stacks/][https_leetcode-cn.com_problems_implement-queue-using-stacks]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]: /images/20221023/1130358e3e1a47498fbd7ce8cf473838.png
[20210305090538151.png]: /images/20221023/d33eb8b5eab54dc9b0760f9d9515d8ff.png
[20210305090627398.png]: /images/20221023/92a3f790082947fea33b10a36fae265d.png
[https_leetcode-cn.com_problems_implement-queue-using-stacks_solution_guan-fang-ti-jie-fang-fa-yi-pythonban-by-95l6]: https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/guan-fang-ti-jie-fang-fa-yi-pythonban-by-95l6/
[https_leetcode-cn.com_problems_implement-queue-using-stacks]: https://leetcode-cn.com/problems/implement-queue-using-stacks/