C++中使用std::stack和std::queue适配器可高效实现栈和队列，二者默认以std::deque为底层容器，提供语义清晰、类型安全的接口，并支持替换底层容器以优化性能；在多线程环境下需通过互斥锁等机制确保线程安全。
在C++中，要实现队列（Queue）和栈（Stack）这两种基本的数据结构，最简洁、最符合现代C++实践的方式就是利用标准模板库（STL）中提供的适配器容器
std::queue
和
std::stack
。它们并不是全新的数据结构，而是将现有的序列容器（如
std::deque
、
std::list
或
std::vector
）封装起来，只暴露队列或栈特有的操作接口，从而保证了操作的语义正确性。
解决方案
使用
std::queue
和
std::stack
非常直观，它们默认都以
std::deque
（双端队列）作为底层容器，因为
std::deque
在两端插入和删除元素都非常高效。
实现栈 (Stack)
栈是一种“后进先出”（LIFO, Last In, First Out）的数据结构。
std::stack
提供了
push
（入栈）、
pop
（出栈）、
top
（查看栈顶元素）、
empty
（判断是否为空）和
size
（获取元素数量）等操作。
立即学习“C++免费学习笔记（深入）”；
#include #include // 包含stack头文件#include void demonstrateStack() { std::stack myStack; // 入栈操作 myStack.push("Apple"); myStack.push("Banana"); myStack.push("Cherry"); std::cout << "当前栈顶元素: " << myStack.top() << std::endl; // Cherry // 栈的大小 std::cout << "栈中元素数量: " << myStack.size() << std::endl; // 3 // 遍历并出栈 std::cout << "开始出栈: " << std::endl; while (!myStack.empty()) { std::cout << "弹出: " << myStack.top() << std::endl; myStack.pop(); } std::cout << "栈是否为空? " << (myStack.empty() ? "是" : "否") << std::endl; // 是}
实现队列 (Queue)
队列是一种“先进先出”（FIFO, First In, First Out）的数据结构。
std::queue
提供了
push
（入队）、
pop
（出队）、
front
（查看队头元素）、
back
（查看队尾元素）、
empty
（判断是否为空）和
size
（获取元素数量）等操作。
#include #include // 包含queue头文件#include void demonstrateQueue() { std::queue myQueue; // 入队操作 myQueue.push(10); myQueue.push(20); myQueue.push(30); std::cout << "当前队头元素: " << myQueue.front() << std::endl; // 10 std::cout << "当前队尾元素: " << myQueue.back() << std::endl; // 30 // 队列的大小 std::cout << "队列中元素数量: " << myQueue.size() << std::endl; // 3 // 遍历并出队 std::cout << "开始出队: " << std::endl; while (!myQueue.empty()) { std::cout << "出队: " << myQueue.front() << std::endl; myQueue.pop(); } std::cout << "队列是否为空? " << (myQueue.empty() ? "是" : "否") << std::endl; // 是}
将这两个示例代码放在
main
函数中调用，就能清晰地看到它们的工作方式。
为什么STL选择提供适配器容器，而不是直接使用序列容器？
这是一个很棒的问题，它触及了软件设计中的一个核心原则：接口与实现的分离。STL之所以提供
std::stack
和
std::queue
作为容器适配器，而不是直接让开发者去用
std::vector
或
std::list
模拟，主要有几个深层考量：
首先，语义清晰性。当你看到代码中使用了
std::stack
，你立刻就知道这个数据结构遵循LIFO原则，它的操作（push、pop、top）也严格限定在栈的语义范围内。如果直接用
std::vector
，虽然可以通过
push_back
和
pop_back
实现栈，但
std::vector
还提供了
operator[]
、
insert
、
erase
等大量不符合栈语义的操作。这会模糊代码意图，也可能导致误用，比如不小心从中间插入或删除元素，从而破坏了栈的结构。适配器强制了接口，确保了数据结构的行为符合其定义。
其次，类型安全和约束。适配器容器通过封装底层容器，只暴露了特定数据结构所需的操作。这是一种“最少知识原则”的应用。它降低了出错的可能性，因为你无法执行不属于栈或队列的操作。这在大型项目或团队协作中尤为重要，它为开发者提供了一个明确且受限的接口，减少了心智负担和潜在的bug。
再者，底层实现的可替换性。
std::stack
和
std::queue
允许你指定不同的底层序列容器（如
std::deque
、
std::list
、甚至
std::vector
——尽管
std::vector
作为
std::queue
的底层容器效率不高）。这意味着，如果未来你发现默认的
std::deque
在特定场景下性能不佳，你可以不改变上层逻辑（即栈或队列的操作语义），仅仅通过修改模板参数就能切换到底层容器，比如换成
std::list
。这种灵活性是直接使用单一序列容器无法比拟的。它将“我需要一个栈”和“这个栈应该如何高效地实现”这两个问题解耦了。
所以，与其说STL“没有直接使用”，不如说它提供了一个更高层次的抽象，让开发者能够以更清晰、更安全、更灵活的方式使用这些经典数据结构。这是一种设计上的优雅，它让我们的代码不仅能工作，而且能更好地表达意图。
自定义底层容器：如何选择最适合你的场景？
虽然
std::stack
和
std::queue
默认使用
std::deque
作为底层容器，但在某些特定场景下，我们可能需要根据性能特征来选择
std::list
或
std::vector
。理解它们的优缺点对于做出明智的选择至关重要。
1.
std::deque
(默认选择)
优点:
std::deque
（双端队列）在两端（头部和尾部）插入和删除元素都具有常数时间复杂度O(1)。这是因为
std::deque
在内部通常实现为一系列固定大小的块，这些块的指针存储在一个映射表中，使得它能高效地扩展。这对于栈（只在一端操作）和队列（两端操作）都是理想的。缺点: 相比
std::vector
，
std::deque
的元素不保证存储在连续的内存空间中，这可能导致缓存局部性稍差，在某些对缓存敏感的场景下性能略逊。随机访问（通过
operator[]
）虽然也是O(1)，但通常比
std::vector
慢一点。适用场景: 绝大多数情况下，
std::deque
都是
std::stack
和
std::queue
的最佳默认选择。如果你不确定，就用它。
2.
std::list
优点:
std::list
（双向链表）在任何位置插入和删除元素都具有常数时间复杂度O(1)，因为它只需要修改前后节点的指针。对于栈和队列，这意味着
push
和
pop
操作效率极高，且不会导致内存重新分配和元素拷贝（这是
std::vector
可能面临的问题）。缺点:
std::list
不支持随机访问（例如
operator[]
），访问元素需要O(n)的时间复杂度。每个元素都需要额外的内存来存储前后节点的指针，导致内存开销较大。缓存局部性极差，因为元素在内存中不连续。适用场景:栈: 如果你的栈需要存储大量元素，并且你非常关心每次
push
/
pop
操作的稳定常数时间性能，且内存重新分配的开销是不可接受的，
std::list
可能是一个选择。队列:
std::list
是实现队列的优秀选择，因为它在头部和尾部插入/删除都非常高效。如果你的队列元素数量变化频繁，且对内存分配和性能的稳定性有较高要求，可以考虑
std::list
。避免: 如果你需要频繁地查看队列或栈的中间元素，或者对内存使用有严格限制，
std::list
不是一个好选择。
3.
std::vector
优点:
std::vector
（动态数组）的元素存储在连续的内存空间中，具有极佳的缓存局部性，随机访问效率最高（O(1)）。缺点:作为栈的底层:
std::vector
作为栈的底层容器是高效的，因为
push_back
和
pop_back
（对应栈的
push
和
pop
）通常是O(1)摊销时间。但当容量不足时，
push_back
会导致内存重新分配和所有元素的拷贝，这会带来O(n)的开销。作为队列的底层:
std::vector
作为队列的底层容器效率很低。
push
操作（
push_back
）是高效的，但
pop
操作（从头部删除元素）需要移动所有后续元素，其时间复杂度为O(n)。这使得
std::vector
不适合作为
std::queue
的底层容器。适用场景:栈: 如果你对栈的内存连续性有要求（例如，为了更好的缓存性能），并且可以接受偶尔的O(n)重新分配开销，或者你知道栈的最大容量并能预先
reserve
，那么
std::vector
可以作为
std::stack
的底层容器。避免: 绝对不要将
std::vector
作为
std::queue
的底层容器，除非你的队列几乎从不执行
pop
操作。
如何指定底层容器：
#include #include #include // 用于作为底层容器#include // 用于作为底层容器#include // 默认，但也可以显式指定// 使用std::list作为底层容器的栈std::stack<int, std::list> myStackWithList;// 使用std::vector作为底层容器的栈// 注意：std::vector作为栈的底层，其push_back和pop_back操作是高效的std::stack<int, std::vector> myStackWithVector;// 使用std::list作为底层容器的队列std::queue<int, std::list> myQueueWithList;// 使用std::deque作为底层容器的队列（显式指定，与默认行为一致）std::queue<int, std::deque> myQueueWithDeque;
选择合适的底层容器，需要根据你的具体需求（性能、内存、操作模式）进行权衡。大多数时候，
std::deque
的平衡性使其成为默认的最佳选择，但了解其他选项能帮助你在特定瓶颈出现时进行优化。
在多线程环境中，STL队列和栈的线程安全问题及初步考量
当我们将STL的
std::queue
和
std::stack
引入多线程编程时，一个非常关键且必须严肃对待的问题就是线程安全性。简单来说，
std::queue
和
std::stack
本身并不是线程安全的。这意味着，如果多个线程同时对同一个队列或栈进行
push
、
pop
、
top
/
front
/
back
或
size
等操作，就可能发生数据竞争（data race），导致未定义行为。这包括但不限于数据损坏、程序崩溃、或者得到错误的结果。
为什么它们不是线程安全的？
STL容器的设计哲学是“提供高效且通用的数据结构，将线程安全留给用户去实现”。容器内部的操作，例如在
push
时修改内部指针、分配内存，或者在
pop
时更新状态，这些都不是原子操作。多个线程同时执行这些非原子操作时，它们的执行顺序是不可预测的，可能导致内部状态处于不一致的中间状态。
举个例子，一个线程正在
push
一个元素，它可能已经分配了内存并准备将数据写入，但还没来得及更新容器的大小或尾部指针。此时，另一个线程尝试
pop
，它可能读取到一个过时的大小，或者尝试访问一个尚未完全写入的元素，甚至访问到无效内存。
如何实现线程安全？
要让
std::queue
或
std::stack
在多线程环境下安全地工作，我们通常需要引入同步机制。最常见的方法是使用互斥锁（
std::mutex
）。
一个基本的线程安全队列或栈通常会是这样的：
#include #include #include // 对于阻塞队列/栈很有用#include // 用于异常处理// 示例：一个简单的线程安全队列template class ThreadSafeQueue {private: std::queue q; mutable std::mutex mtx; // mutable allows const methods to lock std::condition_variable cv; // 用于等待和通知public: void push(const T& value) { std::lock_guard lock(mtx); // 自动加锁解锁 q.push(value); cv.notify_one(); // 通知一个等待的线程有新数据了 } T pop() { std::unique_lock lock(mtx); // 允许在等待时解锁 // 等待直到队列不为空 cv.wait(lock, [this]{ return !q.empty(); }); T value = q.front(); q.pop(); return value; } bool try_pop(T& value) { // 非阻塞式pop std::lock_guard lock(mtx); if (q.empty()) { return false; } value = q.front(); q.pop(); return true; } bool empty() const { std::lock_guard lock(mtx); return q.empty(); } size_t size() const { std::lock_guard lock(mtx); return q.size(); }};// 线程安全栈的实现类似，只是操作接口不同
初步考量和注意事项：
互斥锁的粒度： 上述示例中，每个操作都加锁，这是最直接的实现方式。但如果操作非常频繁且锁竞争激烈，这可能成为性能瓶颈。在某些高级场景中，可能会考虑更细粒度的锁，或者无锁（lock-free）数据结构，但这会显著增加实现的复杂性。阻塞与非阻塞：
pop
操作可能需要等待队列中有元素。上面的
pop
方法是阻塞的（使用
std::condition_variable
），即如果没有元素，调用线程会等待直到有元素可用。你也可以提供一个非阻塞的
try_pop
方法，如果队列为空则立即返回一个指示（例如
false
）。异常安全： 确保在操作过程中抛出异常时，锁能够正确释放。
std::lock_guard
和
std::unique_lock
是RAII（Resource Acquisition Is Initialization）的典范，它们能够自动管理锁的生命周期，非常适合处理异常。
top()
/
front()
的陷阱： 如果一个线程调用
top()
或
front()
获取了栈顶/队头元素，但在它使用这个元素之前，另一个线程执行了
pop
操作，那么之前获取的元素可能已经失效，或者它所指向的内存已被释放或重用。因此，通常建议将
pop
和获取元素合并为一个操作，或者确保在获取元素后立即使用。我的
pop
示例就是返回了值，避免了这个问题。死锁风险： 如果你的线程安全容器与其他锁或资源交互，需要警惕死锁的风险。始终保持一致的加锁顺序，或者使用
std::lock
配合
std::adopt_lock
等高级技术。
在实际项目中，尤其是在高性能或高并发场景，直接手写一个完美无缺的线程安全容器是很有挑战的。通常，我们会倾向于使用成熟的并发库，例如Intel TBB (Threading Building Blocks) 中的
concurrent_queue
，或者Boost库中的并发容器，它们提供了经过充分测试和优化的线程安全数据结构。但理解其底层原理和如何使用
std::mutex
、
std::condition_variable
来构建，是掌握现代C++并发编程的基础。
以上就是C++如何使用STL容器实现队列和栈的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1476254.html
微信扫一扫 
支付宝扫一扫 
