胖虎的工具箱-编程导航 胖虎的工具箱-编程导航

C++容器适配器深入解析：栈、队列、双端队列的底层及应用探索

未分类 2个月前 程序员胖胖胖虎阿
60 0 0

文章标题：

C++容器适配器深度剖析：栈、队列、双端队列的底层与应用探究

文章内容

文章目录

  • 前言
  • stack
    • 常用接口概览
    • stack的模拟实现
  • queue
    • 常见接口说明
    • queue的模拟实现
  • deque
    • 关键接口介绍
  • 容器适配器
  • priority_queue
    • 常用接口解读
    • priority_queue模拟实现
  • 反向迭代器的实现剖析
  • 仿函数（函数对象）
  • 作业板块
    • 逆波兰表达式引申
    • 拓展内容

前言

在C++标准库的宏大架构中，数据结构是构建高效编程的重要基础，而容器适配器、序列容器以及相关算法逻辑，是其中极具实用价值的核心组成部分。无论是日常开发还是算法刷题，栈（stack）、队列（queue）、优先级队列（priority_queue）这类“常客”频繁出现，它们看似简单的接口背后，暗藏着对数据存取规则的精妙设计——栈的“后进先出”适配递归调用、括号匹配等场景，队列的“先进先出”适配层序遍历、任务调度等需求，优先级队列通过堆结构实现带权重的数据筛选，成为解决TopK问题的有效手段。

深入探究这些结构时，我们会产生诸多疑问：为何栈和队列默认的底层容器是deque而非vector或list？deque的“分段连续”存储有何独特之处，能兼顾头尾操作效率与一定的随机访问能力？优先级队列中，仿函数（函数对象）如何灵活把控堆的排序逻辑？反向迭代器的设计又暗藏哪些技巧，能实现遍历方向反转却不影响底层数据结构？这些问题的答案，正是从“会用”迈向“精通”的关键所在。

本文不仅会系统梳理栈、队列、deque、优先级队列的核心接口与应用场景，还会通过完整的模拟实现代码，剖析容器适配器的封装逻辑——比如栈如何依托deque的尾插尾删实现“后进先出”，优先级队列怎样通过向上/向下调整算法维护堆结构。同时，针对仿函数、反向迭代器等易混淆概念，结合实例解析其原理与应用，助你厘清“less与greater的差别”“反向迭代器的++为何是底层迭代器的--”等细节。

理论结合实战更能巩固所学。文中选取力扣（如最小栈、二叉树层序遍历、数组第K大元素）和牛客网（如栈的压入弹出序列）的经典题目，不仅提供解题思路，还附上完整代码实现，让你在刷题过程中直观感受容器的妙用。此外，针对容器特性的选择题解析（如不同容器迭代器的失效问题、deque与vector的区别），可帮你规避学习中的常见误区。

无论你是初涉C++容器的新手，还是想夯实数据结构基础的进阶者，本文都能为你搭建一条从底层原理到实战应用的清晰路径。吃透这些知识，不仅能让你在面对复杂问题时快速找到数据结构选型的最优解，更能培养对代码逻辑的深层理解——毕竟，真正的编程能力，往往源于对“为何如此设计”的追问与探索。

stack

栈遵循后进先出的规则，需注意区分栈顶与栈底，栈顶是最后存入的元素。

常用接口概览

  • empty()：判断栈是否为空。
  • size()：获取栈中元素的个数。
  • top()：获取栈顶元素。
  • push(val)：向栈中压入元素。
  • pop()：弹出栈顶元素。

    需留意，栈没有迭代器，若访问空栈可能引发未定义行为。栈的构造示例：stack<int>st;

stack的模拟实现

namespace renshen
{
    template<class T, class Container = deque<T>>
    class stack
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_back();
        }

        T& top()
        {
            return _con.back();
        }

        size_t size()
        {
            return _con.size();
        }

        bool empty()
        {
            return _con.empty();
        }
    private:
        Container _con;
    };
    //补充:queue和stack库里面也有容器适配器
}

queue

队列遵循先进先出的规则。

