C++ STL中的stack与queue：容器适配器的原理与实战

《C++初阶》系列写到第 13 篇，总算轮到 STL 里最“没存在感”的两个家伙——stack 和 queue 了。说它们没存在感，是因为相比前面动辄十几个接口的 string、vector、list，stack 的公开接口一只手能数完：push、pop、top、empty、size。queue 也只是多了 front 和 back 两个成员。很多初学者学到这儿都会松一口气：这章总算简单了。

但我得先泼一盆冷水：恰恰是这两个看似不起眼的容器适配器，背后藏着 STL 最核心的设计思想。面试里问“stack 的默认底层容器为什么是 deque”“pop 为什么返回值是 void”“适配器（adapter）到底适配了什么”，答不上来的大有人在。而且在实际工程中，括号匹配、逆波兰表达式求值、BFS 层序遍历、单调栈求最大矩形、任务调度队列，几乎没有一处离得开它们。所以这篇文章不打算只列接口就算了，而是把这两个“小玩意儿”从上到下、从原理到实践彻底拆开，让你不只是会写 stack<int> st;，还能说出每一个设计决策背后的为什么。

1. 先搞清楚定位：stack 和 queue 不是容器，是容器适配器

1.1 从接口看本质：为什么代码这么短

先看标准库的头文件设计。<stack> 和 <queue> 内部并不像 vector、list 那样自己维护一块内存、自己实现扩容逻辑，它们只是“站在别人的肩膀上”。stack 的类模板声明是这样的：

cpp复制template<class T, class Container = std::deque<T>>
class stack;

queue 同样：

cpp复制template<class T, class Container = std::deque<T>>
class queue;

看到没，第二个模板参数 Container 默认给的是 std::deque<T>。也就是说，你写 stack<int> 时，真正干活的是它内部那一个 deque 对象。stack 本身只做一件事：把 deque 的接口“藏起来”，只暴露出符合栈语义的那几个方法。这就是适配器的本质——不重新发明轮子，而是给已有的轮子套一个限位器，让它只能往前滚或者只能往后滚。

我见过不少初学者在这里纠结：既然底层是 deque，那我直接用一个 deque 不就行了吗？为什么要多套一层 stack？答案是：语义约束比功能丰富更重要。deque 可以头插、尾插、中间插入、随机访问，太灵活了，灵活就意味着容易用错。而 stack 把操作限制成“只能在尾部压入、只能在尾部弹出、只能看尾部元素”，这种限制本身就是一种设计，它让代码的意图一目了然。你看到 st.push(x)，脑子里立刻知道这是入栈；你看到 q.pop()，立刻知道这是出队。如果换成 deque，你写 dq.push_back(x)，还得想想这到底是栈还是队列还是别的什么。

1.2 适配器模式：STL 里的“限位器”

适配器（Adapter）是一种经典的设计模式，在《设计模式》那本书里跟迭代器、观察者并列。它的核心思想是：不改变底层类的实现，只改变它的接口外观。生活里最常见的例子是电源转换插头——你从国内带过去的手机充电器是两脚扁插，到了国外插座是三脚圆孔，你不会把充电器拆了重新焊一个头，而是加一个转换插头，对外暴露的插孔变成适配当地电网的形状，里面的电压转换逻辑原封不动。

STL 里的 stack 和 queue 就是这种“转换插头”。底层容器（默认 deque）负责具体的内存分配、元素存取、扩容收缩，适配器（stack/queue）负责定义一个 LIFO 或 FIFO 的操作边界。这样一来，底层容器可以随意替换，只要它提供适配器需要的接口就行。stack 需要底层容器支持 push_back、pop_back、back，queue 需要底层容器支持 push_back、pop_front、front、back。所以你看标准库文档里 stack 对 Container 的要求是“满足 SequenceContainer 并且支持 back()、push_back()、pop_back()”，queue 则要求支持 front()、back()、push_back()、pop_front()。这就是适配器能随意组合的基础。

这种“组合优于继承”的思路也值得你在自己的项目里借鉴。不要动不动就继承一个类然后重写一堆虚函数，很多时候你需要的只是把已有类的接口裁剪一下暴露出去。写一个 class Logger { ... }，内部持有 ofstream，对外只提供 info()、error()，这本质上也是一个适配器。

