适配器容器怎么使用 stack和queue实现原理-C++-PHP中文网

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

P粉602998670

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

原创

435人浏览过

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) 的。

优点：

琅琅配音

全能AI配音神器

208

查看详情

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

缺点：

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

何时考虑使用：

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

一个简单的例子：

#include <stack>
#include <vector>
#include <iostream>

int main() {
    std::stack<int, std::vector<int>> 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 <queue>
#include <list>
#include <iostream>

int main() {
    std::queue<std::string, std::list<std::string>> 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;
}

登录后复制

以上就是适配器容器怎么使用 stack和queue实现原理的详细内容，更多请关注php中文网其它相关文章！