常见接口说明

  • empty()：判断队列是否为空。
  • size()：获取队列中元素的个数。
  • front()：获取队列的队首元素。
  • back()：获取队列的队尾元素。
  • push(val)：向队列中插入元素。
  • pop()：弹出队列的队首元素。

    同样，队列没有迭代器。队列的构造示例：queue<int>a;

queue的模拟实现

namespace renshen
{
    template<class T, class Container = deque<T>>
    class queue
    {
    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();
        }

        size_t size()
        {
            return _con.size();
        }

        bool empty()
        {
            return _con.empty();
        }
    private:
        Container _con;
    };
    //引申:vector和list都有front和back
}

deque

对比vector：
1. deque极大缓解了扩容问题，且支持头插头删操作。
2. deque的[]操作效率较低，随机访问速度慢。
对比list：
1. deque支持下标随机访问。
2. deque的CPU高速缓存效率较好。
3. list在中间插入方面表现更优。
总结：deque适用于高频的头插头删、尾插尾删操作，同时有少量随机访问需求的场景。

deque的模拟实现采用中控指针数组（控制分散的区域，而非单个数据）。
在这里插入图片描述
当中控指针数组满时，进行扩容即可。
关于deque的[]模拟写法（如[i]）：
1. 首先判断是否在第一个数组范围内，若不在则减去第一个数组的元素个数，进而确定所在数组。

关键接口

begin、end、rbegin、rend、size、empty、resize、[]、front、back、erase、clear、push_front、push_back、pop_front、pop_back、insert

容器适配器

通常以container命名，使模板具备相应特性。

priority_queue

优先级队列实质是堆（堆顶为最上层元素）。
在这里插入图片描述
上述为类模板定义，默认是大堆。使用示例：priority_queue<int,vector<int>,greater<int>> pq
引申：需区分greater和greater()，前者是函数模板，后者是类模板。
在这里插入图片描述
此为构造函数的声明。
解决TopK问题时，堆排序较为高效，全排序时sort的时间复杂度为nlogn。

常用接口解读

  • empty()：判断优先级队列是否为空。
  • size()：获取优先级队列中元素的个数。
  • top()：获取优先级队列的堆顶元素。
  • push(val)：插入元素并自动排序。
  • pop()：弹出堆顶元素。

    优先级队列没有迭代器，遍历需逐个元素访问。

priority_queue模拟实现

namespace renshen
{
    template<class T, class Container = vector<T>, class Comapre = less<T>>
    class priority_queue
    {
    private:
        void AdjustDown(int parent)
        {
            Comapre 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 AdjustUp(int child)
        {
            Comapre com;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (com(_con[parent],_con[child]))
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else  break;
            }
        }


    public:
        priority_queue()
        {}

        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                _con.push_back(*first);
                ++first;
            }

            // 建堆
            for (int i = (_con.size()-1-1)/2; i >= 0; i--)
            {
                AdjustDown(i);
            }
        }

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

            AdjustDown(0);
        }

        void push(const T& x)
        {
            _con.push_back(x);

            AdjustUp(_con.size() - 1);
        }

        const T& top()
        {
            return _con[0];
        }

        bool empty()
        {
            return _con.empty();
        }

        size_t size()
        {
            return _con.size();
        }
    private:
        Container _con;
    };

反向迭代器的实现剖析

rbegin实际指向end位置，rend实际指向begin位置（需注意，rbegin并非最后一个有效元素的位置）。

namespace renshen
{
    template<class Iterator, class Ref, class Ptr>
    struct ReverseIterator
    {
        typedef ReverseIterator<Iterator, Ref, Ptr> Self;
        Iterator _it;

        ReverseIterator(Iterator it)
            :_it(it)
        {}

        Ref operator*()
        {
            Iterator tmp = _it;
            return *(--tmp);
        } // 反向迭代器解引用为前一个位置

        Ptr operator->()
        {
            return &(operator*());
        } // 编译器会自动利用返回的指针进行->操作

        Self& operator++()
        {
            --_it;
            return *this;
        }

        Self& operator--()
        {
            ++_it;
            return *this;
        }

        bool operator!=(const Self& s) const
        {
            return _it != s._it;
        }
    };
}

