03.04、化栈为队

03.04、化栈为队

1、题目描述

实现一个 MyQueue 类，该类用两个栈来实现一个队列。

2、解题思路

本题要求使用两个栈来实现一个队列。队列遵循先进先出（FIFO）的原则，而栈遵循后进先出（LIFO）的原则。因此，我们需要两个栈来模拟队列的行为：

1. pushS：用于存储入队的元素。
2. popS：用于反转元素顺序，以实现队列的出队操作。

3、解题步骤

1. 入队操作 (push)：
   • 将新元素直接压入到 pushS 栈中。
2. 出队操作 (pop)：
   • 检查 popS 栈是否为空：
     • 如果 popS 为空，将 pushS 中的所有元素逐个弹出并压入 popS。这一步将反转元素的顺序，从而实现队列的 FIFO 行为。
     • 如果 popS 不为空，直接弹出并返回 popS 的栈顶元素。
3. 获取队首元素 (peek)：
   • 类似于 pop 操作，只是我们不弹出 popS 栈的栈顶元素，而是返回它。
4. 检查队列是否为空 (empty)：
   • 队列为空的条件是 pushS 和 popS 都为空。

4、代码详解

class MyQueue {
private:
    stack<int> pushS; // 入队栈
    stack<int> popS;  // 出队栈

public:
    MyQueue() {}

    void push(int x) { pushS.push(x); }

    int pop() {
        // 如果出队栈为空，将入队栈的所有元素移到出队栈中
        if (popS.empty()) {
            while (!pushS.empty()) {
                popS.push(pushS.top());
                pushS.pop();
            }
        }
        int ret = popS.top(); // 获取出队栈的栈顶元素
        popS.pop();           // 弹出该元素
        return ret;
    }

    int peek() {
        // 如果出队栈为空，将入队栈的所有元素移到出队栈中
        if (popS.empty()) {
            while (!pushS.empty()) {
                popS.push(pushS.top());
                pushS.pop();
            }
        }
        return popS.top(); // 返回出队栈的栈顶元素
    }

    bool empty() { return pushS.empty() && popS.empty(); }
};

5、时间复杂度

• 入队操作 (push)：O(1)
• 出队操作 (pop)：均摊 O(1)，因为每个元素最多只会从 pushS 转移到 popS 一次。
• 获取队首元素 (peek)：均摊 O(1)
• 检查队列是否为空 (empty)：O(1)

6、空间复杂度

• 使用了两个栈存储元素，空间复杂度为 O(n)，其中 n 是队列中元素的数量。

这道题通过使用两个栈，成功模拟了队列的行为，展示了栈和队列之间的转换关系。