C++ STL深度剖析：Stack、queue、deque容器适配器核心接口

前引： 在C++标准模板库的体系架构中，栈(stack)与队列(queue)作为典型的容器适配器，通过封装底层序列容器实现了特定数据结构的抽象层。本文以C++17标准为基准，深入解析其模板参数推导机制、适配器模式下的接口约束，以及迭代器失效等关键技术细节。通过对比deque与list作为底层容器的性能差异，探讨如何根据应用场景选择最优实现策略。文章将结合操作系统任务调度、编译器语法分析等典型案例，展示如何通过STL接口实现线程安全的并发数据结构和高效内存管理方案！

目录

Stack

介绍

栈的实例化

检测stack是否为空

获取栈元素个数

获取栈顶元素

压栈

出栈

queue

介绍

队列的实例化

检测队列是否为空

获取队列元素个数

获取队头元素

获取队尾元素

入队列

出队头元素

deque

介绍

deque的实例化

检测deque是否为空

获取元素个数

获取第一个元素

获取最后一个元素

入deque

两端插入与删除元素

---

Stack

介绍

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中！

栈（Stack）：只允许在一端进行插入或者删除的线性表。栈只支持在一端进行插入和删除操作

栈顶（Top）：线性表允许进行插入和删除的那一端

栈底（Bottom）：固定的，不允许进行插入和删除的另一端

空栈：不含任何元素的空表

压栈（Push）：数据的插入也叫压栈（压栈、进栈、入栈都是一个意思）

例如：

在C++STL容器中，为我们提供了 Stack 的接口函数，与 list、Vector、string类似，直接实例化使用即可，下面我们来学习 Stack 的常用接口

栈的实例化

栈的元素支持内置类型（int、char、double......）也支持自定义类型，这里以 int 类型为例：

//实例化
stack<int> V;

遵循：stack<类型> 变量名

检测stack是否为空

如果是当前的栈为空返回非0；不为空返回0

V.empty()

获取栈元素个数

计算当前栈的元素个数，并返回

V.size();

获取栈顶元素

返回当前栈顶元素的引用

V。top();

压栈

将元素存进栈中

V.push(val);

出栈

弹出栈尾元素，注意没有返回值

V.pop();

queue

介绍

队列的满足先进先出（First-In-First-Out，FIFO），它可以在一端插入另一端删除，新元素被插入到队列的末尾（也就是队尾），元素只能在队列的前端（队首）被删除。队列由三个结构组成：

队头：允许删除的一端，又称队首

队尾：允许插入的一端（）

队列长度：即队列中的元素数量

队列的实例化

遵循：queue<类型> 变量名 

queue<int> V;

检测队列是否为空

队列为空返回 true；不为空返回 false

V.empty();

获取队列元素个数

V.size();

获取队头元素

队头就是尾端，出元素的那端，返回尾端元素的引用

V.front();

获取队尾元素

队尾就是头端，进元素的那端，返回头端元素的引用

V.back();

入队列

将元素插入到队列

V.push();

出队头元素

满足先进先出，将先进的元素出队列

V.pop();

deque

介绍

deque是一种动态数组。它可以在两端快速插入和删除元素，同时提供了接近常数时间的随机访问。与vector不同，deque不是将所有元素连续存储，而是将元素存储在一系列固定大小的数组中，并通过一个中央控制结构（通常是一个数组）来管理这些数组的指针

​分段连续存储​：deque内部由多个块组成，每个块是一个固定大小的数组（具体大小由实现定义）这些块在逻辑上连续，但物理内存中不一定连续

​中央控制结构（映射器）​​：一个指针数组（或其他结构），每个指针指向一个数据块。当需要增加新的块时，就在这个指针数组中添加新的指针。这个数组本身可以动态增长，通常从中间开始使用，以便两端扩展

随机访问​：虽然元素在物理上不连续，但可以通过计算快速定位到某个元素的位置。访问一个元素需要先确定它在哪个数据块中，然后在该数据块内索引。这个过程是常数时间复杂度

​双端高效操作​：在deque的首尾添加或删除元素非常高效，因为只需要修改中央控制数组的指针，并可能在需要时分配新的块

中间操作效率低​：在中间插入或删除元素需要移动元素，时间复杂度为O(n)

deque的实例化

//实例化
deque<int> V;

检测deque是否为空

为空返回 true；不为空返回 false

获取元素个数

V.size();

获取第一个元素

与 queue 的  front 访问特点很像 

V.front();

获取最后一个元素

与 queue 的  back 访问特点很像  

V。back();

入deque

V.push_back();

两端插入与删除元素

V.push_back(val);  //尾部插入元素
V.pop_back();       //尾部删除元素V.push_front(val); //头部插入元素
V.pop_front();      //头部删除元素

注意：也可以在中间插入/删除元素，不过很低效，一般不会使用