C++容器适配器之stack、queue、priority_queue

2401_87151858

830人浏览 · 2025-10-17 11:51:58

2401_87151858 · 2025-10-17 11:51:58 发布

stack

stack用法

栈是后进先出，它可以存放一系列数据，但向其中增删有一定的限制，只能尾插或尾删。为了严格控制数据，不支持迭代器或下标访问

void test_stack()
{
    stack<int> st1;
    st1.push(1);    // 插入元素1，即尾插1
    st1.push(2);
    st1.pop();      // 删除栈顶元素，即尾删
    st1.top();      // 返回栈顶，即最后一个元素
    st1.empty();    // 栈为空返回true, 否则返回false
    st1.size();     // 返回栈里元素的个数
}

stack模拟实现

我们发现栈所需的函数在vector中都能找到，例如push()对应push_back()、pop()对应pop_back()这样我们就可以把vector封装一下，只提供特定的函数就可实现栈。
注：模拟实现与其相关测试部分都用命名空间封装了一下，避免与库里的冲突

template<class T>
class stack
{
    vector<T> _v;		// 需要 #include<vector>
public:
    void push(const T& x) { _v.push_back(x); }
    void pop() { _v.pop_back(); }
    T& top() { return _v.back(); }
    bool empty() { return _v.empty(); }
    size_t size() { return _v.size(); }
};

但是栈所需的函数在list中也都能找到，底层要选什么容器呢？这里C++就提供了容器适配器的思想

// 模板参数也可以给缺省值,默认用vector容器
template<class T, class Container = vector<T>>	
class stack
{
    Container _con;
public:
    void push(const T& x) { _con.push_back(x); }
    void pop() { _con.pop_back(); }
    T& top() { return _con.back(); }
    bool empty() { return _con.empty(); }
    size_t size() { return _con.size(); }
};

测试一下

void test01()
{
    stack<int> st;  // 底层容器为vector
    for(int i = 0; i < 5; i++) st.push(i);
    while(!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();
    }
    cout << endl;
    
    stack<int, list<int>> st1;  // 底层容器为list
    for(int i = 0; i < 5; i++) st1.push(i * 10);
    while(!st1.empty())
    {
        cout << st1.top() << ' ';
        st1.pop();
    }
}

运行结果
在这里插入图片描述

但是STL的stack用的容器是deque
在这里插入图片描述

deque是双端队列，支持头插、头删、尾插、尾删，你可以认为它是vector与list的结合体，需要包含头文件：#include<deque>。用法如下：

void test02()
{
    deque<int> q;
    q.push_back(1);     // 尾插1  {1}
    q.push_back(2);     // 尾插2  {1,2}
    q.push_front(9);    // 头插9  {9,1,2}
    q.push_front(8);    // 头插8  {8,9,1,2}
    
    for(int i = 0; i < q.size(); i++)
        cout << q[i] << ' ';    // 支持下标访问, 但是效率不如vector
    cout << endl;

    cout << q.front() << endl;  // 访问队头，相当于q[0]
    cout << q.back() << endl;   // 访问队尾，相当于q[q.size() - 1]
    cout << q.empty() << endl;  // 为空返回true，否则返回false
    cout << q.size() << endl;   // 返回q里的元素个数
}

为什么STL的stack不用vector或者list做默认的底层容器呢？
deque底层是由一段段连续的小空间拼接而成的，类似于一个动态的二维数组。
1.发生扩容时，vector开销较大，deque开销适中；2.插入元素时，list容易产生内存碎片，而deque内存利用率更高。综合考虑后，deque更适合做stack的底层容器

queue

queue用法

队列是先进先出，它可以存放一系列数据，但向其中增删有一定的限制，只能尾插或头删。为了严格控制数据，不支持迭代器或下标访问

void test_queue()
{
    queue<int> q;
    q.push(1);    // 插入元素1，即尾插1
    q.push(2);
    q.pop();      // 删除队头元素，即头删
    cout << q.front() << endl;    // 返回队头元素
    cout << q.back() << endl;     // 返回队尾元素
    cout << q.empty() << endl;    // 队列为空返回true, 否则返回false
    cout << q.size() << endl;     // 返回队列里元素的个数
}

queue模拟实现

queue所需的尾插、头删在list与deque都能找到，任选一个将其封装成queue即可

