STL 容器适配器 stack 与 queue 底层模拟及算法实战

容器适配器概述

STL 中的 stack 和 queue 本质是容器适配器，它们基于基础容器封装实现特定操作逻辑。理解它们的底层机制，有助于我们更好地掌握 STL 设计思想。

什么是容器适配器？

适配器可以理解为'转换器'，它能把原本不兼容的对象改造为可以直接使用的形式。容器适配器专门用来包装底层容器（例如 deque、vector），通过屏蔽复杂接口，只暴露栈、队列等特定数据结构的核心操作。

为什么不支持迭代器？

容器适配器的核心目标是限制访问范围：

• stack：仅允许操作栈顶（LIFO），若暴露迭代器，用户就能遍历所有元素，破坏设计意图。
• queue：仅允许操作队首/队尾（FIFO），迭代器会打破两端操作的限制。
• priority_queue：仅允许操作优先级最高的元素，底层存储顺序并非优先级顺序，遍历无意义。

因此，迭代器这种'通用遍历'工具与适配器'限制访问'的目标相悖，二者天生不兼容。

Stack 详解

核心概念

Stack 是一种后进先出（LIFO）的容器适配器。元素的插入和提取只能在容器的一端进行，通常将底层容器的尾部当作栈顶。

它对底层容器的要求包括：empty、back、push_back、pop_back。默认情况下使用 deque，但 vector 和 list 也符合要求。

模拟实现

namespace bit {
template<class T, class Container = std::deque<T>>
class stack {
public:
    // 压栈：将 x 插入栈顶
    void push(const T& x) { _con.push_back(x); }
    
    // 出栈：删除栈顶元素
    void pop() { _con.pop_back(); }
    
    // 获取栈顶元素：返回 const 引用避免拷贝
    const T& top() { return _con.back(); }
    
    // 判断是否为空
    bool empty() { return _con.empty(); }
    
    // 获取元素个数
    size_t size() { return _con.size(); }

private:
    Container _con; // 底层容器，实际存储数据
};
}

这里的 _con 是实际的存储对象，所有操作都委托给它。关于默认成员函数，编译器会自动生成构造、析构等函数，它们会调用底层容器的对应方法，所以无需手动编写。

Queue 详解

核心概念

Queue 是先进先出（FIFO）的容器适配器。元素从队尾入列，从队头出列。

底层容器需支持：empty、size、front、back、push_back、pop_front。默认同样使用 deque。

模拟实现

namespace bit {
template<class T, class Container = std::deque<T>>
class queue {
public:
    // 入队：插入到尾部
    void push(const T& x) { _con.push_back(x); }
    
    // 出队：删除头部元素
    void pop() { _con.pop_front(); }
    
    // 获取队头元素
    const T& front() { return _con.front(); }
    
    // 获取队尾元素
    const T& back() { return _con.back(); }
    
    // 判空
    bool empty() { return _con.empty(); }
    
    // 获取大小
    size_t size() { return _con.size(); }

private:
    Container _con;
};
}

注意 pop() 不返回值，这是为了符合标准库规范，避免误用。

算法实战

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.top() == _st.top()) {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() { return _st.top(); }
    int getMin() { return _minst.top(); }

private:
    std::stack<int> _st;
    std::stack<int> _minst;
};

2. 栈的压入、弹出序列

思路：模拟入栈出栈过程。依次将元素压入栈，若栈顶与出栈数组待匹配元素一致，则弹出并移动指针。最终栈为空即合法。

class Solution {
public:
    bool IsPopOrder(std::vector<int>& pushV, std::vector<int>& popV) {
        std::stack<int> st;
        int pushi = 0, popi = 0;
        while (pushi < pushV.size()) {
            st.push(pushV[pushi++]);
            while (!st.empty() && st.top() == popV[popi]) {
                st.pop();
                popi++;
            }
        }
        return st.empty();
    }
};

3. 逆波兰表达式求值

思路：遇到数字入栈，遇到运算符则弹出两个数运算后将结果压回栈。

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::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(std::stoi(e));
            }
        }
        return st.top();
    }
};

4. 用栈实现队列

思路：双栈法。一个栈负责入队 (push_st)，一个栈负责出队 (pop_st)。当 pop_st 为空时，将 push_st 全部倒入 pop_st，此时 pop_st 栈顶即为队头。

class MyQueue {
public:
    void push(int x) { push_st.push(x); }
    
    int pop() {
        if (pop_st.empty()) {
            while (!push_st.empty()) {
                pop_st.push(push_st.top());
                push_st.pop();
            }
        }
        if (pop_st.empty()) return 0;
        int top = pop_st.top();
        pop_st.pop();
        return top;
    }
    
    int peek() {
        if (pop_st.empty()) {
            while (!push_st.empty()) {
                pop_st.push(push_st.top());
                push_st.pop();
            }
        }
        if (pop_st.empty()) return 0;
        return pop_st.top();
    }
    
    bool empty() { return push_st.empty() && pop_st.empty(); }

private:
    std::stack<int> push_st;
    std::stack<int> pop_st;
};

5. 用队列实现栈

思路：始终向非空队列加入元素。出栈时将非空队列的前 n-1 个元素导入空队列，剩下的最后一个即为栈顶。

class MyStack {
public:
    void push(int x) {
        if (!q1.empty()) q1.push(x);
        else q2.push(x);
    }
    
    int pop() {
        if (q1.empty()) {
            while (q2.size() > 1) {
                q1.push(q2.front());
                q2.pop();
            }
            int ret = q2.front();
            q2.pop();
            return ret;
        } else {
            while (q1.size() > 1) {
                q2.push(q1.front());
                q1.pop();
            }
            int ret = q1.front();
            q1.pop();
            return ret;
        }
    }
    
    int top() {
        if (!q1.empty()) return q1.back();
        if (!q2.empty()) return q2.back();
        return 0;
    }
    
    bool empty() { return q1.empty() && q2.empty(); }

private:
    std::queue<int> q1;
    std::queue<int> q2;
};