1.3 为什么默认底层是 deque，而不是 vector 或 list

这是最容易被问到、也最容易被一句话带过的问题。很多教程说“因为 deque 对头尾操作都是 O(1)”，但这句话只说对了一半。完整答案有两个层面。

第一，stack 只需要尾部操作，vector 也能胜任，而且 vector 尾部操作还是摊还 O(1) 的，那为什么不用 vector？因为 deque 在扩容策略上比 vector 更平滑。vector 扩容是“一次性搬大房子”，当容量不够时，分配新空间、拷贝/移动旧元素、释放旧空间，这一瞬间的开销非常大。而 deque 的扩容是“旁边加盖一间小房子”，它维护一个中控器（map）指针数组，每个指针指向一段固定大小的缓冲区，空间不够时只是在中控器里多申请一个指针位置，再分配一块新缓冲区，已有的元素不需要搬动。所以 deque 的尾部插入最坏情况也只是 O(1)，不会出现 vector 那样偶尔一次重度拷贝。

第二，queue 需要头部操作。vector 的头部删除是 O(n)，因为所有元素要往前挪一位，这在队列场景下是不可接受的。而 deque 支持头尾两端都是 O(1) 的插入删除。list 头尾操作也是 O(1)，为什么不用 list？因为 list 是链式结构，每个节点单独分配内存，节点之间用指针串联，对 CPU 缓存极其不友好。你遍历 queue 里的元素时，list 的节点在内存里七零八落，预取机制基本失效；deque 的元素集中在一段段连续缓冲区里，缓存命中率高出不少。再加上 list 每个节点还要额外存储两个指针，空间开销也更大。

所以答案其实是一道排除题：vector 头部不行，list 缓存和空间不行，deque 两边都行，它就是两个需求交叉点上的最优解。这个结论放到今天依然成立，也是为什么标准库敢把 deque 作为默认底层的原因。

2. 接口梳理与实操要点：小而美的工具箱

2.1 stack 的五个核心接口，逐个过一遍细节

stack 的接口确实少，但这几个接口的坑一点也不少。

• push(const T& value)：入栈。把元素拷贝进栈顶。
• push(T&& value)：入栈，右值版本，把元素移动进栈顶，避免拷贝。
• pop()：出栈，无返回值。
• top()：返回栈顶元素的引用。
• empty()、size()：判断空和长度。

先说 pop() 为什么返回 void。这个设计是刻意为之的。如果 pop() 返回被弹出的元素，那么它的实现就必须先构造一个返回值再删除栈顶元素。如果这个过程中抛出异常（比如返回值拷贝失败），栈顶已经被破坏或者元素已经丢失，你就陷入了一个“到底弹没弹出去”的状态。为了保证强异常安全（strong exception guarantee），标准库干脆让 pop() 只负责删除，取值请先 top()。所以正确的出栈姿势是：

cpp复制int value = st.top();
st.pop();

再强调一次：如果你直接写 int value = st.pop();，编译直接报错。这其实是一件好事，编译器把你拦在了错误用法之外。还有一点容易被忽略：top() 返回的是引用，所以你可以修改栈顶元素，比如 st.top() = 42;。不过说实话，我写代码这么多年，修改栈顶元素的场景极少，大多数时候只是读它。

2.2 queue 的六个核心接口，注意 front 和 back 的区分

queue 比 stack 多了两个接口，因为队列天然有两个端点：

• push(const T& value) / push(T&& value)：队尾入队。
• pop()：队头出队，同样无返回值。
• front()：队头元素的引用。
• back()：队尾元素的引用。
• empty()、size()。

一个常见的操作误区是搞混 front() 和 back()。说个我自己的糗事，刚学 STL 那会儿写一个任务队列，本来想取队头的优先级最高的任务，结果写了 task_queue.back()，取到了最后加进来的任务，排查了半天才发现是接口用错了。所以初学阶段笔者的建议是：每次都心里默念一遍——front() 是等待最久的那个，back() 是刚进来的那个。宁可慢一点，也别写反。

另外 queue 没有 top()，对应的就是 front()。如果你习惯了 stack 的 top()，切到 queue 的时候特别容易把 front() 写成 top()，编译器报错倒是小事，就怕你在一堆代码里翻来覆去找不到这个错误。

