C++ 标准库容器适配器：stack、queue 与 priority_queue

优化思考： 如果插入大量重复的最小值怎么办？可以定义结构体记录值和计数，减少空间占用。

栈的压入、弹出序列

判断一个序列是否是另一个序列的合法弹出顺序。

#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        size_t pushi = 0, popi = 0;
        stack<int> st;
        while (pushi < pushV.size()) {
            st.push(pushV[pushi++]);
            // 当栈顶匹配弹出序列时，持续出栈
            while (!st.empty() && popV[popi] == st.top()) {
                popi++;
                st.pop();
            }
        }
        return st.empty();
    }
};

逆波兰表达式求值

遇到操作数入栈，遇到操作符则弹出两个数运算后重新入栈。

#include <stack>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                int right = s.top(); s.pop();
                int left = s.top(); s.pop();
                switch (str[0]) {
                    case '+': s.push(left + right); break;
                    case '-': s.push(left - right); break;
                    case '*': s.push(left * right); break;
                    case '/': s.push(left / right); break;
                }
            } else {
                s.push(stoi(str));
            }
        }
        return s.top();
    }
};

4. 模拟实现

#include <deque>
template<class T, class Container = std::deque<T>>
class stack {
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_back(); }
    T& top() { return _con.back(); }
    size_t size() { return _con.size(); }
    bool empty() { return _con.empty(); }
private:
    Container _con;
};

二、Queue（队列）

1. 核心概念

队列是先进先出（FIFO）结构。元素从队尾入列，从队头出列。底层默认使用 deque，也可用 list。

2. 常用接口

3. 模拟实现

注意：vector 不支持高效的头删，所以不能用 vector 作为底层。

#include <list>
template<class T, class Container = std::list<T>>
class queue {
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_front(); }
    T& front() { return _con.front(); }
    T& back() { return _con.back(); }
    size_t size() { return _con.size(); }
    bool empty() { return _con.empty(); }
private:
    Container _con;
};

三、Priority Queue（优先队列）

1. 核心概念

优先队列根据排序标准，第一个元素总是最大（默认大堆）。底层默认使用 vector 并配合堆算法维护结构。

2. 常用接口

• top(): 获取堆顶元素（最大/最小）
• push(x): 插入元素
• pop(): 删除堆顶元素

注意： 默认是大堆。若要小堆，需传入仿函数 greater<T>。

3. 实战案例：数组中的第 K 个最大元素

利用优先队列的特性，将元素全部放入，弹出 K-1 次即可得到第 K 大元素。

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> p(nums.begin(), nums.end());
        while (--k) {
            p.pop();
        }
        return p.top();
    }
};

4. 模拟实现（堆调整算法）

需要实现向上调整（AdjustUp）和向下调整（AdjustDown）来维护堆性质。

#include <vector>
#include <algorithm>
using namespace std;

namespace myPriorityQueue {
    template<class T>
    struct less {
        bool operator()(const T& x, const T& y) const {
            return x < y;
        }
    };
    
    template<class T>
    struct greater {
        bool operator()(const T& x, const T& y) const {
            return x > y;
        }
    };

    template<class T, class Container = std::vector<T>, class Compare = greater<T>>
    class priority_queue {
    public:
        void AdjustUp(int child) {
            int parent = (child - 1) / 2;
            while (child > 0) {
                Compare com;
                if (com(_con[parent], _con[child])) {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (parent - 1) / 2;
                } else {
                    break;
                }
            }
        }

        void AdjustDown(int parent) {
            int child = parent * 2 + 1;
            while (child < _con.size()) {
                // 选出左右孩子中较大的那个
                if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
                    ++child;
                }
                Compare com;
                if (com(_con[parent], _con[child])) {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                } else {
                    break;
                }
            }
        }

        void push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }

        void pop() {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }

        bool empty() { return _con.empty(); }
        const T& top() { return _con[0]; }
        size_t size() { return _con.size(); }

    private:
        Container _con;
    };
}

四、容器适配器原理

适配器模式是将一个类的接口转换成客户希望的另一个接口。STL 中的 stack 和 queue 并不直接管理内存，而是包装了底层容器。

五、Deque（双端队列）

1. 为什么选它做默认底层？

deque 是分段连续的逻辑连续空间。相比 vector，它在头部插入删除无需搬移元素；相比 list，它的空间利用率更高且支持随机访问。

2. 优缺点

• 优势：头尾操作效率高，扩容时不需要像 vector 那样大规模搬移数据。
• 缺陷：遍历效率略低，因为迭代器需要频繁检测是否跨越了小段空间的边界。

在实际开发中，若需要线性结构且涉及频繁的头尾操作，deque 往往是比 vector 更优的选择，这也是 STL 将其设为 stack 和 queue 默认底层的根本原因。