C++ 深入理解 stack、queue 及 priority_queue 实现原理

优化思考： 如果在插入大量重复的最小值时，minst 会占用额外空间。可以定义一个结构体，包含 val 和 count，记录该值的出现次数，从而减少重复存储。

4. 实战案例：栈的压入、弹出序列

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

思路： 模拟入栈过程。遍历压栈数组，依次入栈；每次入栈后检查栈顶是否等于当前期望弹出的元素，若相等则出栈并移动弹出指针。最后检查栈是否为空。

代码实现：

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

5. 实战案例：逆波兰表达式求值

利用栈处理后缀表达式（逆波兰表达式），遇到数字入栈，遇到运算符则弹出两个数字进行计算。

代码实现：

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

6. Stack 模拟实现

了解其本质有助于调试和优化。stack 本质上是对底层容器的包装。

template<class T, class Continer = std::deque<T>>
class stack {
public:
    stack() {}
    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:
    Continer _con;
};

二、Queue：先进先出

1. Queue 介绍

queue 是 FIFO（先进先出）结构。元素从队尾入队列，从队头出队列。底层容器可以是 deque 或 list，默认为 deque。

2. Queue 常用接口

3. Queue 模拟实现

由于需要支持头删，vector 不适用（头删效率低），通常选择 list 或 deque。

template<class T, class Continer = std::list<T>>
class queue {
public:
    queue() {}
    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:
    Continer _con;
};

三、Priority Queue：优先队列

1. Priority Queue 介绍

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（默认大堆）。底层容器通常是 vector，通过堆算法维持堆结构。

2. Priority Queue 使用

默认情况下，priority_queue 是大堆。如果需要小堆，可以通过仿函数（Functor）来定制比较逻辑。

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

利用优先队列可以在 O(N log K) 时间内找到第 K 大元素，比完全排序更高效。

思路： 将数组放入优先级队列，弹出 k-1 次后，剩下的栈顶即为第 K 大元素。

代码实现：

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. Priority Queue 模拟实现

这里展示了基于 vector 的手动堆实现，包括向上调整（AdjustUp）和向下调整（AdjustDown）。

基础版（大堆）：

namespace myPriorityQueue {
template<class T, class Container = std::vector<T>>
class priority_queue {
public:
    void AdjustUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (_con[child] > _con[parent]) {
                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;
            }
            if (_con[child] > _con[parent]) {
                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;
};
}

支持仿函数版本（可配置大小堆）： 通过引入 Compare 模板参数，可以灵活控制堆的性质。例如传入 greater<T> 即可实现小堆。

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:
    priority_queue() = default;

    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last) : _con(first, last) {
        for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
            AdjustDown(i);
        }
    }

    void AdjustUp(int child) {
        Compare com;
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (com(_con[parent], _con[child])) {
                swap(_con[child], _con[parent]);
                child = parent;
                parent = (parent - 1) / 2;
            } else {
                break;
            }
        }
    }

    void AdjustDown(int parent) {
        Compare com;
        int child = parent * 2 + 1;
        while (child < _con.size()) {
            if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
                ++child;
            }
            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;
};
}

四、容器适配器与 Deque

1. 什么是适配器

适配器模式将一个类的接口转换成客户希望的另外一个接口。在 STL 中，stack 和 queue 就是典型的容器适配器，它们不直接管理内存，而是包装其他容器。

2. 为什么选择 Deque 作为默认底层容器

deque（双端队列）是一种分段连续的空间数据结构。它在头部和尾部插入删除都是 O(1)，且扩容时不需要像 vector 那样搬移大量数据。

• 对比 Vector：deque 头插效率高，无需搬移元素。
• 对比 List：deque 空间利用率更高，没有额外的节点指针开销。

虽然 deque 遍历时迭代器较复杂（需检测段边界），但 stack 和 queue 本身不需要遍历，因此 deque 成为了它们的最佳默认搭档。

掌握这些底层原理，能帮助我们在实际开发中更合理地选择数据结构，提升程序性能。