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

这里 _con 是底层容器对象，实际存储所有元素。stack 的所有操作都是通过封装这个容器的接口实现的。

关键接口说明：

• push(const T& x)：调用底层容器的 push_back，把元素插入到栈顶。
• pop()：调用 pop_back，删除栈顶元素。
• top()：返回 back()，即栈顶元素的 const 引用，避免拷贝且防止外部修改。
• empty()：返回容器的判空结果。
• size()：返回容器的元素个数。

为什么不用提供默认成员函数？ 编译器会自动生成默认成员函数（构造、拷贝、赋值、析构），这些函数会调用底层容器的对应函数，能完整实现初始化、拷贝和资源释放。stack 自身不管理额外动态资源，依赖底层容器即可。

queue 介绍

queue 是先进先出（FIFO）上下文中的容器适配器。元素从队尾入队列，从队头出队列。默认底层容器也是 deque。

对底层容器的要求包括：empty、size、front、back、push_back、pop_front。

queue 模拟实现

namespace bit {
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 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;
};
}

同样，_con 是底层容器对象，体现适配器的封装思想。

算法题实战

最小栈

题目要求设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

思路是用一个数据栈存储所有入栈元素，另一个最小值栈同步维护对应阶段的栈内最小值。入栈时仅当新元素小于等于最小值栈顶（或最小值栈为空）时，才将其压入最小值栈；出栈时若弹出的元素是当前最小值，则同步弹出最小值栈顶。

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:
    stack<int> _st;
    stack<int> _minst;
};

栈的压入、弹出序列

验证两个整数序列是否是同一个栈的压入、弹出顺序。

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

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++]);
            while (!st.empty() && st.top() == popV[popi]) {
                st.pop();
                popi++;
            }
        }
        return st.empty();
    }
};

逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

遇到数字直接入栈，遇到运算符则弹出栈顶两个元素进行运算，结果再入栈。注意减法和除法要注意操作数顺序。

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

用栈实现队列

使用两个栈来实现队列功能。一个栈负责入队（push_st），一个栈负责出队（pop_st）。

入队直接压入 push_st。出队时，若 pop_st 为空，则将 push_st 中的所有元素倒序转移到 pop_st 中，此时 pop_st 的栈顶即为队列队头。这样利用两个栈的反转特性实现了 FIFO。

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) {
        push_st.push(x);
    }
    
    int pop() {
        if (pop_st.empty()) {
            while (!push_st.empty()) {
                int top = push_st.top();
                push_st.pop();
                pop_st.push(top);
            }
        }
        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()) {
                int top = push_st.top();
                push_st.pop();
                pop_st.push(top);
            }
        }
        if (pop_st.empty()) return 0;
        return pop_st.top();
    }
    
    bool empty() {
        return push_st.empty() && pop_st.empty();
    }

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

用队列实现栈

使用两个队列实现栈功能。始终向非空的队列中加入元素，保证新元素在队列尾部，最终成为栈顶。

pop 操作时，将非空队列的元素（除了最后一个）全部倒入空队列，剩下的最后一个元素就是栈顶，直接弹出即可。这利用了队列的 FIFO 特性来模拟栈的 LIFO 行为。

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) {
                int front = q2.front();
                q2.pop();
                q1.push(front);
            }
            int ret = q2.front();
            q2.pop();
            return ret;
        } else {
            while (q1.size() > 1) {
                int front = q1.front();
                q1.pop();
                q2.push(front);
            }
            int ret = q1.front();
            q1.pop();
            return ret;
        }
    }
    
    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;
};