std::stack 的核心接口是六个:push、pop、top、empty、size,加一个构造函数(C++11 还有 emplace 和 swap,用法与普通容器一致)。std::queue 没有 top,改成 front 和 back 各管一头,所以多一个成员。两个类里没有一行真正的算法,全是把操作转给底层容器。
| 容器 | 接口 | 语义 |
|---|---|---|
stack | stack() / push(x) / pop() / top() / empty() / size() | 构造空栈;压栈;弹出栈顶(返回 void);栈顶引用;判空;元素个数 |
queue | queue() / push(x) / pop() / front() / back() / empty() / size() | 构造空队列;队尾入队;队头出队(返回 void);队头引用;队尾引用;判空;元素个数 |
stack 的模拟实现只需要底层提供 push_back、pop_back、back、empty、size:
#include <cstddef>
#include <deque>
template<class T, class Con = std::deque<T>>
class MyStack
{
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_back(); }
T& top() { return _c.back(); }
const T& top() const { return _c.back(); }
bool empty() const { return _c.empty(); }
std::size_t size() const { return _c.size(); }
private:
Con _c;
};换成 std::vector<T> 或 std::list<T> 把 Con 填进去,这段代码照样成立。栈和 vector 之间没有特殊关系,vector 只是满足那五个操作的容器之一。

适配器是接口收窄,不是新容器
stack、queue、priority_queue 在标准里叫容器适配器(container adaptor)。适配器是一种设计模式:把一个已有接口转换成调用方需要的那组接口,自己不负责存储。

这层收窄有两个直接后果。
第一,适配器没有迭代器。stack 和 queue 都没有 begin()、end()。一给迭代器,就能从中间插入、删除、改元素,“只能从端点进出”的约束当场失效,所以标准干脆不提供。
第二,Container 模板参数只表示“用谁来装”,不表示“它一定合适”。约束是在成员函数体里兑现的:queue::pop 调用 _c.pop_front(),容器没有这个成员,模板实例化到那一行才报错。语法上允许填,语义上未必成立。
pop() 返回 void 也是同一个思路。要返回值就得先拷贝或移动栈顶元素,再删;遇到不可拷贝的类型(比如 std::unique_ptr)这条路直接走不通,拷贝途中抛异常还会破坏强异常保证。所以读用 top()/front(),删用 pop(),两件事分开。空容器上调 top()、front()、pop() 都是未定义行为,不是抛异常。
deque 的分段结构,正好只被用在两端
stack 只用尾部,deque 和 vector 都够;queue 要头删,vector 没有 pop_front,list 可以。标准却给两个适配器都默认了 deque,原因在于它两端都是 O(1),而且扩容不搬已有元素。

deque 不是一整块连续内存。它由若干段固定大小的缓冲区拼成,另有一张指针数组(中控数组,libstdc++ 里叫 map)按顺序指向这些缓冲区。

为了维持“看起来连续、还能 d[i]”的假象,deque 的迭代器要同时记住四个位置:

每次自增都要判断有没有跨过缓冲区边界,随机访问也要多一层间接,所以遍历和下标访问都比 vector 慢。这就是 deque 的短板,也是它在一般序列场景里用得少的原因。和 list 比,它不用为每个元素额外存两个指针,空间利用率更高。往两端插入时,如果当前缓冲区还有空位就直接放;没有空位就新开一段,把指针挂到中控数组前面或后面——已有元素不搬家。

