C++ STL Stack、Queue、Deque 容器适配器接口详解

V.front();

获取队尾元素

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

V.back();

入队列

将元素插入到队列

V.push(val);

出队头元素

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

V.pop();

deque

介绍

dque 是一种动态数组。它可以在两端快速插入和删除元素，同时提供了接近常数时间的随机访问。与 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(val);

两端插入与删除元素

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

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