C++ STL 容器适配器详解：Stack、Queue、Priority Queue 原理与实战

【栈的压入弹出序列】

基本思路

模拟入栈和出栈的过程。遍历压入序列，将元素压入辅助栈，然后检查栈顶是否与弹出序列当前元素匹配。如果匹配则弹出，直到不匹配或栈为空。

代码实现

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        size_t pushi = 0, popi = 0;
        stack<int> st;
        while (pushi < pushV.size()) {
            // 1. 首先将一个数据 push 进栈
            st.push(pushV[pushi++]);
            
            // 2. 是否匹配
            // 2.1 匹配——栈顶数据和 popi 指向的数据相等并且栈不为空，出栈顶数据，popi++
            while (!st.empty() && st.top() == popV[popi]) {
                st.pop();
                popi++; // 这里出数据可能会出现栈为空的情况，栈为空时就继续入栈
            }
            // 2.2 不匹配——继续将 pushV 数据入栈
        }
        
        // 当栈最后为空或者 popi 走到最后，指向最后一个数据的下一个位置时则为正常序列
        return popi == popV.size();
    }
};

【逆波兰表达式求值】

基本原理

遇到操作数就入栈，遇到操作符就弹出两个操作数进行计算，结果再入栈。

代码实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto& str : tokens) {
            // 为操作符
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                if (str == "+") {
                    st.push(left + right);
                } else if (str == "-") {
                    st.push(left - right);
                } else if (str == "*") {
                    st.push(left * right);
                } else {
                    st.push(left / right);
                }
            }
            // 为操作数
            else {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

1.4 stack 的模拟实现

从接口可以看出，栈实际是一种特殊的线性结构。使用 vector 完全可以模拟实现 stack。用 list 也可以，取决于你传入的 Container 支持哪些接口。

#pragma once
#include <iostream>
#include <vector>
#include <list>
#include <deque>
using namespace std;

namespace lrq {
    template<class T, class Container = deque<T>> // 这里可以给一个缺省值
    class stack {
    public:
        void push(const T& x) {
            _con.push_back(x);
        }
        void pop() {
            _con.pop_back();
        }
        size_t size() const {
            return _con.size();
        }
        bool empty() const {
            return _con.empty();
        }
        const T& top() const {
            return _con.back();
        }
    private:
        Container _con;
    };
}

二、queue 的介绍和使用

2.1 queue 简介

队列（Queue）是一种先进先出（FIFO）的容器适配器。元素从队尾入队列，从队头出队列。底层容器可以是标准容器类模板之一（如 deque、list），默认情况下使用 deque。

该底层容器应至少支持以下操作：

• empty()：检测队列是否为空
• size()：返回队列中有效元素的个数
• front()：返回队头元素的引用
• back()：返回队尾元素的引用
• push_back()：在队列尾部入队列
• pop_front()：在队列头部出队列

2.2 queue 的使用

2.3 queue 的模拟实现

注意：queue 不可以使用 vector 作为底层来实现，因为 vector 不支持头删（pop_front）操作。

#pragma once
namespace lrq {
    template<class T, class Container = deque<T>>
    class queue {
    public:
        void push(const T& x) {
            _con.push_back(x);
        }
        void pop() {
            _con.pop_front();
        }
        size_t size() const {
            return _con.size();
        }
        const T& front() const {
            return _con.front();
        }
        bool empty() const {
            return _con.empty();
        }
    private:
        Container _con;
    };
}

三、priority_queue 的介绍和使用

3.1 priority_queue 简介

优先队列（Priority Queue）是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素。

底层容器可以是任何标准容器类模板（如 vector、deque）。默认情况下，如果没有指定容器类，则使用 vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。

3.2 priority_queue 的使用

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将元素构造成堆的结构。注意：默认情况下 priority_queue 是大堆。

#include <iostream>
#include <queue> // priority_queue 和 queue 共用一个头文件
using namespace std;

int main() {
    // 默认是大的优先级高
    // priority_queue<int> pq;
    
    // 显示传参数，这里涉及到仿函数，使用 greater<int> 小的优先级高
    priority_queue<int, vector<int>, greater<int>> pq;
    
    pq.push(1);
    pq.push(10);
    pq.push(90);
    pq.push(4);
    
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

3.3 在 OJ 题中的应用

【数组中的第 K 个最大元素】

使用优先级队列解决真是再适合不过了！

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 使用优先级队列，底层就是一个大堆
        priority_queue<int> pq(nums.begin(), nums.end());
        
        // k-- 是出 k 次，也就是循环 k 次；--k 是出 k-1 次，也就是进入循环 k 次
        while (--k) {
            pq.pop();
        }
        return pq.top();
    }
};

3.4 priority_queue 的模拟实现

通过对 priority_queue 的底层结构就是堆，因此此处只需对堆进行通用的封装即可。

数据结构关于二叉树的忘了真得复习了，不然下面看起来费劲。

#pragma once
#include <vector>
namespace bit {
    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 = vector<T>, class Compare = less<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 push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }
        
        void AdjustDown(int parent) {
            Compare com;
            size_t 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 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 什么是适配器

适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。

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

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器。这是因为 stack 和队列只是对其他容器的接口进行了包装。STL 中 stack 和 queue 默认使用 deque。

4.3 deque 的简单介绍

【deque 的原理介绍】

double-ended queue（双端队列）：是一种双开口的"连续"空间的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

deqque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组。

【deque 的缺陷】

与 vector 比较，deque 的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率比 vector 高。

与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque 有一个致命缺陷：不适合遍历。因为在遍历时，deque 的迭代器要频繁地去检测其是否移动到某段小空间的边界，导致效率低下。因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。

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

stack 是一种后进先出的特殊线性数据结构，只要具有 push_back() 和 pop_back() 操作的线性结构都可以作为底层容器，比如 vector 和 list。

queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构都可以作为底层容器，比如 list。

但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：

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

结合了 deque 的优点，而完美避开了其缺陷。

下面是本节课对 STL 库里面实现的 stack 和 queue 进行测试以及对 vector 和 deque 排序效率的测试。

#include <stack.h>
#include <queue.h>
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;

void test_op1() {
    srand(time(0));
    const int N = 1000000;
    deque<int> dq;
    vector<int> v;
    for (int i = 0; i < N; ++i) {
        auto e = rand() + i;
        v.push_back(e);
        dq.push_back(e);
    }
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    int begin2 = clock();
    sort(dq.begin(), dq.end());
    int end2 = clock();
    printf("vector:%d\n", end1 - begin1);
    printf("deque:%d\n", end2 - begin2);
}

void test_op2() {
    srand(time(0));
    const int N = 1000000;
    deque<int> dq1;
    deque<int> dq2;
    for (int i = 0; i < N; ++i) {
        auto e = rand() + i;
        dq1.push_back(e);
        dq2.push_back(e);
    }
    int begin1 = clock();
    sort(dq1.begin(), dq1.end());
    int end1 = clock();
    int begin2 = clock();
    // 拷贝到 vector
    vector<int> v(dq2.begin(), dq2.end());
    sort(v.begin(), v.end());
    dq2.assign(v.begin(), v.end());
    int end2 = clock();
    printf("deque sort:%d\n", end1 - begin1);
    printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}

int main() {
    //test_op1();
    test_op2();
    return 0;
}

同样的排序，vector 比 deque 要快。这验证了之前提到的 deque 遍历效率低下的问题。