// 这里默认用deque封装
template<class T, class Container = deque<T>>
class queue
{
    Container _con;
public:
    void push(const T& x) { _con.push_back(x); }
    void pop() { _con.pop_front(); }
    T& front() { return _con.front(); }
    T& back() { return _con.back(); }
    bool empty() { return _con.empty(); }
    size_t size() { return _con.size(); }
};

测试一下

void test03()
{
    queue<int> q1;  // 底层容器为deque
    for(int i = 0; i < 5; i++) q1.push(i);
    while(!q1.empty())
    {
        cout << q1.front() << ' ';
        q1.pop();
    }
    cout << endl;
    
    queue<int, list<int>> q2;  // 底层容器为list
    for(int i = 0; i < 5; i++) q2.push(i * 10);
    while(!q2.empty())
    {
        cout << q2.front() << ' ';
        q2.pop();
    }
}

运行结果
在这里插入图片描述

priority_queue

优先队列底层就是堆，堆顶元素就是整个堆的最值

priority_queue用法

void test_priority_queue()
{
    priority_queue<int> h1;     // 默认是大堆
    h1.push(1);    // 插入元素1
    h1.push(55);
    h1.push(9);
    h1.push(13);
    h1.push(28);
    cout << h1.top() << endl;      // 返回堆顶，由于是大堆，堆顶元素是55
    h1.pop();      // 删除堆顶元素
    h1.empty();    // 堆为空返回true, 否则返回false
    h1.size();     // 返回堆里元素的个数
    
    // 小堆写法：
    priority_queue<int, vector<int>, greater<int>> h2;  //第一个模板参数表示数据类型，第二个表示底层用vector容器实现，第三个是比较函数类型。
    // 这里刚好与sort相反。sort默认是升序，传入greater<int>()对象后是降序
}

测试

void test04()
{
    priority_queue<int> h1;     // 默认是大堆
    vector<int> v = { 5,3,1,7,9,4,6 };
    for(auto& e : v)
        h1.push(e);

    // 支持迭代器区间构造, 这样建堆时间复杂度O(n)。上面通过push建堆时间复杂度O(n*logn)
    priority_queue<int> hh1(v.begin(), v.end());

    while(!h1.empty())
    {
        cout << h1.top() << ' ';
        h1.pop();
    }
    cout << endl;

    priority_queue<int, vector<int>, greater<int>> h2;  // 小堆
    for(auto& e : v)
        h2.push(e);
    while(!h2.empty())
    {
        cout << h2.top() << ' ';
        h2.pop();
    }
}

运行结果
在这里插入图片描述

priority_queue模拟实现

在此之前需确保你已经大致了解堆，本篇结尾也提供了堆的一些内容点击直达

大致回顾一下插入删除操作：

插入元素：尾插，然后向上调整
删除堆顶：与最后一个元素交换，尾删，然后向下调整

下面将以大堆为例

template<class T, class Container = vector<T>>
class priority_queue
{
    Container _con;

    // 向上调整：如果这个节点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。
    void up(int i)
    {
        if(i == 0) return;
        int p = (i - 1) / 2; // p是i的父节点
        if(_con[i] > _con[p])	// 小堆需写成：if(_con[i] < _con[p])
        {
            swap(_con[i], _con[p]);
            up(p);
        }
    }

    // 向下调整：在该节点的儿子中，找一个权值最大的，若其权值大于该节点，则与该结点交换，否则直接停止。重复此过程直到叶子节点
    void down(int p)
    {
    	// 找权值最大的儿子节点
        int s = 2*p + 1;
        if(s >= _con.size()) return;
        if(s + 1 < _con.size() && _con[s + 1] > _con[s]) s++; // 小堆需将第二个条件改为:_con[s + 1] < _con[s]
        if(_con[s] > _con[p]) // 小堆需写成：if(_con[s] < _con[p])
        {
            swap(_con[s], _con[p]);
            down(s);
        }
    }
    // 可以发现，大堆与小堆无疑就是将 > 改为 <，本质就是换了个比较方式
public:
    priority_queue() = default;

    // 迭代器区间构造 -- 原地建堆
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
    {
        while(first != last) 
        {
            _con.push_back(*first);
            ++first;
        }
        // 从最后一个非叶子节点向下调整
        for(int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            down(i);
    }
    // 下面的写法时间复杂度O(n*logn), 上面的写法时间复杂度O(n)
    // priority_queue(Iterator first, Iterator last)
    // {
    //     while(first != last) 
    //         push(*first);
    // }
    
    // 插入：尾插，然后向上调整
    void push(const T& x)
    {
        _con.push_back(x);
        up(_con.size() - 1);
    }
    
    // 删除堆顶：与最后一个元素交换，删除最后一个元素，然后向下调整
    void pop()
    {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        down(0);
    }
    // 注意返回值是const T&, 而非T&。若更改了_con[0]那还需向下调整,但我们不知道何时会更改
    const T& top() const { return _con[0]; }
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }
};