2.3 初始化方式与底层容器切换：一次性把配置讲明白

stack 和 queue 的构造除了默认构造，还有几种实用形态。假设你手里已经有一个 vector 存了大量数据，想让它们依次入栈：

cpp复制std::vector<int> vec = {1, 2, 3, 4, 5};
std::stack<int, std::vector<int>> st(vec);

注意这里的写法：std::stack<int, std::vector<int>>。第二个模板参数指定底层容器为 vector，然后把现成的 vector 传进去构造。queue 也一样：

cpp复制std::deque<int> dq = {1, 2, 3, 4};
std::queue<int> q(dq);

默认情况下 queue<int> 的底层就是 deque，所以直接用 deque 初始化的代码很自然。如果你想让 queue 用 list 做底层，比如你需要在元素中间做删除且队列操作不多：

cpp复制std::list<int> lst = {1, 2, 3};
std::queue<int, std::list<int>> q(lst);

这种灵活性就是适配器模式带来的好处。你甚至可以自定义一个底层容器类，只要它支持 queue 需要的那些接口就行，STL 不会对你做任何“必须继承自某某类”的强制要求。这种基于鸭子类型（duck typing）的模板设计，是 STL 能够高度复用的根基。

还有一个 C++11 之后才有的细节：stack 和 queue 都支持用初始化列表构造？其实不行。标准库没有为它们提供 initializer_list 构造函数，你写 std::stack<int> st = {1, 2, 3}; 会编译失败。想用列表初始化，得先构造底层容器：

cpp复制std::deque<int> dq = {1, 2, 3};
std::stack<int> st(dq);

这个坑我见不少人踩过，提前给你打预防针。

2.4 一个大坑：容器适配器没有迭代器，遍历怎么办

很多从 vector 转过来的同学，第一反应是写 for (auto it = st.begin(); it != st.end(); ++it)。醒醒，stack 和 queue 根本没有 begin() 和 end()。它们故意不提供迭代器，目的是防止你违反栈的原则——不允许你从栈底开始顺藤摸瓜翻一遍元素，你要么只看栈顶，要么一个个弹出来。

那万一我真的就是想看看栈里有哪些元素怎么办？办法有好几个。如果只是临时调试，可以开一个副本，把元素依次弹出：

cpp复制std::stack<int> tmp = st;
while (!tmp.empty()) {
    std::cout << tmp.top() << " ";
    tmp.pop();
}

如果是真正业务需求，说明你的数据结构选错了。要么直接用 deque，要么把 stack 里的元素转存到 vector 再遍历。stack 和 queue 的语义是“受限的、单入口单出口的管道”，而不是“可以随便翻看的口袋”。这个设计约束不是缺陷，而是特性。

另外还有一点，stack 和 queue 都支持 swap，能高效交换两个适配器对象的内容：

cpp复制std::stack<int> a, b;
a.swap(b);
// 或者
swap(a, b);

因为底层容器是支持 swap 的，适配器直接转发这个操作，不会逐元素拷贝。写代码的时候用 swap 清理容器里所有元素也很方便：std::stack<int>().swap(st); 或者直接 st = {};（前提是类型支持）。

3. 性能对比与原理剖析：deque 到底凭什么

3.1 深入 deque 的结构：中控器与缓冲区的双轨制

要理解 stack 和 queue 的默认底层，必须知道 deque 是怎么设计的。如果你已经学过 vector 和 list，那可以这样类比：deque 是“一段段连续内存通过指针串起来的组合体”。

deque 在逻辑上是连续的，物理上却不是整块连续内存。它有一个叫做 map（中控器）的指针数组，map 里每个元素指向一段固定大小的缓冲区。缓冲区通常是 512 字节或者由实现决定，比如 GCC 的 libstdc++ 对 int 类型可以缓冲 128 个元素。当你在 deque 头部插入元素时，如果当前第一块缓冲区满了，中控器会在 map 前面追加一个指针，指向新的缓冲区；尾部也一样。所以 deque 的头尾插入不需要移动已有元素，也不需要整体搬移数据。

