Leetcode 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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["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

解题思路：

当我们使用两个栈来实现队列时，主要思路是利用栈的特性来实现先进先出（FIFO）的队列操作。

在这个实现中，我们使用两个栈：stack1和stack2。其中，stack1用于存储元素，而stack2作为辅助栈用于执行一些操作。

push(int x) 方法：
- 当要推入一个元素时，我们直接将元素压入stack1即可。
pop() 方法：
- 首先，我们检查stack2是否为空。如果不为空，说明其中已经有之前从stack1中弹出的元素，我们可以直接从stack2中弹出栈顶元素并返回。
- 如果stack2为空，我们需要将stack1中的元素全部逐个弹出并压入stack2，以实现先进先出的顺序。我们将stack1中的元素依次弹出并压入stack2，直到stack1为空。
- 然后，我们从stack2中弹出栈顶元素并返回。
peek() 方法：
- 类似于pop()方法，我们首先检查stack2是否为空。如果不为空，直接返回stack2的栈顶元素。
- 如果stack2为空，我们需要将stack1中的元素逐个弹出并压入stack2，以实现先进先出的顺序。我们将stack1中的元素依次弹出并压入stack2，直到stack1为空。
- 然后，我们返回stack2的栈顶元素，但不进行弹出操作。
empty() 方法：
- 我们只需检查stack1和stack2是否同时为空。如果两个栈都为空，说明队列为空，返回true；否则，返回false。

通过使用两个栈，我们可以在O(1)的时间复杂度下实现队列的push、pop、peek和empty操作。其中，在pop和peek操作时，如果stack2中已经有元素，我们可以直接从stack2中取出，而不需要重新调整栈的顺序。只有当stack2为空时，我们才需要将元素从stack1中弹出并压入stack2，以保持队列的先进先出顺序。

代码实现：

import java.util.Stack;

class MyQueue {
    Stack<Integer> stack1; // 用于存储元素的栈1
    Stack<Integer> stack2; // 用于辅助操作的栈2
  
    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }
  
    // 将元素推入队列
    public void push(int x) {
        stack1.push(x); // 直接将元素推入栈1
    }
  
    // 弹出队列的头部元素
    public int pop() {
        if (!stack2.isEmpty()) {
            return stack2.pop(); // 如果栈2非空，直接弹出栈2的顶部元素
        }
    
        // 如果栈2为空，则将栈1中的元素逐个弹出并压入栈2，实现队列的先进先出顺序
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    
        return stack2.pop(); // 弹出栈2的顶部元素
    }
  
    // 获取队列的头部元素（不弹出）
    public int peek() {
        if (!stack2.isEmpty()) {
            return stack2.peek(); // 如果栈2非空，直接返回栈2的顶部元素
        }
    
        // 如果栈2为空，则将栈1中的元素逐个弹出并压入栈2，实现队列的先进先出顺序
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    
        return stack2.peek(); // 返回栈2的顶部元素
    }
  
    // 检查队列是否为空
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty(); // 当栈1和栈2都为空时，队列为空
    }
}

代码跟踪：

假设我们按照以下顺序执行操作：

调用 push(1)，将元素1推入队列。
调用 push(2)，将元素2推入队列。
调用 push(3)，将元素3推入队列。
调用 pop()，弹出队列头部元素。
调用 push(4)，将元素4推入队列。
调用 peek()，查看队列头部元素。
调用 pop()，再次弹出队列头部元素。

下面是每个步骤的详细图示：

初始状态：

stack1: 
stack2:

执行 push(1)：

stack1: 
        1
stack2:

执行 push(2)：

stack1: 
        2
        1
stack2:

执行 push(3)：

stack1: 
        3
        2
        1
stack2:

执行 pop()：

stack1: 
stack2: 
        2
        3

注意：元素在stack2中按照逆序排列，这样弹出栈顶元素就相当于弹出队列头部元素。

执行 push(4)：

stack1: 
        4
stack2: 
        2
        3

执行 peek()：peek()之后只返回2元素，但是 2不出栈。

stack1: 
        4
stack2: 
        2
        3

注意：peek操作只返回栈顶元素，不进行弹出操作。

执行 pop()：2出栈

stack1: 
        4
stack2: 
        3

最终，通过这个示例，可以看到在执行各种操作时，栈1和栈2的变化过程，以及如何利用两个栈实现队列的先进先出特性。

目录CONTENT

Leetcode 232.用栈实现队列

Leetcode 232.用栈实现队列

解题思路：

代码实现：

代码跟踪：

评论区