下面是一份吃透 C++ STL 栈与队列的完整指南：涵盖用法、底层结构、模拟实现、优先队列对比与技巧 ✅
（适合作为学习笔记收藏）
✅ 栈与队列概念回顾
| 容器 | 特点 | 允许操作 | 遵循原则 |
|---|---|---|---|
stack | 后进先出 | push/pop/top | LIFO |
queue | 先进先出 | push/pop/front/back | FIFO |
priority_queue | 堆结构 | push/pop/top | 最大/最小堆优先 |
✅ 只能在一端进行更改的 stack，与两端操作受限的 queue 都属于 container adapters（适配器）
✅ stack 用法总结
#include <stack>
stack<int> st;
st.push(10);
st.push(20);
cout << st.top() << endl; // 20
st.pop();
cout << st.size() << endl;
cout << (st.empty() ? "empty" : "not empty");
底层实现
默认底层：deque
可手动指定：
stack<int, vector<int>> st2;
✅ 特点：扩容时不会整体拷贝（deque）
✅ queue 用法总结
#include <queue>
queue<int> q;
q.push(1);
q.push(2);
cout << q.front() << endl; // 1
cout << q.back() << endl; // 2
q.pop();
底层实现
默认底层：deque
queue<int, list<int>> q2;
✅ 特点：头删 O(1)
✅ priority_queue 用法总结
#include <queue>
priority_queue<int> pq; // 默认最大堆
pq.push(3);
pq.push(10);
pq.push(1);
cout << pq.top(); // 10 (最大)
pq.pop();
构造最小堆 ✅
priority_queue<int, vector<int>, greater<int>> minpq;
自定义结构排序
struct Node {
int val, w;
bool operator < (const Node& rhs) const {
return w < rhs.w; // 大顶堆
}
};
priority_queue<Node> pq;
或使用比较器
struct CMP {
bool operator() (Node a, Node b) {
return a.w > b.w; // 最小堆
}
};
priority_queue<Node, vector<Node>, CMP> pq;
✅ Top → 优先级最高元素
✅ stack/queue/priority_queue 时间复杂度对比
| 操作 | stack | queue | priority_queue |
|---|---|---|---|
| push/pop | O(1) | O(1) | O(log n) |
| top/front/back | O(1) | O(1) | O(1) |
| 是否顺序遍历 | ❌ | ❌ | ❌ |
✅ STL 模拟实现核心思想
✅ stack 模拟
template<class T>
class MyStack {
private:
vector<T> v;
public:
void push(T x){ v.push_back(x); }
void pop(){ v.pop_back(); }
T top(){ return v.back(); }
bool empty(){ return v.empty(); }
};
✅ queue 模拟
template<class T>
class MyQueue {
private:
deque<T> dq;
public:
void push(T x){ dq.push_back(x); }
void pop(){ dq.pop_front(); }
T front(){ return dq.front(); }
T back(){ return dq.back(); }
bool empty(){ return dq.empty(); }
};
✅ priority_queue 本质：堆
// push: 上浮
// pop: 下沉
// top: 堆顶元素
内部使用 make_heap, push_heap, pop_heap
✅ 常考题 & 应用场景总结
| 容器 | 高频问题 | 应用场景 |
|---|---|---|
| stack | 括号匹配、逆序、单调栈 | DFS、表达式求值 |
| queue | 层序遍历、滑动窗口 | BFS、调度队列 |
| priority_queue | 第K大、合并区间 | Dijkstra、A*、频率统计 |
✅ 小技巧
✅ 清空容器（没有 clear）
priority_queue<int>().swap(pq);
✅ priority_queue 提取所有元素变有序
- 最大堆 → 降序
- 最小堆 → 升序
✅ 面试常踩坑
| 问题 | 正确答案 |
|---|---|
| stack/queue 是否可遍历？ | ❌ NO |
| priority_queue 是否稳定排序？ | ❌ NO |
| queue 是否使用 vector？ | ❌ 默认 deque |
📌 完整对比总结图
| 特性 | stack | queue | priority_queue |
|---|---|---|---|
| 底层结构 | deque/vector/list | deque/list | vector(堆) |
| 序访问限制 | 严格 | 严格 | 非线性 |
| 是否支持随机访问 | ❌ | ❌ | ❌ |
| 最佳算法场景 | DFS | BFS | 堆优化算法 |
发表回复