那如果要实现小堆呢？再写一个类吗？为了更灵活，C语言通常用函数指针，C++一般用仿函数

仿函数

让对象能像函数那样使用

struct Test
{
	// operator()重载
    void operator()(string s) const
    {
        cout << s << endl;
    }
};

void test06()
{
    Test f;	// f是Test类的一个对象
    f("Hello");     // 输出：Hello
    // 相当于: f.operator()("Hello");
}

为此我们可以对象去比较大小

struct Less
{
    // a < b返回true，否则返回false
    bool operator()(int a, int b) const
    {
        return a < b;
    }
};
struct Greater
{
    // a > b返回true，否则返回false
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

void test07()
{
    Less le;
    Greater gr;
    int a = 10, b = 4;
    if(a < b) 
        cout << "a < b" << endl;
    if(le(a, b))  // 相当于le.operator()(a, b)
        cout << "a < b" << endl;

    if(a > b) 
        cout << "a > b" << endl;
    if(gr(a, b))  // 相当于gr.operator()(a, b)
        cout << "a > b" << endl;
}

能自定义大小堆的写法如下：

template<class T>
struct myless
{
    bool operator()(const T& a, const T& b) const
    {
        return a < b;
    }
};

template<class T>
struct mygreater
{
    bool operator()(const T& a, const T& b) const
    {
        return a > b;
    }
};

// 新增一个比较大小的模板参数
template<class T, class Container = vector<T>, class Compare = myless<T>>
class priority_queue
{
    Container _con;

    // 向上调整
    void up(int i)
    {
        if(i == 0) return;
        int p = (i - 1) / 2;
        Compare cmp;
        if(cmp(_con[p], _con[i])) // 只需改用仿函数比较_con[p]与_con[i]的大小即可
        {
            swap(_con[i], _con[p]);
            up(p);
        }
        
        // 下面的写法是用匿名对象
        // if(Compare()(_con[p], _con[i]))
        // {
        //     swap(_con[i], _con[p]);
        //     up(p);
        // }
    }

    // 向下调整
    void down(int p)
    {
        int s = 2*p + 1;
        if(s >= _con.size()) return;
        Compare cmp;
        if(s + 1 < _con.size() && cmp(_con[s], _con[s + 1])) s++;	// 改用仿函数去在比大小
        if(cmp(_con[p], _con[s])) // 改用仿函数去在比大小
        {
            swap(_con[s], _con[p]);
            down(s);
        }
    }
    
public:
// 下面的代码与之前写的一样

    priority_queue() = default;

