概述
在 C++ 标准库的庞大体系中，数据结构是支撑高效编程的基石。容器适配器、序列容器以及相关的算法逻辑，构成了其中最具实用价值的核心内容。无论是日常开发还是算法刷题，栈（stack）、队列（queue）、优先级队列（priority_queue）这些'常客'的身影几乎无处不在。
它们看似简单的接口背后，藏着对数据存取规则的精妙设计：栈的'先进后出'适配递归调用、括号匹配等场景；队列的'先进先出'适配层序遍历、任务调度等需求；优先级队列则通过堆结构实现带权重的数据筛选，成为 TopK 问题的利器。
深入学习这些结构时，我们往往会产生更多疑问：为什么栈和队列的默认底层容器是 deque 而非 vector 或 list？deque 的'分段连续'存储到底特殊在哪里？优先级队列中，仿函数是如何灵活控制堆的排序逻辑的？反向迭代器的设计又暗藏哪些技巧？本文不仅会系统梳理核心接口与使用场景，更会通过完整的模拟实现代码，拆解容器适配器的封装逻辑，帮你理清细节，从'会用'进阶到'精通'。
栈 (Stack)
栈遵循后进先出（LIFO）原则，注意区分栈顶和栈底——栈顶是最后放入的那个元素。
常用接口一览
empty(): 判断是否为空size(): 获取元素数量top(): 访问栈顶元素push(val): 压入元素pop(): 弹出栈顶元素
注意：没有迭代器，不要尝试访问空的栈，否则可能引发未定义行为。
模拟实现
namespace renshen {
// 容器适配器模板
template<class T, class Container = deque<T>>
class stack {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
T& top() { return _con.back(); }
size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Container _con;
};
}
队列 (Queue)
队列遵循先进先出（FIFO）原则。
常用接口一览
empty(),size(): 状态查询front(),back(): 访问队头/队尾push(val): 队尾入队pop(): 队头出队
同样没有迭代器支持直接遍历。
模拟实现
namespace renshen {
template<class T, class Container = deque<T>>
class queue {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
T& front() { return _con.front(); }
T& back() { return _con.back(); }
size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Container _con;
};
}
双端队列 (Deque)
相比于 vector，deque 极大缓解了扩容问题并支持头插头删；相比于 list，它支持下标随机访问且 CPU 高速缓存效率不错。
总结： deque 适合高频头插头删、尾插尾删，并且需要少量下标随机访问的场景。
其模拟实现通常采用中控指针数组（控制分散的一片一片区域），当中控指针数组满了再扩容即可。
常见接口
begin, end, rbegin, rend, size, empty, resize, [], front, back, erase, clear, push_front, push_back, pop_front, pop_back, insert
容器适配器概览
命名上通常沿用 container 作为模板参数名，让模板更具通用性。
优先级队列 (Priority Queue)
优先级队列本质上是堆，堆顶即为优先级最高的元素。处理 TopK 问题时用堆排序效果较好，全排序则建议直接使用 std::sort（时间复杂度 O(NlogN)）。
常用接口
empty,size,top,push,pop- 无迭代器，遍历需逐项取出
模拟实现
这里展示了基于向量构建大堆的核心逻辑，包含向上调整和向下调整算法。
namespace renshen {
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
private:
void AdjustDown(int parent) {
Compare com;
size_t child = parent * 2 + 1;
while (child < _con.size()) {
if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
++child;
}
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
} else break;
}
}
void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while (child > 0) {
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
} else break;
}
}
public:
priority_queue() {}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
_con.push_back(*first);
++first;
}
// 建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(i);
}
}
void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
const T& top() { return _con[0]; }
bool empty() { return _con.empty(); }
size_t size() { return _con.size(); }
private:
Container _con;
};
}
反向迭代器
rbegin 其实指向 end 位置，rend 指向 begin 位置（注意 rbegin 并不是最后一个有元素的位置，而是逻辑上的起始）。
namespace renshen {
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator {
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _it;
ReverseIterator(Iterator it) : _it(it) {}
Ref operator*() {
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->() { return &(operator*()); }
Self& operator++() {
--_it;
return *this;
}
Self& operator--() {
++_it;
return *this;
}
bool operator!=(const Self& s) const {
return _it != s._it;
}
};
}
引申：重载运算符的结合性和优先级是跟本身的运算符一样的。
仿函数 (Function Object)
仿函数即函数对象，类对象可以像函数一样使用。库里面的 less<T> 用来搞升序，greater<T> 用来搞降序。
相比普通函数，仿函数具有状态保持等优势，但需注意其类型可能因状态不同而不同。
实战演练
理论之外，实战更能检验掌握程度。以下精选了几道经典题目，展示容器的妙用。
最小栈 (Min Stack)
思路： 维护两个栈，一个存数据 _st，另一个存最小值 _min。插入时若比当前最小值小或为空则压入 _min；弹出时若与 _min 栈顶相同则同步弹出。
class MinStack {
public:
void push(int val) {
_st.push(val);
if (_min.empty() || val <= _min.top()) _min.push(val);
}
void pop() {
if (_st.top() == _min.top()) _min.pop();
_st.pop();
}
int top() { return _st.top(); }
int getMin() { return _min.top(); }
private:
stack<int> _st;
stack<int> _min;
};
栈的弹出压入序列
思路： 利用辅助栈模拟入栈过程。栈没跟出栈序列的元素匹配就入数据，匹配了就出数据。全入完了栈里还有数据说明不对。
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
int pushi = 0;
int popi = 0;
while (pushi <= pushV.size() - 1) {
st.push(pushV[pushi++]);
while (!st.empty() && st.top() == popV[popi]) {
popi++;
st.pop();
}
}
return popi == pushi;
}
};
二叉树的层序遍历
思路： 使用 queue 进行广度优先搜索。注意处理 root 为空的情况。对于自底向上的版本，只需在结果基础上 reverse 即可。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vv;
queue<TreeNode*> q;
int levelsize = 0;
if (root) {
q.push(root);
levelsize = 1;
}
while (!q.empty()) {
vector<int> v;
for (int i = 1; i <= levelsize; i++) {
TreeNode* j = q.front();
q.pop();
v.push_back(j->val);
if (j->left) q.push(j->left);
if (j->right) q.push(j->right);
}
levelsize = q.size();
vv.push_back(v);
}
return vv;
}
};
数组中的第 K 个最大元素
思路：
- 建大堆，把前 k-1 个堆顶踢了。
- 建 k 个元素的小堆，遍历数组，比堆顶大则替换。最终堆顶即为第 K 大。
注意：建小堆要用
greater<T>。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq;
for (auto e : nums) {
pq.push(e);
}
while (k > 1) {
pq.pop();
k--;
}
return pq.top();
}
};
知识点辨析
- 仿函数特性： 仿函数在同一时间里可代表单一函数但有不同状态；定义相同也可能类型不同；使代码变简单。关于速度，通常认为与普通函数相当或略慢（因虚函数开销），但在特定优化下表现优异。
- 容器选择： 如果需要高效的随机存取，还要大量的首尾插入删除，建议使用
deque。 - 迭代器失效：
vector和deque底层是连续空间，删除元素会挪动数据，可能导致原有迭代器失效；list是链表，删除节点不影响其他节点迭代器。
补充说明
- 逆波兰表达式： 后缀表达式，操作数顺序不变，操作符按优先级重排。转换时遇到左括号视为新起点，右括号停止递归出栈。
- 内存分配： 堆上开辟的空间地址随机；栈空间则遵循固定规则。
- 命名空间： 自定义头文件若未展开命名空间，需在.cpp 文件中显式展开，避免编译错误。