适配器容器怎么使用 stack和queue实现原理

P粉602998670

发布时间：2025-08-22 11:31:01

440人浏览过

来源于php中文网

原创

std::stack和std::queue是适配器容器，基于底层容器（如deque、vector、list）提供受限接口，分别实现LIFO和FIFO语义，默认使用deque因其两端高效操作且缓存性能好。

适配器容器怎么使用 stack和queue实现原理

std::stack

和

std::queue

并非独立的容器，它们是所谓的“适配器容器”。其核心在于将现有底层容器（如

std::deque

、

std::vector

或

std::list

）的功能，适配成特定的数据结构接口，也就是我们熟悉的栈（LIFO，后进先出）和队列（FIFO，先进先出）行为。它们自己并不存储数据，而是通过调用底层容器的特定方法来实现栈和队列的语义。

解决方案

理解适配器容器的关键在于它们提供了一个受限的接口，隐藏了底层容器的复杂性。这就像你拿到一个遥控器，你只关心按哪个按钮能换台，而不用管电视机内部复杂的电路板。

std::stack

的实现原理：

std::stack

默认使用

std::deque

作为其底层容器。它通过封装

deque

的

push_back()

实现

push

操作（将元素压入栈顶），通过

pop_back()

实现

pop

操作（从栈顶移除元素），以及通过

back()

实现

top

操作（查看栈顶元素）。这种设计巧妙地利用了

deque

两端高效插入/删除的特性，使得栈的 LIFO 行为得以高效模拟。当然，你也可以显式指定

std::vector

或

std::list

作为其底层容器。

std::queue

的实现原理：

std::queue

也默认使用

std::deque

作为其底层容器。它通过封装

deque

的

push_back()

实现

push

操作（将元素加入队列尾部），通过

pop_front()

实现

pop

操作（从队列头部移除元素），通过

front()

实现

front

操作（查看队列头部元素），以及通过

back()

实现

back

操作（查看队列尾部元素）。同样，

deque

在两端操作上的高效性，完美契合了队列 FIFO 的需求。

std::queue

也可以选择

std::list

作为底层容器，但通常不推荐使用

std::vector

，因为

vector

的

pop_front()

操作效率很低。

为什么标准库选择

std::deque

作为

std::stack

和

std::queue

的默认底层容器？

这其实是一个关于效率和通用性的权衡。在我看来，选择

std::deque

作为默认，是一个非常明智的决定。

std::deque

（双端队列）的特点是它能高效地在两端进行元素的添加和删除操作，这些操作通常是均摊 O(1) 的复杂度。对于

std::stack

来说，所有操作都集中在一端（栈顶），

deque

的

push_back

和

pop_back

完美匹配。而对于

std::queue

，它需要在头部删除（

pop_front

）和在尾部添加（

push_back

），这正是

deque

的拿手好戏。

如果换成

std::vector

，虽然它在尾部添加（

push_back

）和删除（

pop_back

）效率很高，但如果在头部删除（

pop_front

），就需要将所有后续元素向前移动，这会带来 O(N) 的时间复杂度，对于

std::queue

来说是不可接受的性能瓶颈。

std::list

（双向链表）虽然在任意位置插入和删除都是 O(1)，听起来很美，但它会带来更大的内存开销（每个节点需要额外的指针存储前后地址），而且由于内存不是连续分配的，其缓存局部性（cache locality）会比较差，这在实际运行中可能会导致性能不如

deque

。所以，

deque

就像一个平衡点，它既提供了两端操作的高效性，又比

list

有更好的缓存表现，是大多数场景下的“甜点”。

std::stack

使用

std::vector

作为底层容器有哪些考虑？

当然可以，而且在某些特定场景下，这可能是一个不错的选择。

当

std::stack

的底层容器是

std::vector

时，其

push

操作对应

vector::push_back

，

pop

操作对应

vector::pop_back

，

top

操作对应

vector::back

。这些操作对于

vector

来说都是非常高效的，尤其是

pop_back

和

back

都是 O(1)。

push_back

在

vector

容量不足时需要重新分配内存并拷贝，但这通常是均摊 O(1) 的。

优点：

SlidesAI

使用SlidesAI的AI在几秒钟内创建演示文稿幻灯片

下载

缓存局部性好：
```
vector
```
的元素在内存中是连续存放的，这意味着访问相邻元素时，CPU 缓存的命中率会更高，这对于
```
top
```
操作或当栈中元素需要被连续处理时可能带来性能优势。
内存利用率可能更高： 相较于
```
deque
```
或
```
list
```
，
```
vector
```
在不考虑扩容预留空间的情况下，每个元素占用的实际内存通常更紧凑。

缺点：

扩容开销： 如果栈的元素数量增长非常快，
```
vector
```
可能会频繁地进行内存重新分配和数据拷贝，这在某些对实时性要求极高的场景下需要注意。尽管是均摊 O(1)，但单次扩容的代价可能比较高。

何时考虑使用：

当你对栈的最大容量有较好的预估，或者希望预先分配好内存以避免运行时扩容开销时。
当你非常看重缓存性能，且栈的
```
top
```
操作被频繁访问时。

一个简单的例子：

#include 
#include 
#include 

