STL 容器适配器：Stack/Queue 底层模拟与算法实战

deque 是双端队列，虽名字带'队列'，但和 FIFO 结构的队列无实际关联。它是支持头尾高效增删、可随机访问的双端动态容器，是 STL 中灵活高效的基础容器之一。下一章会简单介绍它，目前大家可以先把它当作类似 vector 和 list 的容器来理解。

Container _con：是 stack 的底层容器对象，实际存储所有元素；stack 的所有操作都是通过封装这个容器的接口实现的（体现'适配器'的封装思想）。

核心接口说明

• push(const T& x)：调用底层容器 _con 的 push_back，把元素 x 插入到栈顶（对应容器尾部）。
• pop()：调用 _con 的 pop_back，删除栈顶元素（不返回值）。
• const T& top()：返回 _con.back()，即栈顶元素的 const 引用（避免拷贝，也防止外部修改）。
• empty()：返回 _con.empty() 的结果，判断栈是否为空。
• size()：返回 _con.size()，获取栈中元素的个数。

为什么不需要手动定义默认成员函数？

编译器会自动为 stack 生成默认成员函数（包括默认构造、拷贝构造、赋值重载、析构函数等），而这些自动生成的函数会调用底层容器（如 deque）的对应函数 —— 比如默认构造调用容器的无参构造、拷贝构造调用容器的拷贝构造，能完整实现 stack 的初始化、拷贝、资源释放等需求。同时 stack 是容器适配器，自身不管理额外动态资源，所有功能都依赖底层容器，因此无需手动提供默认成员函数。

1. queue 介绍

• queue 的定位：队列是一种容器适配器，专门用于在 FIFO（先进先出）上下文中操作，其中从容器一端插入元素，另一端提取元素。
• queue 的实现逻辑：队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
• queue 对底层容器的要求：底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

queue 的默认底层容器：标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。

2. queue 模拟实现

namespace bit {
    // 容器适配器：模拟实现 queue（FIFO 先进先出）
    // T：元素类型；Container：底层存储容器，默认用 deque<T>
    template<class T, class Container = deque<T>>
    class queue {
    public:
        // 入队：将元素 x 插入队列尾部（复用底层容器的尾插）
        void push(const T& x) { _con.push_back(x); }
        
        // 出队：删除队列头部元素（复用底层容器的头删）
        void pop() { _con.pop_front(); }
        
        // 获取队列头部元素（const 引用返回，避免拷贝、防止外部修改）
        const T& front() { return _con.front(); }
        
        // 获取队列尾部元素（const 引用返回，避免拷贝、防止外部修改）
        const T& back() { return _con.back(); }
        
        // 判断队列是否为空（复用底层容器的判空）
        bool empty() { return _con.empty(); }
        
        // 获取队列中元素的个数（复用底层容器的 size）
        size_t size() { return _con.size(); }
        
    private:
        Container _con; // 底层容器，实际存储队列的所有元素
    };
}

Container _con：是 queue 的底层容器对象，实际存储所有元素；queue 的所有操作都是通过封装这个容器的接口实现的（体现'适配器'的封装思想）。

核心接口说明

• push(const T& x)：调用底层容器 _con 的 push_back，把元素 x 插入到队列尾部（对应容器尾部）。
• pop()：调用 _con 的 pop_front，删除队列头部元素（不返回值）。
• const T& front()：返回 _con.front()，即队列头部元素的 const 引用（避免拷贝，也防止外部修改）。
• const T& back()：返回 _con.back()，即队列尾部元素的 const 引用（避免拷贝，也防止外部修改）。
• empty()：返回 _con.empty() 的结果，判断队列是否为空。
• size()：返回 _con.size()，获取队列中元素的个数。

1. 最小栈

思路分析

用一个数据栈存储所有入栈元素，另一个最小值栈同步维护对应阶段的栈内最小值；入栈时仅当新元素小于等于最小值栈顶（或最小值栈为空）时，才将其压入最小值栈；出栈时若弹出的元素是当前最小值（与最小值栈顶相等），则同步弹出最小值栈顶；获取最小值直接返回最小值栈顶，实现 O(1) 时间复杂度的查询，同时保证入栈、出栈操作高效可行。

参考实现

class MinStack {
public:
    MinStack() {}
    
    void push(int val) {
        _st.push(val); // 压入数据栈
        // 维护最小值栈，空或当前值≤栈顶时压入
        if (_minst.empty() || val <= _minst.top()) {
            _minst.push(val);
        }
    }
    
    void pop() {
        // 弹出的是最小值时，同步弹出最小值栈
        if (!_minst.empty() && _minst.top() == _st.top()) {
            _minst.pop();
        }
        _st.pop(); // 弹出数据栈
    }
    
    int top() {
        return _st.top(); // 返回数据栈顶
    }
    
    int getMin() {
        return _minst.top(); // 返回最小值栈顶
    }
    
private:
    stack<int> _st;      // 数据栈：存储所有元素
    stack<int> _minst;   // 最小值栈：存储各阶段最小值
};

2. 栈的压入、弹出序列

思路分析

模拟栈的入栈、出栈过程，最终栈为空则代表符合规则：先将元素入栈，若当前入栈元素与出栈数组的待匹配元素一致，则让该入栈元素出栈，同时出栈数组的匹配指针后移；重复这一过程，直到所有元素处理完后，若栈为空，说明入栈、出栈的顺序是合法的。

