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::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) 的。
优点：
-
缓存局部性好：
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;
} 