int main() {
    std::stack> myVectorStack;
    myVectorStack.push(10);
    myVectorStack.push(20);
    std::cout << "Top of vector stack: " << myVectorStack.top() << std::endl;
    myVectorStack.pop();
    std::cout << "Size of vector stack: " << myVectorStack.size() << std::endl;
    return 0;
}

std::queue

可以使用

std::list

作为底层容器吗？它的优缺点是什么？

是的，

std::queue

完全可以使用

std::list

作为底层容器。实际上，这是

std::queue

除了

std::deque

之外的另一个标准支持的底层容器选项。

当

std::queue

的底层容器是

std::list

时，其

push

操作对应

list::push_back

，

pop

操作对应

list::pop_front

，

front

操作对应

list::front

，

back

操作对应

list::back

。由于

std::list

是一个双向链表，它在两端进行插入和删除操作的效率都是 O(1)。

优点：

真正的 O(1) 插入/删除：
```
list
```
的
```
push_back
```
和
```
pop_front
```
操作始终是 O(1)，不会像
```
vector
```
那样有潜在的扩容开销，也不会像
```
deque
```
那样有分块管理带来的微小开销。
无内存重新分配： 元素插入或删除不会导致现有元素的内存地址改变，这对于一些需要稳定指针/迭代器的场景可能有用（尽管对于适配器容器来说，你通常不会直接操作底层迭代器）。
灵活的内存使用： 元素可以分散在内存的任何位置，不需要连续的内存块。

缺点：

内存开销大：
```
list
```
的每个节点除了存储数据，还需要存储指向前一个和后一个节点的指针。这意味着每个元素会比
```
vector
```
或
```
deque
```
占用更多的内存。
缓存局部性差： 由于元素在内存中不连续，CPU 缓存的命中率会较低。这在处理大量数据时，可能会导致性能劣于
```
deque
```
或
```
vector
```
。
遍历效率低： 虽然
```
queue
```
不直接提供遍历接口，但如果底层容器需要支持遍历，
```
list
```
的遍历效率不如连续内存的容器。

何时考虑使用：

当你对队列的元素数量完全无法预估，且希望避免任何形式的内存重新分配或拷贝开销时。
当单个元素的内存开销和缓存性能不是瓶颈，而更看重操作的严格 O(1) 保证时。
在一些内存碎片化问题比较严重的嵌入式系统或特定环境中，
```
list
```
的内存分配模式可能更具优势。

一个简单的例子：

#include 
#include 
#include 

int main() {
    std::queue> myListQueue;
    myListQueue.push("First");
    myListQueue.push("Second");
    std::cout << "Front of list queue: " << myListQueue.front() << std::endl;
    myListQueue.pop();
    std::cout << "Back of list queue: " << myListQueue.back() << std::endl;
    return 0;
}

如何用C++实现一个ECS（实体组件系统）？C++游戏引擎架构模式【游戏开发】

C++如何实现一个简单的A*寻路算法_C++游戏AI开发中的路径规划实战

C++如何实现一个简单的行为树_C++游戏AI中决策逻辑的行为树实现

c++ 矩阵乘法代码 c++矩阵运算实现教程

c++怎么使用ONNX Runtime来运行一个AI模型_C++与ONNX Runtime集成运行AI模型实践

相关专题

treenode的用法

在计算机编程领域，TreeNode是一种常见的数据结构，通常用于构建树形结构。在不同的编程语言中，TreeNode可能有不同的实现方式和用法，通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

529

2023.12.01

C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化，涵盖排序算法（快速排序、归并排序）、查找算法、图算法、动态规划、贪心算法等，并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构（链表、树、堆、哈希表等），帮助开发者提升在复杂应用中的算法设计与性能优化能力。

2025.12.22

硬盘接口类型介绍

硬盘接口类型有IDE、SATA、SCSI、Fibre Channel、USB、eSATA、mSATA、PCIe等等。详细介绍：1、IDE接口是一种并行接口，主要用于连接硬盘和光驱等设备，它主要有两种类型：ATA和ATAPI，IDE接口已经逐渐被SATA接口；2、SATA接口是一种串行接口，相较于IDE接口，它具有更高的传输速度、更低的功耗和更小的体积；3、SCSI接口等等。

989

2023.10.19

PHP接口编写教程

本专题整合了PHP接口编写教程，阅读专题下面的文章了解更多详细内容。

2025.10.17

php8.4实现接口限流的教程

PHP8.4本身不内置限流功能，需借助Redis（令牌桶）或Swoole（漏桶）实现；文件锁因I/O瓶颈、无跨机共享、秒级精度等缺陷不适用高并发场景。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

195

2025.12.29

堆和栈的区别

堆和栈的区别：1、内存分配方式不同；2、大小不同；3、数据访问方式不同；4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容，供大家免费下载体验。

366

2023.07.18

堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

559

2023.08.10

linux是嵌入式系统吗

linux是嵌入式系统，是一种用途广泛的系统软件，其特点是：1、linux系统是完全开放、免费的；2、linux操作系统的显著优势是多用户和多任务，保证了多个用户使用互不影响；3、设备是独立的，只要安装驱动程序，任何用户都可以对任意设备进行使用和操作。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

170

2024.02.23