但是代价是什么？访问元素时不能像 vector 那样直接 base + index * size 一次算出来，需要先定位到哪一块缓冲区，再算缓冲区内的偏移。为了加速这个计算，deque 的迭代器并不只是持有一个指针，而是持有四个信息：当前元素的指针 cur、当前缓冲区的起始指针 first、当前缓冲区的结束指针 last、以及指向中控器某个槽位的指针 node。每次迭代器自增，如果 cur 到达 last，就要跳到下一块缓冲区。这就是 deque 的随机访问是 O(1) 但常数比 vector 大不少的原因。

你可以把 deque 理解成“一列火车”，每个车厢是一块连续内存，车厢与车厢之间用挂钩（map 指针）连接，乘客在车厢内部是连排坐，但车厢之间不连通。座位号越靠后的乘客定位越麻烦，得先数车厢再数座位。这就是为什么遍历 deque 比遍历 vector 慢，但比遍历 list 快得多。

3.2 三方对决：vector、list、deque 性能对比

纸上谈兵没有意义，关键场景下的性能对比才能说明问题。我整理了一张针对容器适配器常见操作的对照表，基于 C++17、Release 模式、GCC 11 的背景，数据是大量实测后的经验值（不是精确计时，但趋势非常稳定）：

看到这个表你应该明白了：stack 只需要尾部操作，vector 其实也不差，但 deque 的尾部插入最坏情况更好；queue 需要头尾两端，list 虽然两端也能 O(1)，但缓存命中和内存开销完全被 deque 碾压。所以默认 deque 是科学决策，不是拍脑袋。

3.3 函数调用栈与 std::stack 的关系：不要混淆两个“栈”

热词里有一条“protect(): protection stack overflow”，这是 R 语言环境里的报错，跟 C++ 的 std::stack 八竿子打不着。但在初学 C++ 的时候，很多人会把“函数调用栈”和“std::stack 容器”混为一谈，我在这儿顺手把二者的关系说清楚。

“函数调用栈（call stack）”是操作系统和编译器在程序运行时维护的一块内存区域，每次调用函数就把参数、返回地址、局部变量压进去，函数返回时再弹出。它确实是“栈”这种抽象逻辑的一种物理实现，但它跟 std::stack<int> 没有任何直接关系——后者只是你代码里手动管理的一个数据结构，存放在堆或其他内存区域。调用栈溢出通常是因为递归深度过深或者栈上分配了超大局部数组，这属于运行时错误；而 std::stack 的容量一般只受内存总量限制，几乎不会“栈溢出”。

所以当你在网上搜“c++ stack overflow”时，大概率看到的是 Stack Overflow 这个网站，其次是函数调用栈溢出的讨论，极少会撞到 std::stack 的容量问题。学习容器时把这两个概念切割清楚，后面学递归、学函数调用原理时才不会绕晕。

4. 实战演练：经典场景直接抄作业

4.1 括号匹配：栈的第一个经典考题

几乎每一本数据结构教材讲完栈的第一道题都是括号匹配，因为它的逻辑和栈的 LIFO 特性天然契合。给你一串字符串，里面包含 (、)、[、]、{、}，判断它是否合法。合法规则是：每个右括号必须有与之匹配的左括号，并且括号不能交叉嵌套，比如 ([)] 是非法的，([]) 合法。

解题思路就是从左到右扫描，遇到左括号入栈；遇到右括号，检查栈顶是不是对应的左括号，是就弹出，不是或者栈为空就判定非法。扫描结束后栈如果不为空，说明有左括号没闭合，也是非法。

cpp复制bool isValid(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

这个实现虽然能 AC，但我建议你再优化一步：用哈希表建立右括号到左括号的映射，代码会更简洁。关键在于理解：栈天然保留了“最近一个未匹配的左括号”这个信息，这正是 LIFO 的用武之地。

4.2 逆波兰表达式求值：把运算符写在后面的“计算器”

逆波兰表达式（Reverse Polish Notation, RPN）是一种不需要括号的表达式表示法，比如 3 4 + 5 * 等价于 (3 + 4) * 5。计算机非常喜欢这种格式，因为它能用栈一次扫描完成求值，不需要处理运算符优先级和括号。

规则是：从左到右扫描 tokens，遇到数字压栈；遇到运算符，弹出两个操作数，按顺序计算，结果重新压栈。注意弹出操作数时的顺序：第一个弹出的是右操作数，第二个左操作数，做减法或除法时顺序不能反。

cpp复制int evalRPN(std::vector<std::string>& tokens) {
    std::stack<int> st;
    for (const std::string& tok : tokens) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            if (tok == "+") st.push(left + right);
            else if (tok == "-") st.push(left - right);
            else if (tok == "*") st.push(left * right);
            else st.push(left / right);  // 注意整数除法向零截断
        } else {
            st.push(std::stoi(tok));
        }
    }
    return st.top();
}