stack 和 queue 恰好绕开了 deque 的两个短板:它们从不遍历,只碰端点;而两端的 O(1)、扩容不搬元素、已有元素的引用保持稳定这几条优点全留下了。所谓“避开缺陷”,说的是场景匹配。
课件在这里有两句话要改。一句是“栈实际是一种特殊的 vector,因此使用 vector 完全可以模拟实现 stack”:stack 与 vector 没有特殊关系,默认底层是 deque,vector 只是候选之一。另一句说 deque 扩容不用搬元素、效率比 vector 高:这只在头部插入和扩容时成立,遍历和随机访问它都不如 vector,不能一概而论。
queue 要求底层能头删
queue 对底层容器的要求是一组具体操作:empty、size、front、back、push_back、pop_front。deque 和 list 都满足,vector 不满足——它没有 pop_front,头删要搬移全部元素。默认选择 deque。
#include <cstddef>
#include <deque>
template<class T, class Con = std::deque<T>>
class MyQueue
{
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& front() { return _c.front(); }
const T& front() const { return _c.front(); }
T& back() { return _c.back(); }
const T& back() const { return _c.back(); }
bool empty() const { return _c.empty(); }
std::size_t size() const { return _c.size(); }
private:
Con _c;
};课件用 list 做 queue 的模拟实现,结论是对的:list 有 push_back 和 pop_front。但默认实现用的是 deque,因为 list 每个元素要多背两个指针,缓存也不友好。
priority_queue 是堆,比较器决定堆顶是谁
priority_queue 的模板签名是三个参数:
template<class T,
class Container = std::vector<T>,
class Compare = std::less<T>>
class priority_queue;| 接口 | 语义 |
|---|---|
priority_queue() / priority_queue(first, last) | 构造空队列;用 [first, last) 建堆 |
empty() / size() | 判空、元素个数 |
top() | 堆顶元素(默认是最大元素) |
push(x) | 插入 x |
pop() | 删除堆顶元素 |
底层容器必须支持随机访问迭代器,并提供 empty、size、front、push_back、pop_back。vector 和 deque 满足,list 不行。默认用 vector。
默认比较器是 std::less<T>,结果却是最大值在堆顶。这并不矛盾:堆按比较器维护“父节点不小于子节点”,less 认为更大的元素更“大”,最大元素自然浮到 front()。
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main()
{
std::vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
std::priority_queue<int> big(v.begin(), v.end()); // 大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> small(v.begin(), v.end());
std::cout << big.top() << ' ' << small.top() << '\n'; // 9 0
}课件那张接口表把 priority_queue(first, last) 也写成“构造一个空的优先级队列”,这一格是错的。区间构造会把 [first, last) 里的元素搬进底层容器并调用 make_heap,构造完不是空的,也不保持原顺序,只保证堆性质;只有默认构造才是空队列。
放自定义类型时,默认的 less 需要类型提供 operator<,换 greater 则需要 operator>:
#include <functional>
#include <queue>
#include <vector>
struct Date
{
int y = 1900, m = 1, d = 1;
bool operator<(const Date& o) const
{
if (y != o.y) return y < o.y;
if (m != o.m) return m < o.m;
return d < o.d;
}
bool operator>(const Date& o) const { return o < *this; }
};
int main()
{
std::priority_queue<Date> big; // 用 <
std::priority_queue<Date, std::vector<Date>, std::greater<Date>> small; // 用 >
big.push(Date{2018, 10, 29});
small.push(Date{2018, 10, 29});
return 0;
}priority_queue 底下是三个算法函数:make_heap、push_heap、pop_heap。堆是一棵完全二叉树压进数组,下标 i 的孩子是 2i+1 和 2i+2,所以底层必须是随机访问容器。push 把新元素放到末尾再上浮,pop 把堆顶与末尾交换、删掉末尾再下沉,两者都是 O(log N)。课件里的模拟实现就是这层转发:
#include <algorithm>
#include <cstddef>
#include <functional>
#include <vector>
template<class T, class Con = std::vector<T>, class Compare = std::less<T>>
class MyPriorityQueue
{
public:
MyPriorityQueue() = default;
template<class InputIt>
MyPriorityQueue(InputIt first, InputIt last) : _c(first, last)
{
std::make_heap(_c.begin(), _c.end(), Compare());
}
void push(const T& x)
{
_c.push_back(x);
std::push_heap(_c.begin(), _c.end(), Compare());
}
void pop()
{
std::pop_heap(_c.begin(), _c.end(), Compare());
_c.pop_back();
}
const T& top() const { return _c.front(); }
bool empty() const { return _c.empty(); }
std::size_t size() const { return _c.size(); }
private:
Con _c;
};几个题里,数据结构的选择就是解法
最小栈。要求 push、pop、top、getMin 都是 O(1)。用两个栈,一个存全部元素,另一个只在“新元素不大于当前最小值”时压入,弹出时两个栈顶相等就一起弹。
#include <stack>
class MinStack
{
public:
void push(int x)
{
_elem.push(x);
if (_min.empty() || x <= _min.top())
_min.push(x);
}
void pop()
{
if (_min.top() == _elem.top())
_min.pop();
_elem.pop();
}
int top() const { return _elem.top(); }
int getMin() const { return _min.top(); }
private:
std::stack<int> _elem, _min;
};比较必须用 <=。只用 < 时,连续压两个相同的最小值只会记录一份,弹掉一个后 _min 仍然停在旧值,和真实最小值对不上。
栈的压入、弹出序列。给两个等长序列,判断后者能不能是前者的合法出栈顺序。用一个栈模拟:按 pushV 顺序入栈,每入一个就看栈顶是否等于当前的 popV[outIdx],相等就持续弹出并推进 outIdx;pushV 用完仍不相等,返回 false。
逆波兰表达式求值。遇数字入栈,遇运算符弹出两个操作数,先弹出的是右操作数。顺序写反,减法和除法立刻出错。
#include <cstdlib>
#include <stack>
#include <string>
#include <vector>
int evalRPN(const std::vector<std::string>& tokens)
{
std::stack<int> s;
for (const auto& str : tokens)
{
if (str == "+" || str == "-" || str == "*" || str == "/")
{
int right = s.top(); s.pop();
int left = s.top(); s.pop();
switch (str[0])
{
case '+': s.push(left + right); break;
case '-': s.push(left - right); break;
case '*': s.push(left * right); break;
case '/': s.push(left / right); break;
}
}
else
{
s.push(std::atoi(str.c_str()));
}
}
return s.top();
}两个栈实现队列。新元素一律进 _in;出队时若 _out 为空,就把 _in 整个倒进 _out,队列头就浮到 _out 的栈顶。“_out 为空才倒”这条判断不能省,否则每次出队都搬一遍,整体退化成 O(N²)。有它,每个元素最多被搬两次,摊还 O(1)。
#include <stack>
class MyQueue
{
public:
void push(int x) { _in.push(x); }
int pop()
{
int v = front();
_out.pop();
return v;
}
int front()
{
if (_out.empty())
while (!_in.empty())
{
_out.push(_in.top());
_in.pop();
}
return _out.top();
}
bool empty() const { return _in.empty() && _out.empty(); }
private:
std::stack<int> _in, _out;
};数组中第 K 大的元素。把整个数组丢进大堆再弹 k-1 次,空间是 O(N)。更省的做法是维护一个大小为 k 的小堆:新元素入堆,超过 k 就弹掉堆顶(当前这 k 个里最小的),扫完堆顶就是第 K 大。
#include <functional>
#include <queue>
#include <vector>
int findKthLargest(const std::vector<int>& nums, int k)
{
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
for (int x : nums)
{
pq.push(x);
if (static_cast<int>(pq.size()) > k)
pq.pop();
}
return pq.top();
}用大堆还是小堆,取决于要把谁丢出去:要保留最大的 k 个,就得让最小的那个一直待在堆顶,等着被弹掉。
还没有评论 — 第一条由你来留。