STL 容器适配器 Stack 与 Queue 的实现与题型应用

这里有几个容易忽略的点

默认成员函数不用特地写出来。stack 自己不管资源，真正的数据都在 _con 里，编译器自动生成的构造、析构这些函数就够用了。

top() 返回 const T& 也比较合理，少一次拷贝，外部还改不了栈顶值。这个接口设计很朴素，但挺实用。

底层容器默认选 deque，不是因为 vector 不行，而是 deque 在头尾两端扩展都比较顺手。对 stack 来说只用尾部，差别不算大，但 STL 统一默认 deque，一般跟着这个选就行。

Queue 的核心逻辑和实现

设计思路

queue 是先进先出结构，元素从队尾进，从队头出。它比 stack 多一个头部操作要求，因此底层容器得能支持 front() 和 pop_front()。

• front()：获取队头元素
• pop_front()：删除队头元素
• 其他接口与 stack 类似，比如 back()、push_back()、empty()、size()

代码实现

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;
    };
}

这里默认还是 deque。这不是随便拍脑袋定的，原因很简单：deque 两端操作都能做到比较稳定的 O(1)。如果你硬把 vector 当 queue 的底层容器，pop_front() 就会触发元素整体搬移，性能会掉到 O(N)，这类实现一般没必要。

经典题型：把栈和队列用起来

理解结构本身不难，真正拉开差距的是你能不能在题目里迅速认出它的影子。下面这些题都很典型，套路也很稳定。

1. 最小栈 Min Stack

题目要求维护 push、pop、top 和 getMin()，而且都要是 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:
    std::stack<int> _st;      // 数据栈
    std::stack<int> _minst;   // 最小值栈
};

这个题的关键不在技巧，而在于你愿不愿意多维护一点状态。多一个栈，换来所有操作 O(1)，这笔账很划算。

2. 栈的压入、弹出序列

题目给两个数组，一个是入栈序列，一个是出栈序列，判断后者是不是合法出栈顺序。

做法就是老老实实模拟。按顺序把入栈序列压入辅助栈，每压一次就看看栈顶是不是已经匹配上当前要出栈的元素。能弹就一直弹，直到对不上为止。最后栈空了，说明顺序合法。

class Solution {
public:
    bool IsPopOrder(std::vector<int>& pushV, std::vector<int>& popV) {
        std::stack<int> st;
        int pushi = 0, popi = 0;
        int n = pushV.size();

        while (pushi < n) {
            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、pop、peek 和 empty。

思路很经典：一个栈负责进数据，另一个栈负责出数据。入队时直接压到 push_st；出队时如果 pop_st 为空，就把 push_st 的元素全部倒过去，这样顺序就翻过来了，pop_st 栈顶正好是队头。

class MyQueue {
public:
    MyQueue() {}

    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. 用队列实现栈

反过来，用两个队列做一个栈。

做法也直白：始终往非空队列里塞数据。需要 pop 的时候，把非空队列前面的元素一个个挪到另一个空队列里，直到只剩最后一个，这个就是栈顶，直接弹掉即可。

class MyStack {
public:
    MyStack() {}

    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();
        else if (!q2.empty()) return q2.back();
        return 0;
    }

    bool empty() {
        return q1.empty() && q2.empty();
    }

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

这里的代价很明确：push 很便宜，pop 会贵一些。和上一个题正好相反。实现时不用追求花哨，保证行为正确就够了。

收个尾

stack 和 queue 看上去接口很少，但它们把'访问边界'这件事做得很干净。适配器的价值也在这里：不是给你更多能力，而是替你把不该做的事挡掉。理解了这一层，再去看这些题，基本就是在做接口约束下的状态模拟。