std::stack 的核心接口是六个:push、pop、top、empty、size,加一个构造函数(C++11 还有 emplace 和 swap,用法与普通容器一致)。std::queue 没有 top,改成 front 和 back 各管一头,所以多一个成员。两个类里没有一行真正的算法,全是把操作转给底层容器。

容器接口语义
stackstack() / push(x) / pop() / top() / empty() / size()构造空栈;压栈;弹出栈顶(返回 void);栈顶引用;判空;元素个数
queuequeue() / 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 的操作都集中在同一端:push 从顶部压入,pop 从顶部弹出,top 指向最新压进去的那个元素

适配器是接口收窄,不是新容器

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

适配器的含义:墙上的插座提供的是另一种接口,中间那块转换头不改电本身,只把插头形状对上。stack 对 deque 做的事与此相同

这层收窄有两个直接后果。

第一,适配器没有迭代器。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 是双端进出的线性结构:push/pop 在头尾各有一对,四个操作都是 O(1)

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

deque 的底层:左边是中控数组,每个槽存一个指向缓冲区的指针;右边是若干段独立的缓冲区。中控数组满时,会另找一块更大的空间把指针搬过去,元素本身不动

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

deque 迭代器的四个字段:cur 指向当前元素,first/last 是当前缓冲区的边界,node 是这段缓冲区在中控数组里的槽位。++ 越过 last 时换段并同步 node

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

尾部连续 push 时,新元素先填满当前缓冲区;满了再申请一段新缓冲区,并把指针追加到中控数组。整个过程没有整块搬运

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 个,就得让最小的那个一直待在堆顶,等着被弹掉。