C++ 中的栈、队列与优先队列：从使用到模拟实现

如果存在大量重复元素，可以用结构体或 pair 记录值和计数来优化空间。

栈的压入、弹出序列
输入两个整数序列，第一个是压栈顺序，判断第二个是否为合法的弹出顺序。

思路：用一个辅助栈模拟。遍历压入序列，依次入栈，每次入栈后检查栈顶是否等于弹出序列的当前指针值，若相等则连续弹出并移动指针。最后栈空说明合法。

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

逆波兰表达式求值
遇到操作数入栈，遇到操作符时，取出栈顶两个数运算，结果再入栈。对于操作符判断，用 switch 处理四种情况。

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

stack 的模拟实现

核心就是包装一个底层容器，只暴露需要的接口。标准库默认用 deque，但用 vector 也可以。

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）

队列是先进先出（FIFO）的结构，队尾进，队头出。底层容器可以用 deque 或 list，默认是 deque。包含 <queue>。

模拟实现时要注意，因为需要从队头删除元素，所以底层不能是 vector（没有 pop_front），最好用 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）

优先队列不同于普通队列，它保证队头元素始终是最大值（默认大顶堆）。底层一般用 vector，因为需要随机访问来维护堆结构。

应用：数组中的第 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();
    }
};

priority_queue 的模拟实现

核心就是建堆和调整。以下是默认大堆的手动实现，包含了向上调整和向下调整。

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> 使得行为与标准库默认的大顶堆一致（这里示例中默认 Compare 设为 greater，实际标准库默认是 less，不过我们实现时可以自由定义）。

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

容器适配器 —— 为什么它们是 adapter？

stack 和 queue 本身不存储元素，而是对底层容器进行包装，将接口适配成 LIFO 或 FIFO 的行为。这种设计模式就叫适配器（adapter）。标准库中，它们默认使用 deque 作为底层容器。

deque 简介

deque（双端队列）支持头尾 O(1) 插入删除，空间利用率比 list 好，比 vector 头插效率高。但它不是一整块连续内存，而是由多个固定大小的块拼接而成，迭代器在遍历时需要检查是否到达块边界，所以遍历效率差。

因此，在需要大量遍历的场景，vector 和 list 更合适；而 stack 和 queue 只在一端操作，不需要遍历，deque 作为底层既能高效扩容，又不造成大的内存碎片，自然成了默认选择。

deque 也有一些明显缺陷：迭代器的实现复杂，频繁的块切换会带来额外开销。除非你需要双端操作且关注内存使用，否则一般优先考虑 vector 或 list 即可。

注：文中 stack、queue、priority_queue 的模拟实现仅用于理解底层原理，实际开发中直接使用标准库即可。