参考实现

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st; // 模拟出入栈
        int pushi = 0;
        int popi = 0;
        
        // 入完了就跳出循环
        while (pushi < pushV.size()) {
            st.push(pushV[pushi++]);
            
            // 不匹配
            if (st.top() != popV[popi]) {
                continue;
            }
            // 匹配
            else {
                while (!st.empty() && st.top() == popV[popi]) {
                    popi++;
                    st.pop();
                }
            }
        }
        
        // 等于空说明符合栈的规则
        return st.empty();
    }
};

3. 逆波兰表达式求值

思路解析

利用栈的特性，遇到数字入栈，遇到运算符则弹出栈顶两个元素进行运算，结果再压回栈中。遍历结束后，栈中剩余的唯一元素即为结果。

参考实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto& e : tokens) {
            // 操作符 取栈顶两个元素进行运算，运算结果入栈
            if (e == "+" || e == "-" || e == "*" || e == "/") {
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                switch (e[0]) {
                    case '+': st.push(left + right); break;
                    case '-': st.push(left - right); break;
                    case '*': st.push(left * right); break;
                    case '/': st.push(left / right); break;
                }
            } else {
                // 操作数直接入栈，字符串转整型
                st.push(stoi(e));
            }
        }
        return st.top();
    }
};

4. 用栈实现队列

思路分析

使用两个栈配合：一个负责入队（push_st），一个负责出队（pop_st）。入队时直接压入 push_st；出队时，如果 pop_st 为空，则将 push_st 中的所有元素倒序转移到 pop_st 中，此时 pop_st 的栈顶即为队列的队头元素。

参考实现

class MyQueue {
public:
    // 构造函数：编译器自动生成，初始化两个空栈
    MyQueue() {}
    
    // 入队操作：将元素 x 加入队列（直接压入 push_st 栈）
    void push(int x) {
        push_st.push(x);
    }
    
    // 出队操作：移除并返回队列的队头元素
    int pop() {
        // 1. 若 pop_st 为空，将 push_st 中的所有元素倒序转移到 pop_st 中
        if (pop_st.empty()) {
            while (!push_st.empty()) {
                int top = push_st.top();
                push_st.pop();
                pop_st.push(top);
            }
        }
        // 2. 保护逻辑：若两个栈都为空（队列空），返回 0
        if (pop_st.empty()) {
            return 0;
        }
        // 3. 弹出 pop_st 栈顶（即队列队头）并返回
        int top = pop_st.top();
        pop_st.pop();
        return top;
    }
    
    // 查看队头元素：返回队列的队头元素（不移除）
    int peek() {
        // 1. 若 pop_st 为空，将 push_st 中的所有元素倒序转移到 pop_st 中
        if (pop_st.empty()) {
            while (!push_st.empty()) {
                int top = push_st.top();
                push_st.pop();
                pop_st.push(top);
            }
        }
        // 2. 保护逻辑：若两个栈都为空（队列空），返回 0
        if (pop_st.empty()) {
            return 0;
        }
        // 3. 返回 pop_st 栈顶（即队列队头），不弹出元素
        int top = pop_st.top();
        return top;
    }
    
    // 判断队列是否为空：两个栈都为空时，队列才为空
    bool empty() {
        return push_st.empty() && pop_st.empty();
    }
    
private:
    stack<int> push_st; // 入数据栈：专门接收新加入队列的元素
    stack<int> pop_st;  // 出数据栈：专门用于弹出/查看队列的队头元素
};

5. 用队列实现栈

思路分析

• push 操作：始终向'非空的队列'中加入元素（保证新元素在队列尾部，最终成为栈顶）；
• pop 操作：将非空队列的元素（除了最后一个）全部倒入空队列，剩下的最后一个元素就是栈顶，直接弹出即可。

参考实现

class MyStack {
public:
    MyStack() {}
    
    // 入栈：压入非空队列（双空则入 q2）
    void push(int x) {
        if (!q1.empty()) {
            q1.push(x);
        } else {
            q2.push(x);
        }
    }
    
    int pop() {
        // 情况 1：q1 为空，处理 q2
        if (q1.empty()) {
            // 将 q2 前 n-1 个元素导入 q1，保留最后一个作为栈顶
            while (q2.size() > 1) {
                int front = q2.front();
                q2.pop();
                q1.push(front);
            }
            // 取出并弹出 q2 中仅剩的栈顶元素
            int ret = q2.front();
            q2.pop();
            return ret;
        }
        // 情况 2：q2 为空，处理 q1（逻辑同 q2）
        else {
            while (q1.size() > 1) {
                int front = q1.front();
                q1.pop();
                q2.push(front);
            }
            int ret = q1.front();
            q1.pop();
            return ret;
        }
        // 栈空保护：两个队列都为空时返回 0（注：此语句无法执行，已提前在 top() 处理）
        if (empty()) {
            return 0;
        }
    }
    
    // 取栈顶：返回非空队列的队尾，栈空返回 0
    int top() {
        if (!q1.empty()) {
            return q1.back();
        } else if (!q2.empty()) {
            return q2.back();
        } else {
            return 0;
        }
    }
    
    // 判断栈空：两个队列都为空即为栈空
    bool empty() {
        return q1.empty() && q2.empty();
    }
    
private:
    queue<int> q1;
    queue<int> q2;
};