C++ 标准库容器适配器：Stack、Queue 与 Priority Queue 详解

优化方案： 如果插入大量重复数据，可以使用结构体记录值和计数，减少空间占用。

栈的压入、弹出序列

给定两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

思路：

1. 准备一个辅助栈和一个指向弹出序列的指针。
2. 遍历压入序列，依次入栈。
3. 每次入栈后，检查栈顶元素是否与弹出序列当前指针指向的元素相同。若相同，则出栈并移动指针。
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();
    }
};

逆波兰表达式求值

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

思路：

1. 遇到操作数则入栈。
2. 遇到操作符，取栈顶两个数进行运算，结果继续入栈。

代码实现：

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

1.3 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 的介绍和使用

2.1 queue 的介绍

queue（队列）是一种先进先出（FIFO）的数据结构。元素从队尾入队列，从队头出队列。底层容器可以是 deque 或 list，默认使用 deque。

2.2 queue 的使用

2.3 queue 的模拟实现

由于需要支持头删，不能使用 vector。

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 的介绍和使用

3.1 priority_queue 的介绍

优先队列是一种容器适配器，它的第一个元素总是它所包含的元素中最大的。底层容器通常是 vector 或 deque，默认使用 vector。需要支持随机访问迭代器，以便内部维护堆结构。

3.2 priority_queue 的使用

优先级队列默认是大堆。如果需要小堆，可以通过仿函数来实现。

3.3 在算法中的应用

例如查找数组中的第 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();
    }
};

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

加上仿函数版本： 为了更灵活地控制大小堆关系，引入仿函数比较器。

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);
        }
    }
    // ... 同上 AdjustUp, AdjustDown, push, pop 等逻辑，仅比较处使用 com(...)
    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;
};
}

四. 容器适配器

4.1 什么是适配器

适配器是一种设计模式，将一个类的接口转换成客户希望的另外一个接口。STL 中的 stack 和 queue 并非真正的容器，而是对底层容器的接口进行了包装。

4.2 STL 标准库中 stack 和 queue 的底层结构

虽然 stack 和 queue 可以存放元素，但在 STL 中将其称为容器适配器。它们默认使用 deque 作为底层容器。

五. deque 的介绍

5.1 deque 的原理介绍

double ended queue（双端队列）可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。与 vector 相比，头插效率高；与 list 相比，空间利用率较高。

deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，类似于动态二维数组。为了维护其'整体连续'以及随机访问的假象，迭代器的设计比较复杂。

5.2 deque 的缺陷

与 vector 比较，deque 的优势是头部插入和删除不需要搬移元素，扩容也不需要搬移大量数据。与 list 比较，其底层是连续空间，空间利用率比较高。 但是，deque 不适合遍历，因为在遍历时，迭代器要频繁检测是否移动到某段小空间的边界，导致效率低下。因此实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list。

5.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器

1. stack 和 queue 不需要遍历，只需要在固定的一端或者两端进行操作。
2. 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。