引申：重载运算符的结合性和优先级与原运算符一致。

仿函数（函数对象）

此类对象可像函数一样使用。示例：

template<class T>
class Less
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x < y;
    }
};
// 调用方式：
Less lesstest;
lesstest(1,2) 或 lesstest.operator()(1,2)

引申：标准库中的less用于升序，greater用于降序。

作业板块

力扣 155. 最小栈

思路：使用两个栈，一个用于存储数据，另一个用于存储最小值。当插入元素小于等于当前最小值栈顶时，将该元素压入最小值栈；弹出元素与最小值栈顶相同时，弹出最小值栈顶元素。

class MinStack {
public:
    void push(int val) {
        _st.push(val);
        if(_min.empty()||val<=_min.top())  _min.push(val);
    }

    void pop() {
        if(_st.top() == _min.top())   _min.pop();
        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _min.top();
    }
private:
    stack<int>_st;
    stack<int>_min;
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

牛客网 栈的弹出压入序列

思路：若栈顶元素与出栈序列元素不匹配，则压入数据；匹配则弹出数据。若全部压入后栈中仍有数据，说明序列不合法。

class Solution {
  public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st;
        int pushi = 0;
        int popi = 0;
        while (pushi <= pushV.size() - 1) {
            st.push(pushV[pushi++]);
            while (!st.empty() && st.top() == popV[popi]) {
                popi++;
                st.pop();
            }
        }

        return popi == pushi;
    }
};

力扣 102. 二叉树的层序遍历 & 107. 二叉树的层序遍历 II

    1. 二叉树的层序遍历

      思路：使用队列，注意处理根节点为空的情况。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>vv;
        queue<TreeNode*>q;  int levelsize = 0;
        if(root)
        {
            q.push(root); levelsize = 1;
        }

        while(!q.empty())
        {
            vector<int> v;
            for(int i = 1;i<=levelsize;i++)
            {
                TreeNode* j = q.front();  q.pop();
                v.push_back(j->val);
                if(j->left)  q.push(j->left);
                if(j->right)  q.push(j->right);
            }
            levelsize = q.size();
            vv.push_back(v);
        }

        return vv;
    }
};
    1. 二叉树的层序遍历 II

      思路：在上一题基础上，对结果进行反转。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>vv;
        queue<TreeNode*>q;  int levelsize = 0;
        if(root)
        {
            q.push(root); levelsize = 1;
        }

        while(!q.empty())
        {
            vector<int> v;
            for(int i = 1;i<=levelsize;i++)
            {
                TreeNode* j = q.front();  q.pop();
                v.push_back(j->val);
                if(j->left)  q.push(j->left);
                if(j->right)  q.push(j->right);
            }
            levelsize = q.size();
            vv.push_back(v);
        }

        reverse(vv.begin(),vv.end());
        return vv;
    }
};

[力扣 215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/

版权声明：程序员胖胖胖虎阿 发表于 2025年9月19日 下午7:35。
转载请注明：C++容器适配器深入解析：栈、队列、双端队列的底层及应用探索 | 胖虎的工具箱-编程导航

相关文章

SpringSecurity 自定义认证逻辑的两种方式(高级玩法)
程序员胖胖胖虎阿
370
Spring Cloud Config服务端配置细节(二)之加密解密
程序员胖胖胖虎阿
377
Javase-8.数组的练习
程序员胖胖胖虎阿
149
微服务架构之：Redis分布式锁
程序员胖胖胖虎阿
415
#yyds干货盘点#dart系列之:dart语言中的异常
程序员胖胖胖虎阿
340
突破桎梏！国产金仓数据库全面取代Oracle，迈向自主掌控
程序员胖胖胖虎阿
151

暂无评论

暂无评论...

JetBrains全家桶正版账号

官方正版 JetBrains 账号

登录即可使用全家桶 不限操作系统 官方授权 支持全家桶所有软件 不限版本
🔥 最低 32元/年
致力于称为最好的程序员导航网站

友链申请 免责声明 关于我们

Copyright © 2022  胖虎的工具箱-编程导航   陇ICP备2022001249号