STL stack 与 queue 底层模拟实现及算法实战

关键细节说明

1. 默认成员函数：编译器会自动生成默认构造函数、析构函数等。由于 stack 本身不管理额外动态资源，所有操作都委托给 _con，自动生成的函数能正确调用底层容器的对应逻辑，无需手动编写。
2. const 引用返回：top() 返回 const T& 是为了避免不必要的拷贝开销，同时防止调用者通过引用修改栈顶元素，保证数据安全性。
3. 底层容器选择：虽然 vector 性能不错，但 deque 是默认选项，因为它在头部和尾部都能高效增删，更适合队列场景，而 Stack 主要用尾部，两者差异不大，但 deque 内存分配更灵活。

Queue 核心逻辑与实现

设计思路

Queue 是先进先出（FIFO）结构，元素从队尾进入，从队头离开。对底层容器的要求比 Stack 稍高，需要支持头部操作：

• 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 是最常用的底层容器，因为它在两端都能 O(1) 时间完成操作。如果使用 vector 作为 Queue 的底层容器，pop_front 会导致中间元素移动，性能下降至 O(N)，所以不建议。

经典算法场景实战

掌握原理后，我们来看几个典型应用场景，看看如何利用栈和队列的特性解决实际问题。

1. 最小栈 (Min Stack)

问题描述：设计一个支持 push、pop、top 以及获取当前栈中最小元素的栈，要求所有操作时间复杂度均为 O(1)。

思路分析： 维护两个栈：一个普通数据栈 _st 存储所有元素，另一个辅助栈 _minst 专门记录历史最小值。

• 当新元素入栈时，如果它小于等于 _minst 的栈顶（或 _minst 为空），则同步压入 _minst。
• 当元素出栈时，如果弹出的元素等于 _minst 的栈顶，说明当前最小值被移除了，需同步弹出 _minst。

代码实现：

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;   // 最小值栈
};

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 为空，将 push_st 中的所有元素依次弹出并压入 pop_st，此时 pop_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. 用队列实现栈

问题描述：仅使用两个队列实现栈的基本操作。

思路分析： 始终向非空队列中加入元素。出栈时，将非空队列的前 N-1 个元素依次移出并加入空队列，剩下的最后一个元素即为栈顶，将其弹出即可。

代码实现：

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

通过以上模拟实现与算法实践，希望能帮你更透彻地理解 STL 容器适配器的设计哲学，并在实际开发中灵活运用这些数据结构。