​c++:stack、queue、priority_queu增删查改模拟实现、deque底层原理

Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。

一· C++stack简介使用和模拟实现

1.1stack简介

参考文档：stack的文档介绍

在我的主页中的算法与数据结构中讲过stack(栈)的实现有两种方式底层是数组和底层式链式结构，其实是哪种结构都可以，只要我们能保证是先进后出(同一端进出数据)下标进行访问即可，在主页种我使用数组作为底层是因为两种方式数组作为底层效率相对更高。下面我们来看一看库中的stack：

​

​

从图中可以看出stack使用的默认适配器是dque(双端队列)【下面会讲解deque】，从栈的接口支持的操作可以看出前面我们讲过的stl中的vector，list都支持相关操作，所以我们后续可以对其进行封装，只有保证数据先进后出即可。

1.2stack的增删查改模拟实现

​

这里我们可以将底层容器定义成模板，然后将容器定义成成员变量进行封装(保证先进后出)。在实现stack相应接口时，通过成员变量调用底层容器接口(这就是容器适配器，将容器作为底层复用）

二C++queue的介绍使用和模拟实现

2.1queue简介使用

参考文档：queue文档介绍

2.2queue增删查改的模拟实现

从上图可以看出queue的底层容器也是deque，由于queue是先进先出(一端人数据一端出数据)，所以其底层容器要支持尾插和头删。因为vtctor不直接支持对于头部的删除，所以这里不将vector作为queue的底层容器(库种也不支持)，如果硬要将vector作为queue的底层容器，此时就也使用vector中的erase接口来实现头部的删除，效率很低。

三 容器适配器

3.1概念：

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设

计经验的总结，一开始有23种现在不止)，该种模式是将一个类的接口转换成客户希望的另外一个接口。例如古代打仗以前看人数，后面人们经验多了(孙子兵法)不只是看人数，还要看带队将领。

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

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为

容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认

使用deque，比如：

3.3deque的简单了解(了解不是很重要)

3.3.1deque讲解

deque(双端队列),不要看名字是队列，其实它不是队列，是一个指针数组，更像是stack和queue的结合。它是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

要注意 deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组 ，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问

的假象，落在了deque的迭代器身上， 因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

3.3.2deque不同位置的插入数据

3.3.2.1尾插

3.3.2.2头插（很容易出错和你想象的不一样)

3.3.2.3中间位置插入数据

3.4deque的优缺点(缺陷)

这里就要和vector和list比较

vector

优点： 支持下标随机访问。 cpu高速缓存命中率高(了解):参考文档：cpu缓存相关问题(非常经典建议收藏) 缺点： 在头部或中部删除效率低下(因为要挪动数据） 扩容有优点成本，存在一定浪费(因为扩容一般是成倍扩大，二插入数据可能没有插入扩容个数多）

list

优点： 任意位置可以O（1）插入删除，不需要挪动数据。 不存在扩容，按需申请释放，不浪费空间。 缺点： 不支持下标随机访问。 cpu高速缓存命中率低(了解)

deque

与vector比较，deque的优势是：头部操作效率很高(不需要挪动数据）,其扩容时，也不需要搬移大量的元素，因此其效率是必vector高的，但是这方面与list相比又没有做到极致提升。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段，但是这方面与vector相比又没有做到极致提升。所以deque更像vector和list的结合，但是又没有做到对与两者优点的极致提升(有点和我们所说的四不像类似，毕竟既想要这个又想要那个很难)。 但是， deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下 ，而序列式场景中，可能需要经常遍历，因此 在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性

结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据

结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如

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

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进

行操作。

1. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的

元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

四 priority_queue的简介使用和模拟实现

4.1priority_queue介绍

参考文档：priority_queue的文档介绍

priority_queue(优先级队列，顾名思义按照优先级进行，而把什么当作优先级自己可以定)默认使用vector作为其底层容器，所以我们在插入/删除数据时都要调整结构保证其是一个堆结构(引入相关算法)。注意：库中默认情况是大堆，由于实际需求可能不一样，要建小堆此时就有更改仿函数(这就是仿函数的作用)，库中默认仿函数(<）是建大堆，这也是库中的一个缺陷(大堆即降序一个>）

4.2priority_queue增删查改的模拟实现

由于我们在插入/删除数据时都要调整结构保证其是一个堆结构，所以要引入相关算法：向上调整算法/向下调整算法，这些算法都是堆的相关只是不懂参考：【数据结构与算法】顺序结构与链式结构（非常经典)

前言

由于优先级队列是一种容器，所以我们可以使用模板将其作为成员变量，在根据实际传入的容器生成实例化出具体版本，由于建大/小堆我们是不知道的，所以我们在其算法中定义仿函数变量，调用仿函数控制行为来满足不同需求。

五 全部代码

本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好理解C++相关知识 ，觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识，我们下期再见。