力扣面试03.04题：用栈实现队列 - 双栈解法详解

内容简介

本文详细解析了力扣面试03.04题"用栈实现队列"的双栈解法。通过两个栈的巧妙配合，实现了队列的先进先出(FIFO)特性。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握栈与队列相互转换的核心技巧。

算法思路

1‌.双栈结构‌：使用输入栈s1和输出栈s2

‌2.入队操作‌：直接压入输入栈s1

‌3.出队操作‌：当输出栈s2为空时，将输入栈s1的所有元素弹出并压入s2

‌4.队首元素‌：与出队操作类似，但不移除元素

‌5.判空条件‌：两个栈同时为空时队列为空

代码实现（带详细注释）

class MyQueue {
public:
    stack<int> s1;  // 输入栈，负责接收push操作
    stack<int> s2;  // 输出栈，负责pop和peek操作

    MyQueue() {
        // 构造函数，无需特殊初始化
    }
    
    // 入队操作：直接压入输入栈
    void push(int x) {
        s1.push(x);
    }
    
    // 出队操作：移除并返回队首元素
    int pop() {
        // 如果输出栈为空，将输入栈元素全部转移到输出栈
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());  // 将s1栈顶元素压入s2
                s1.pop();           // 弹出s1栈顶元素
            }
        }
        int res = s2.top();  // 获取输出栈栈顶元素
        s2.pop();            // 弹出输出栈栈顶元素
        return res;          // 返回队首元素
    }
    
    // 获取队首元素但不移除
    int peek() {
        // 如果输出栈为空，将输入栈元素全部转移到输出栈
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();  // 返回输出栈栈顶元素
    }
    
    // 判断队列是否为空
    bool empty() {
        return s1.empty() && s2.empty();  // 两个栈都为空时队列为空
    }
};

复杂度分析

‌push操作‌：O(1)，直接压入输入栈

‌pop/peek操作‌：均摊O(1)，最坏情况下O(n)

‌空间复杂度‌：O(n)，需要两个栈存储所有元素

优化方向

‌延迟转移‌：只在需要时才转移元素，减少不必要的操作

‌代码复用‌：将元素转移逻辑提取为单独函数

‌异常处理‌：添加对空队列pop/peek操作的处理

总结

双栈实现队列是数据结构转换的经典问题，通过输入栈和输出栈的配合，巧妙地用后进先出(LIFO)的栈实现了先进先出(FIFO)的队列特性。理解这种解法有助于掌握栈和队列的核心概念及其相互转换技巧。