C++容器适配器详解：stack、queue、deque与priority_queue

1. C++容器概览：从stack到priority_queue

在C++标准库中，容器是构建高效程序的基础工具。stack、queue、deque和priority_queue这四种容器适配器，虽然底层实现各不相同，但都提供了特定场景下的数据管理能力。作为C++开发者，我经常看到新手对这些容器的选择和使用存在困惑。比如有人用vector模拟栈操作，却不知道标准库已经提供了现成的stack；还有人为了实现优先级队列自己写堆结构，却忽略了priority_queue的存在。

这些容器适配器的本质是对基础序列容器的封装和功能限制。stack和queue限制访问顺序，priority_queue添加排序功能，而deque则是两者常用的底层实现。理解它们的特性和适用场景，能让我们写出更简洁、高效的代码。

2. stack：后进先出的数据结构

2.1 stack的核心特性

stack（栈）遵循LIFO（Last In First Out）原则，就像餐厅里叠放的盘子，总是取用最上面的那个。它的主要操作只有三个：

• push：将元素压入栈顶
• pop：移除栈顶元素
• top：访问栈顶元素

cpp复制#include <stack>
std::stack<int> s;
s.push(1);  // 栈：1
s.push(2);  // 栈：1 2
std::cout << s.top(); // 输出2
s.pop();    // 移除2

2.2 底层容器选择

stack默认使用deque作为底层容器，但也可以指定其他容器：

cpp复制std::stack<int, std::vector<int>> vec_stack;
std::stack<int, std::list<int>> list_stack;

选择依据：

• vector：连续内存，适合频繁访问但大小变化不大的场景
• list：元素分散存储，适合频繁插入删除
• deque（默认）：折中方案，支持快速首尾操作

注意：如果用vector作为底层容器，当栈增长时可能导致所有元素重新分配和拷贝

2.3 典型应用场景

• 函数调用栈：编译器自动管理
• 括号匹配：遇到左括号压栈，右括号弹栈匹配
• 撤销操作：将操作压栈，撤销时弹出
• 表达式求值：中缀转后缀表达式

3. queue：先进先出的队列

3.1 queue的基本操作

queue（队列）遵循FIFO（First In First Out）原则，就像排队买票，先来的人先得到服务。主要操作：

• push：元素加入队尾
• pop：移除队首元素
• front：访问队首元素
• back：访问队尾元素

cpp复制#include <queue>
std::queue<int> q;
q.push(1);  // 队列：1
q.push(2);  // 队列：1 2
std::cout << q.front(); // 输出1
q.pop();    // 移除1

3.2 底层实现选择

queue默认也使用deque作为底层容器，但可用list：

cpp复制std::queue<int, std::list<int>> list_queue;

不能使用vector