C++ 栈、队列与双端队列｜C++ 第 15 课

Easy explanation

盘子堆和候车队伍，代表两种完全不同的顺序。

餐厅把盘子一只只叠起来，最后放上的最先拿走，这就是后进先出；公交站最早到的人最先上车，这就是先进先出。选择数据结构其实是在选择规则，容器会限制不合适的操作，让代码更贴近现实问题。

stack 通常只看 top，queue 只看 front 和 back。它们故意不提供任意下标，因为中间元素不应被随意抽走。deque 则允许两端高效进出，可用来实现更灵活的窗口或双向任务。

目标 1理解 LIFO 与 FIFO 的行为差异

目标 2正确使用 stack、queue 和 deque

目标 3用栈完成括号匹配

目标 4用队列模拟任务与服务流程

C++ 栈、队列与双端队列通俗学习插图 — 数据的进入与离开顺序，直接决定最适合的容器。

Core concepts

先把四个核心知识点说清楚。

01

栈

stack<string> history;

push 压入顶部，top 查看顶部，pop 移除顶部，适合撤销、调用路径和嵌套结构。

02

队列

queue<Task> jobs;

push 从尾部加入，front 查看最早元素，pop 移除最早元素，适合公平排队。

03

双端队列

deque<int> window;

两端都能 push 和 pop，适合从两边处理或维护滑动范围。

04

空容器检查

if (!items.empty()) items.pop();

top、front 和 pop 前必须确认非空，否则程序行为无效。

undo.push(currentText);

修改前保存旧状态，撤销时恢复最后一次保存。

Task next = jobs.front(); jobs.pop();

先读取队首，再移除；pop 本身不返回元素。

window.push_back(value); window.pop_front();

固定长度窗口加入新值并移除最旧值。

while (!s.empty()) s.pop();

适配器没有 clear，可循环弹出或换一个空容器。

Complete examples

两个例子，把知识变成能运行的程序。

Example 1

例子一：检查括号是否正确配对

遇到左括号先保存；遇到右括号时，它必须与最近尚未匹配的左括号配对，所以检查栈顶。

右括号出现时栈为空说明缺少左括号；扫描结束栈仍不空说明缺少右括号。两种情况都要检查。

左括号入栈，右括号匹配栈顶

bool validBrackets(const string& text)
{
    stack<char> opened;
    for (char ch : text)
    {
        if (ch == '(' || ch == '[' || ch == '{') opened.push(ch);
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (opened.empty()) return false;
            char left = opened.top();
            opened.pop();
            if ((ch == ')' && left != '(') ||
                (ch == ']' && left != '[') ||
                (ch == '}' && left != '{')) return false;
        }
    }
    return opened.empty();
}

{a + [b * (c + d)]} -> 正确([)] -> 错误((x) -> 错误

Example 2

例子二：打印任务队列

每个任务包含名称和页数。最早提交的任务在队首，打印后从队列移除，直到全部完成。

总页数可以边处理边累计。若打印机暂停，不必改变队列顺序，下次继续取 front。

先进先出的处理循环

struct PrintJob { string name; int pages; };
queue<PrintJob> jobs;
jobs.push({"作业.pdf", 3});
jobs.push({"照片.png", 1});
jobs.push({"报告.pdf", 8});

int printed = 0;
while (!jobs.empty())
{
    PrintJob job = jobs.front();
    jobs.pop();
    cout << "正在打印：" << job.name << '\n';
    printed += job.pages;
}
cout << "总页数：" << printed << '\n';

正在打印：作业.pdf正在打印：照片.png正在打印：报告.pdf总页数：12

Algorithm thinking

先问“下一个应该处理谁”，再选容器。

若下一个总是最近加入的，使用栈；若下一个总是等待最久的，使用队列；若两端都可能加入或移除，考虑 deque。用 vector 也能模拟，但会开放不需要的操作，队首删除还可能移动大量元素。

容器操作通常是 O(1)，但完整算法仍可能遍历全部输入。例如括号匹配每个字符处理一次，是 O(n)。分析时既看单次操作，也看执行次数。

1
识别顺序规则
写出最近优先、最早优先或两端处理。
2
定义元素内容
任务不只有名字时，用 struct 把时间、优先级等放在一起。
3
保护读取操作
top 和 front 前检查 empty，明确空结构代表什么。
4
模拟小样本
用三到四个元素画出每次 push 和 pop 后的结构。

Common mistakes

这些错误很常见，学会自己排查。

1

空栈取 top

右括号可能先出现，匹配前必须检查栈是否为空。

2

以为 pop 返回元素

STL 的 pop 只删除，先用 top 或 front 复制需要的数据。

3

队首用 vector erase

频繁删除 vector 开头会移动后续元素，真正队列应使用 queue 或 deque。

4

只检查局部配对

扫描结束还要确认栈为空，否则可能剩下未闭合左括号。

本课通用调试法

先准备一个最小输入，只保留能够重现问题的几行数据；再在关键步骤输出变量值，确认程序究竟在哪一步偏离预期。编译错误从第一条开始处理，运行错误则比较“实际结果”和“期望结果”。修复后别只重跑原来的例子，还要增加空输入、边界值和错误输入，防止问题换一个形式再次出现。

Homework

第 15 课课后作业：从模仿到独立完成。

建议按顺序完成。前四题帮助巩固语法和基本操作，第五到第七题要求把多个知识点组合起来，第八题是小项目。每道题都要先写输入、处理、输出三行计划，再开始敲代码；程序运行后至少测试正常情况、边界情况和错误情况。

1

十进制转二进制

把除 2 得到的余数压栈，再弹出得到正确顺序，处理零。

2

文字撤销

每次修改前把旧文本压栈，实现最多五次 undo，并处理没有历史的情况。

3

括号报告

不仅返回真假，还输出第一个错误位置和期望的括号。

4

普通排队

模拟银行取号、叫号、取消和查看等待人数，空队列时提示。

5

循环队列游戏

玩家行动后回到队尾，生命值为零则不再入队，直到只剩一人。

6

滑动平均

用 deque 维护最近五个温度，加入新值后输出窗口平均值。

7

双端任务

普通任务加到尾部，紧急任务加到头部，每轮处理头部任务。

8

服务中心项目

模拟顾客排队、多个窗口处理、等待时间统计和暂停恢复，输出完整日志。

本课验收标准：能根据顺序解释为何选择栈、队列或 deque；所有读取前检查空容器；括号算法覆盖提前右括号和剩余左括号；队列项目保持正确服务顺序。

提交内容应包括源代码、三组测试输入与输出、一个曾经出现的错误及修复方法。最后请用自己的话解释本课最重要的概念；如果只能照着代码念，还需要再独立重写一次核心例子。

Lesson 15 summary

合适的数据结构，会把顺序规则直接写进程序。

stackqueuedequeLIFO / FIFO括号匹配

下一课学习 set 和 map。它们不按进入顺序解决问题，而是利用键快速判断是否存在、去重和统计频率。

进入第 16 课返回第 14 课查看课程大纲