17370845950

C++中stack、queue和priority_queue是STL容器适配器，基于deque等底层容器封装，仅支持受限访问：stack为LIFO，仅top()/push()/pop()；queue为FIFO，有front()/back()；priority_queue为最大堆，默认top()返回最值。

在 C++ 中，stack 和 queue 是标准模板库（STL）提供的容器适配器，它们不直接存储数据，而是基于底层容器（如 deque 或 vector）封装出特定的访问接口。用法简单但需注意其“受限访问”特性——不能随机访问、不能遍历（除非手动弹出）、不支持迭代器遍历（stack/queue 本身无 begin()/end()）。

stack 基本操作与常用方法

stack 是后进先出（LIFO）结构，只允许在栈顶插入和删除。

• 定义方式：默认底层为 deque，也可指定 vector 或 list：
  stack s; 或 stack> s;
• 核心操作：
  s.push(x) —— 压入元素
  s.pop() —— 移除栈顶（不返回值）
  s.top() —— 返回栈顶引用（使用前必须非空）
  s.empty() —— 判空（推荐代替 s.size() == 0）
  s.size() —— 元素个数
• 注意事项：
  没有 front()/back()，只有 top()；
  不能用下标或迭代器访问；
  若需遍历，只能不断 pop 并暂存，或改用 vector + 手动模拟。

queue 基本操作与常用方法

queue 是先进先出（FIFO）结构，只允许队尾入、队首出。

• 定义方式：默认底层也是 deque，可显式指定：
  queue q; 或 queue> q;
• 核心操作：
  q.push(x) —— 入队（队尾）
  q.pop() —— 出队（队首，不返回值）
  q.front() —— 访问队首元素
  q.back() —— 访问队尾元素（仅 queue 有，stack 没有）
  q.empty() / q.size() —— 同 stack
• 常见误用提醒：
  q.front() 和 q.back() 返回的是引用，修改会影响队列内容；
  不要对空队列调用 front() 或 back()，行为未定义；
  仍不支持迭代器遍历，如需遍历建议用 vector + 下标或改用 deque。

priority_queue：带优先级的“伪队列”

虽名为 queue，但实际是最大堆（默认），属于堆结构，不是 FIFO 队列。常用于 Top-K、贪心算法等场景。

• 基本用法：
  priority_queue pq; —— 大根堆（默认）
  priority_queue, greater> pq; —— 小根堆
• 支持的操作：
  pq.push(x), pq.pop(), pq.top()（堆顶，即最值）,pq.empty(), pq.size()
  注意：没有 front()/back()，只有 top()
• 自定义比较：可传入仿函数或 lambda（C++11+），例如按字符串长度排序：
  priority_queue, [](const string&a,const string&b){return a.size() pq;

实用技巧与避坑指南

真正写题或工程时，几个高频细节决定是否写出健壮代码：

• 判空再取值：所有 .top()、.front()、.back() 调用前务必检查 empty()，尤其在 while 循环中；
• 不要依赖 size() 判断逻辑：某些场景（如多线程）size 可能不及时更新，判空更安全；
• 想遍历？换容器：若需要遍历、查找、中间插入，stack/queue 不适合，直接用 vector、deque 或 list；
• 性能考虑：默认底层 deque 对头尾操作都是 O(1)，比 vector 更适合作为适配器基础；若明确只从一端操作且内存连续重要，可指定 vector，但 push_back 可能触发扩容。