逆波兰表达式的核心思想其实就是“把操作延迟到必要的时候”：你不确定一个数字什么时候会参与运算，只知道它参与运算时，一定是最新出现的、还没被动过的数字。这不就是栈顶嘛。

4.3 队列实现二叉树层序遍历：BFS 的标准模板

跟栈的 DFS 气质不同，queue 是 BFS（广度优先搜索）的天然伙伴。二叉树的层序遍历是 queue 的最典型应用：从根节点开始，每弹出一个节点，就把它的左右孩子依次入队，这样下一层总是排在当前层所有节点之后。

cpp复制struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        std::vector<int> level;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

这里最关键的技巧是 int levelSize = q.size();。必须在一开始就记录当前层的节点数，然后用这个数量来控制内部循环，如果不提前保存，循环里 q.size() 会不断变化，你会把下一层的节点也混进当前层。这个坑几乎所有初学者都踩过，我也是。

队列的 FIFO 特性保证了节点访问顺序就是“逐层推进”，这也是图里 BFS 求最短路径的基础。你以后写迷宫最短路径、社交网络好友推荐、操作系统任务调度，核心骨架都是这个模板。

4.4 自定义类型入栈：深拷贝、移动语义与性能优化

初学时大多数例子入栈的都是 int 或 string，但真实业务里经常要把自定义对象放进 stack 或 queue。假设你有一个 BigObject，构造函数里要申请大块内存，拷贝代价很高：

cpp复制struct BigObject {
    std::vector<double> data;
    explicit BigObject(size_t n) : data(n) {}
};

std::stack<BigObject> st;
BigObject obj(1000000);
st.push(obj);            // 拷贝，慢
st.push(std::move(obj)); // 移动，快（前提是你写入了移动构造函数）

这里有两个要点。第一，如果你已经不打算再用 obj，就写成 std::move(obj)，触发移动语义。第二，如果你没写移动构造函数，编译器会帮你生成一个默认的（前提是类里没有需要手动管理的资源，比如裸指针），它会把 data 的底层指针“偷”过来，不会发生深拷贝。

还需要注意一点：emplace 系列函数。C++11 为 stack 和 queue 增加了 emplace，它直接在容器内部构造对象，省去了一次拷贝/移动：

cpp复制st.emplace(1000000); // 直接调用 BigObject(size_t) 构造，不产生临时对象

这比 st.push(BigObject(1000000)) 少一次中间构造。我实测下来的经验：大对象入栈入队，优先考虑 emplace。

5. 常见问题与避坑实录

5.1 空容器操作：未定义行为是最大的坑

初学者最容易犯的错误，而且编译器大概率不报错——在对空栈或空队列调用 top()、front()、back() 时，程序的行为是未定义的。所谓未定义行为，就是可能返回垃圾值、可能崩溃、可能偶尔正常，完全不可控。标准库不会为了你去检查空不空，因为那会拖慢每一次合法操作的速度。

怎么防？两个手段：

1. 操作前显式检查 if (!st.empty())。
2. 写一个安全取值的小工具模板，统一封装：

cpp复制template<typename Adapter, typename T = typename Adapter::value_type>
std::optional<T> safeTop(Adapter& a) {
    if (a.empty()) return std::nullopt;
    return a.top();
}

std::optional 能很好地表达“可能有值也可能没有值”的语义，比返回一个默认值更安全。你没法用一个默认值表达“栈空了”这件事，因为默认值本身可能就是合法的栈元素。

5.2 迭代器失效问题：适配器反而更省心

