力扣225题：用队列实现栈 - 双队列解法详解

内容简介

本文详细解析了力扣第225题"用队列实现栈"的双队列解法。通过两个队列的交替使用，实现了栈的后进先出(LIFO)特性。这种方法虽然时间复杂度为O(n)，但思路清晰，是理解栈和队列关系的经典解法。文章包含完整注释代码、算法思路讲解和复杂度分析。

算法思路

‌双队列结构‌：使用两个队列s1和s2，其中s1始终维护栈的顺序

‌push操作‌：先将所有元素转移到s2，放入新元素后再转移回来，确保新元素在队列前端

‌pop/top操作‌：直接操作s1的队首元素

‌empty判断‌：检查s1是否为空

完整代码（带注释）

class MyStack {
public:
    queue<int> s1;  // 主队列，始终维护栈的顺序
    queue<int> s2;  // 辅助队列，用于临时存储
    
    MyStack() {}  // 构造函数
    
    // 入栈操作
    void push(int x) {
        // 将s1中所有元素转移到s2
        while (!s1.empty()) {
            s2.push(s1.front());
            s1.pop();
        }
        
        // 放入新元素到空队列s1
        s1.push(x);
        
        // 将s2中元素转移回s1
        while (!s2.empty()) {
            s1.push(s2.front());
            s2.pop();
        }
    }
    
    // 出栈操作
    int pop() {
        int a = s1.front();  // 获取栈顶元素
        s1.pop();            // 移除栈顶元素
        return a;            // 返回被移除的元素
    }
    
    // 获取栈顶元素
    int top() {
        return s1.front();  // 直接返回s1队首元素
    }
    
    // 判断栈是否为空
    bool empty() {
        return s1.empty();  // 检查s1是否为空
    }
};

复杂度分析

‌push操作‌：O(n)，需要两次完整队列转移

‌pop/top/empty操作‌：O(1)，直接访问队列前端

‌空间复杂度‌：O(n)，使用两个队列存储元素

优化方向

‌单队列实现‌：可以只使用一个队列，通过循环移位实现

‌改进push效率‌：记录栈顶元素，减少部分情况下的操作次数

‌使用其他数据结构‌：考虑使用链表等更灵活的结构

总结

本文提供的双队列解法是用队列实现栈的经典方法，通过队列间的元素转移实现了栈的后进先出特性。理解这种解法有助于深入掌握数据结构的相互转换原理。