LeetCode: 232 Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, pop, peek, empty).

push(x) — Pushes element x to the back of the queue.
pop() — Removes the element from the front of the queue.
peek() — Gets the front element.
empty() — Returns whether the queue is empty.

Example:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output
[null, null, null, 1, 1, false]

Explanation:

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

问题

只使用两个栈来实现一个先进先出 (FIFO) 的队列。实现的队列应支持普通队列的所有功能（push、pop、peek、empty）。

push(x) — 将元素 x 推到队列的后面。
pop() — 移除队列前面的元素。
peek() — 获取队列前面的元素。
empty() — 返回队列是否为空。

解决方案

双栈法

Approach: Two Stacks / 双栈法

This approach uses two stacks to simulate the behavior of a queue. One stack (in_stack) is used to handle the input (push operation), and the other stack (out_stack) is used to handle the output (pop and peek operations). By reversing the order of elements when transferring from in_stack to out_stack, we can mimic the FIFO behavior of a queue.

这种方法使用两个栈来模拟队列的行为。一个栈 (in_stack) 用于处理输入（push 操作），另一个栈 (out_stack) 用于处理输出（pop 和 peek 操作）。通过将元素从 in_stack 转移到 out_stack 时反转顺序，我们可以模拟队列的先进先出行为。

Implementation / 实现

Python

class MyQueue:

    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self.move()
        return self.out_stack.pop()

    def peek(self) -> int:
        self.move()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def move(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

Explanation / 解释

Initialize the Stacks / 初始化栈
```
self.in_stack = []
self.out_stack = []
```
- English: We initialize two stacks: in_stack for input operations and out_stack for output operations.
- Chinese: 我们初始化两个栈：in_stack 用于输入操作，out_stack 用于输出操作。
Push Operation / 入队操作
```
def push(self, x: int) -> None:
   self.in_stack.append(x)
```
- English: The push method adds an element to the in_stack.
- Chinese: push 方法将元素添加到 in_stack 中。
Pop Operation / 出队操作
```
def pop(self) -> int:
   self.move()
   return self.out_stack.pop()
```
- English: The pop method removes the front element from the queue by ensuring elements are transferred from in_stack to out_stack if necessary.
- Chinese: pop 方法通过确保必要时将元素从 in_stack 转移到 out_stack 中，来移除队列中的前端元素。
Peek Operation / 获取队列前端元素
```
def peek(self) -> int:
   self.move()
   return self.out_stack[-1]
```
- English: The peek method returns the front element without removing it, by checking the top element of the out_stack.
- Chinese: peek 方法通过检查 out_stack 的顶部元素，返回前端元素而不移除它。
Empty Operation / 队列是否为空
```
def empty(self) -> bool:
   return not self.in_stack and not self.out_stack
```
- English: The empty method checks if both in_stack and out_stack are empty, indicating that the queue is empty.
- Chinese: empty 方法检查 in_stack 和 out_stack 是否都为空，表示队列为空。
Move Helper Function / 转移辅助函数
```
def move(self) -> None:
   if not self.out_stack:
       while self.in_stack:
           self.out_stack.append(self.in_stack.pop())
```
- English: The move method transfers elements from in_stack to out_stack only when out_stack is empty, ensuring the correct order for FIFO operations.
- Chinese: move 方法仅在 out_stack 为空时，将元素从 in_stack 转移到 out_stack，以确保先进先出操作的正确顺序。

Recursive Approach / 递归方法

A recursive approach for implementing a queue using stacks is not practical due to the nature of the problem. The iterative method using two stacks is the optimal solution.

使用栈实现队列的递归方法由于问题的性质，实际上并不实用。使用双栈的迭代方法是最佳解决方案。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度:
- push: O(1)
- pop: Amortized O(1)
- peek: Amortized O(1)
- empty: O(1)
Space Complexity / 空间复杂度: O(n), where n is the number of elements in the queue.

Key Concept / 关键概念

Two Stacks / 双栈: By using two stacks, we can simulate the FIFO behavior of a queue, leveraging the LIFO property of stacks.
双栈: 通过使用两个栈，我们可以利用栈的后进先出特性来模拟队列的先进先出行为。

Summary / 总结

English: The Two Stacks method effectively simulates a queue using the LIFO nature of stacks, ensuring that all queue operations are performed in constant or amortized constant time.
Chinese: 双栈方法有效地利用栈的后进先出特性来模拟队列，确保所有队列操作在常数或摊销常数时间内完成。

Tips / 提示

English: Practice problems that require you to simulate one data structure using another to gain a deeper understanding of underlying principles.
Chinese: 练习需要使用一种数据结构模拟另一种数据结构的问题，以更深入地理解其底层原理。

Solution Template for Similar Questions / 提示

English: Consider using two stacks or two queues to simulate each other when you need to implement queue or stack functionality with a different underlying data structure.
Chinese: 当需要使用不同的底层数据结构实现队列或栈功能时，考虑使用两个栈或两个队列相互模拟。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice implementing data structures using other data structures to strengthen your understanding of algorithmic principles.
Chinese: 练习使用其他数据结构实现数据结构，以加强对算法原理的理解。

mplement Queue using Stacks – Leetcode 232 – Python by NeetCodeIO

Post Views: 13

CODEBITWAVE

LeetCode: 232 Implement Queue using Stacks