stack、queue 与 priority_queue

C++ STL 详解 —— stack、queue 与 priority_queue 全面解析

写在前面：
这一篇我们把 STL 里的三个“特殊选手”一次讲清楚 —— stack、queue 和 priority_queue。
它们不属于传统意义上的“容器”，而是 容器适配器（container adapter）。
这几个在面试、OJ 里出现频率非常高，不熟真的会吃亏。

一、stack（栈）

1.1 stack 的基本概念

栈是一种 后进先出（LIFO） 的线性结构。

通俗点说：

• 先进来的在底下
• 后进来的在上面
• 只能操作“栈顶”

常用接口

stack()
empty()
size()
top()
push()
pop()

⚠ 注意：
pop() 没有返回值，这是很多人刚开始会写错的。

1.2 stack 的典型应用

例1：最小栈

要求：

• push
• pop
• top
• getMin

核心思想：
用两个栈。

class MinStack {
public:
void push(int x) {
_elem.push(x);

if (_min.empty() || x <= _min.top())
_min.push(x);
}

void pop() {
if (_elem.top() == _min.top())
_min.pop();

_elem.pop();
}

int top() {
return _elem.top();
}

int getMin() {
return _min.top();
}

private:
stack<int> _elem;
stack<int> _min;
};

思路精髓：

• _elem 正常存数据
• _min 只记录“当前最小值轨迹”

时间复杂度全部 O(1)。

例2：判断出栈序列是否合法

典型模拟题。

核心思路：

• 用一个辅助栈
• 模拟压栈过程
• 看是否能按顺序弹出

bool IsPopOrder(vector<int> pushV, vector<int> popV) {
if (pushV.size() != popV.size())
return false;

stack<int> s;
int in = 0;
int out = 0;

while (out < popV.size()) {
while (s.empty() || s.top() != popV[out]) {
if (in < pushV.size())
s.push(pushV[in++]);
else
return false;
}

s.pop();
out++;
}

return true;
}

这是标准模拟题模板。

例3：逆波兰表达式求值

遇到运算符，弹两个数。

int evalRPN(vector<string>& tokens) {
stack<int> s;

for (auto& str : tokens) {
if (str == "+" || str == "-" || str == "*" || str == "/") {
int right = s.top(); s.pop();
int left = s.top(); s.pop();

if (str == "+") s.push(left + right);
if (str == "-") s.push(left – right);
if (str == "*") s.push(left * right);
if (str == "/") s.push(left / right);
}
else {
s.push(atoi(str.c_str()));
}
}

return s.top();
}

OJ 高频题。

1.3 stack 的模拟实现

stack 本质只需要：

• push_back
• pop_back
• back

所以可以直接用 vector 封装：

template<class T>
class MyStack {
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_back(); }
T& top() { return _c.back(); }
bool empty() const { return _c.empty(); }
size_t size() const { return _c.size(); }

private:
vector<T> _c;
};

简单干脆。

二、queue（队列）

2.1 queue 的基本概念

队列是 先进先出（FIFO）。

• 从队尾进
• 从队头出

常用接口

queue()
empty()
size()
front()
back()
push()
pop()

2.2 queue 的应用

用两个栈实现队列

经典面试题。

核心思路：

• s1 负责入队
• s2 负责出队
• s2 空时，把 s1 全倒过去

class MyQueue {
public:
void push(int x) {
s1.push(x);
}

int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}

int x = s2.top();
s2.pop();
return x;
}

private:
stack<int> s1;
stack<int> s2;
};

2.3 queue 的模拟实现

queue 需要：

• push_back
• pop_front

vector 头删效率低。

更适合用 list：

template<class T>
class MyQueue {
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& front() { return _c.front(); }
T& back() { return _c.back(); }
bool empty() const { return _c.empty(); }

private:
list<T> _c;
};

三、priority_queue（优先队列）

3.1 本质是什么？

它就是一个 堆。

默认是：

大堆（最大堆）

priority_queue<int> q;

3.2 改成小堆

priority_queue<int, vector<int>, greater<int>> q;

第三个参数是比较器。

3.3 典型应用：第 K 大元素

int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());

for (int i = 0; i < k – 1; i++)
pq.pop();

return pq.top();
}

时间复杂度：

O(n + k log n)

更优写法可以用小堆控制 k 个元素。

3.4 自定义类型

必须重载 < 或 >。

class Date {
public:
Date(int y, int m, int d)
: _year(y), _month(m), _day(d) {}

bool operator<(const Date& other) const {
if (_year != other._year)
return _year < other._year;
if (_month != other._month)
return _month < other._month;
return _day < other._day;
}

private:
int _year;
int _month;
int _day;
};

默认大堆使用 <。

四、容器适配器

4.1 什么是适配器？

一句话：

用已有容器封装出新的接口形式。

stack 和 queue：

• 本质是对其他容器的“限制性封装”

4.2 为什么默认用 deque？

因为：

• vector 扩容会搬迁数据
• list 不支持随机访问
• deque 头尾插入效率高
• stack/queue 不需要遍历

deque 结合了优点。

五、总结

六、OJ 高频练习

建议练：

• 用两个栈实现队列
• 用队列实现栈
• 第 K 大元素
• 逆波兰表达式
• 滑动窗口最大值

最后一句

栈、队列、优先队列本身不难。

难的是：

什么时候该想到用它们。

刷题刷多了，你会发现：

• 模拟流程 → 栈
• 层序遍历 → 队列
• 排序前 K → 堆

熟练之后，它们是非常好用的工具。