用 vector 的时候，插入删除经常导致迭代器失效，残留迭代器再用就是悬垂指针。而 stack 和 queue 根本不提供迭代器，所以不存在“迭代器失效”这个困扰。这反而是适配器带来的一个隐形安全收益：你不可能持有一个容器内部的迭代器去绕过限制，所有访问都必须通过 push/pop/top/front 这些门面方法，风险面天然缩小。

但是注意，如果你用的是 std::stack<int, std::vector<int>> 这种自定义底层的 stack，并且你偷偷通过某种方式获得了底层容器的引用（比如继承 stack 暴露底层，虽然不建议），那你仍然要遵守 vector 的迭代器失效规则。这提醒我们：适配器只保护遵守规则的使用者，别想办法绕过去。

5.3 深浅拷贝问题：对象进容器后谁负责内存

自定义类型入栈还有一个经典误区：如果对象内部有裸指针，并且你只写了默认拷贝构造函数，那么入栈的是“浅拷贝”，两个对象共享同一块堆内存，析构时 double free 直接崩溃。

这个问题在 stack、queue、vector 里都一样，但在 stack 里来得更隐蔽，因为你看不到整体结构，以为只操作一个对象。解决办法很简单：遵循“三/五法则”——如果类管理了资源，就显式实现拷贝构造、拷贝赋值、析构函数，或者用 RAII 容器（比如 std::vector、std::string）代替裸指针。我自己这些年写代码的经验是，能用标准库容器就绝不用裸指针 + new/delete，让资源自己管理自己。

5.4 拓展：千万别把 priority_queue 忘了

写这篇文章前我看了一眼热词榜，很多人在搜“单调栈算法 c++”“广搜模板 c++”，这些算法依赖的容器就是 stack 和 queue，但我还想多提一句它俩的“近亲”——priority_queue。priority_queue 在 <queue> 头文件里，也是一个容器适配器，默认底层是 vector，本质是二叉堆。它跟 queue 的区别是：出队的是“优先级最高”的元素，而不是最早入队的元素。

处理“每次取当前最大值/最小值”的问题，比如堆排序、Top K、任务调度、Dijkstra 最短路，priority_queue 就是首选。它跟 stack/queue 的关系是：同一个适配器家族，不同的比较策略。学了 stack 和 queue 再学 priority_queue，你会发现 STL 的设计是一以贯之的——底层容器 + 接口限制 + 操作策略。

5.5 实战心法：什么时候必须用栈模拟递归

最后分享一个我备考刷题时总结出的心法：递归天然就是栈的结构，编译器用自己的 call stack 帮你压栈参数和局部变量。但当递归深度可能很大（比如深度优先搜索一个十万节点的树），或者你想避免函数调用开销时，就可以手动用 std::stack 模拟递归。

以二叉树的先序遍历为例，递归写法大家都会，用栈的迭代写法是这样的：

cpp复制std::vector<int> preorder(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

为什么先压右再压左？因为栈是 LIFO，先入栈的后出栈，为了让左孩子先被访问，只能把右孩子先压进去。这种“反直觉”的顺序正是递归转迭代的核心难点。同理，queue 做 BFS、stack 模拟 DFS，两者配合几乎能覆盖绝大多数树的遍历场景。

所以当你写出一个递归函数并且怀疑它可能爆栈时，先别急着调大栈空间，考虑一下用 std::stack 把它改写成迭代版本。这不仅是在学 STL 容器，也是在学一种通用的计算思维方式。

写在最后的一点个人体会

当年我学这两个容器适配器的时候，觉得接口太少了，没有什么值得钻研的地方，于是草草翻过，直接跳到算法题狂刷。结果第一次面试就被问到“为什么 stack 的默认容器是 deque 而不是 vector”，我支支吾吾答不上来，那种尴尬我到现在还记得。后来我重新翻开源码和文档，把 deque 的结构、适配器模式的来龙去脉、异常安全设计逐行理顺，才算是真正把这两个“小东西”装进了脑子里。

所以借着这篇文章，我真的建议你用同样认真的态度去对待每一个“看起来很简单”的知识点。stack<int> 背后是标准委员会对性能、安全、语义约束的层层权衡；queue<int> 也不只是一个 FIFO 队列，它是 BFS、任务调度、生产者消费者模型的地基。把简单的东西学透，复杂的东西自然会变得简单。