std::stack和std::queue是适配器容器，基于底层容器（如deque、vector、list）提供受限接口，分别实现LIFO和FIFO语义，默认使用deque因其两端高效操作且缓存性能好。
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::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::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) 的。
优点：
缓存局部性好：
vector
的元素在内存中是连续存放的，这意味着访问相邻元素时，CPU 缓存的命中率会更高，这对于
top
操作或当栈中元素需要被连续处理时可能带来性能优势。内存利用率可能更高： 相较于
deque
或
list
，
vector
在不考虑扩容预留空间的情况下，每个元素占用的实际内存通常更紧凑。
缺点：
扩容开销： 如果栈的元素数量增长非常快，
vector
可能会频繁地进行内存重新分配和数据拷贝，这在某些对实时性要求极高的场景下需要注意。尽管是均摊 O(1)，但单次扩容的代价可能比较高。
何时考虑使用：
当你对栈的最大容量有较好的预估，或者希望预先分配好内存以避免运行时扩容开销时。当你非常看重缓存性能，且栈的
top
操作被频繁访问时。
一个简单的例子：
#include #include #include int main() { std::stack<int, std::vector> 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::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<std::string, std::list> 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实现原理的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1472396.html
微信扫一扫 
支付宝扫一扫 