    // 迭代器区间构造
    template<class Iterator>
    priority_queue(Iterator first, Iterator last)
    {
        while(first != last) 
        {
            _con.push_back(*first);
            ++first;
        }
        // 从最后一个非叶子节点向下调整
        for(int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            down(i);
    }

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

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

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

测试

void test06()
{
    priority_queue<int, vector<int>, mygreater<int>> h;
    priority_queue<int> h2;
    int a[10] = { 1,11,3,2,8,9,10,5,22,7 };
    for(auto e : a) 
    {
        h.push(e);
        h2.push(e);
    }

    while(!h.empty())
    {
        cout << h.top() << ' ';
        h.pop();
    }
    cout << endl;
    
    while(!h2.empty())
    {
        cout << h2.top() << ' ';
        h2.pop();
    }
}

运行结果
在这里插入图片描述

堆

用于找一组数据中的最值。堆的结构是完全二叉树，每个结点中存有一个元素（或者说是权值）

堆的性质：

大堆（大根堆）：父亲的权值 $\geqslant$ 儿子的权值。具体来说，对于任何一个节点i，假设i的左右儿子分别为left、right，则有i权值 $\geqslant$ left的权值并且 i权值 $\geqslant$ right的权值
小堆（小根堆）：父亲的权值 $\leqslant$ 儿子的权值

大堆示例图：

在这里插入图片描述

小堆示例图：
在这里插入图片描述

完全二叉树我们可以用数组实现，每个节点的下标就是其层序遍历对应的下标。（用数组实现可以很方便地插入元素）
在这里插入图片描述

假设下标从0开始，对于任何一个节点i：

它的父节点下标为(i-1)/2，（这里的除法就是C++里的除法，会下取整）
它的左儿子节点下标为2*i + 1
它的右儿子节点下标为2*i + 1 + 1

若设下标从1开始，对于任何一个节点i：

它的父节点下标为i/2，
它的左儿子节点下标为2*i，
它的右儿子节点下标为2*i + 1，

下面将以大堆为例
由堆性质，对于任意一颗子树，子树的根节点就是这颗子树中所有节点的最大值

过程

插入

堆中插入一个元素，要保证插入后也是一棵完全二叉树。最简单的方法就是：在最后一层的最右边的叶子之后插入。如果最后一层已满，就新增一层。用数组模拟就相当于尾插。例如在上述大堆示例图中插入20：
在这里插入图片描述

但是插入之后可能会不满足堆性质，我们需要进行调整

向上调整：如果这个节点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。
在这里插入图片描述

在这里插入图片描述

可以证明，经过向上调整后，所有节点都满足堆的性质

代码如下：

vector<int> a; // 数组模拟堆,下标从0开始

// 向上调整，i表示当前节点的下标
void up(int i)
{
    if(i == 0) return; // 到根节点了，停止
    int p = (i - 1) / 2;
    if(a[i] > a[p]) // 该节点权值 > 父节点，交换，然后继续向上调整
    {
        swap(a[i], a[p]);
        up(p);
    }
}

void push(int x)
{
    a.push_back(x);
    up(a.size() - 1);
}

删除

删除堆中最大的元素，即删除根结点。
由于数组中删除最后一个数很容易，我们可以将根节点与最后一个节点交换，然后再删除最后一个数。
在这里插入图片描述

在这里插入图片描述

但是新的根结点可能不满足堆性质，我们需要进行调整
向下调整：在该节点的儿子中，找一个权值最大的，若其权值大于该节点，则与该结点交换，否则直接停止。重复此过程直到叶子节点。

在这里插入图片描述

可以证明，经过向下调整后，所有节点都满足堆的性质

代码如下：

// 向下调整。下面所用到的a就是上文的vector<int> a;
void down(int p)
{
    // 找p的权值最大的儿子节点
    int s = 2*p + 1;
    if(s >= a.size()) return;   
    if(s + 1 < a.size() && a[s + 1] > a[s]) s++;

    // 权值最大的儿子节点的权值 > 父节点，交换，然后继续向下调整
    if(a[s] > a[p]) 
    {
        swap(a[s], a[p]);
        down(s);
    }
}

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

测试

vector<int> a; // 数组模拟堆
void up(int i)
{
    // 到根节点了，停止
    if(i == 0) return;
    int p = (i - 1) / 2;
    if(a[i] > a[p]) // 该节点权值 > 父节点，交换，然后继续向上调整
    {
        swap(a[i], a[p]);
        up(p);
    }
}

void push(int x)
{
    a.push_back(x);
    up(a.size() - 1);
}

void down(int p)
{
    // 找p的权值最大的儿子节点
    int s = 2*p + 1;
    if(s >= a.size()) return;   
    if(s + 1 < a.size() && a[s + 1] > a[s]) s++;

    // 权值最大的儿子节点的权值 > 父节点，交换，然后继续向下调整
    if(a[s] > a[p]) 
    {
        swap(a[s], a[p]);
        down(s);
    }
}

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

// 返回堆顶元素
int top() { return a[0]; }

int main()
{
    int arr[5] = { 5,2,8,1,4 };
    for(int i = 0; i < 5; i++)
        push(arr[i]);
    
    while(!a.empty())
    {
        cout << top() << ' ';
        pop();
    }
    return 0;
}

运行结果
在这里插入图片描述

原地建堆：从最后一个节点往前依次向下调整

int main()
{
    a = { 5,2,8,1,4 };
    for(int i = a.size() - 1; i >= 0; i--)
        down(i);
        
    // 也可以这样写，从最后一个非叶子节点往前依次向下调整
    // for(int i = (a.size() - 1 - 1) / 2; i >= 0; i--)
    //     down(i);
    
    while(!a.empty())
    {
        cout << top() << ' ';
        pop();
    }
    return 0;
}

总结一下：

插入元素：尾插，然后向上调整
删除堆顶：与最后一个元素交换，尾删，然后向下调整
原地建堆：从最后一个节点（或最后一个非叶子节点）往前依次向下调整

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责