XP02 Day6 栈、队列学习笔记

一、vector 动态数组

1. 为什么要学习 vector？

以前我们常用普通数组：

int a[100];

普通数组的特点是：

大小一开始就固定了。

比如：

int a[100];

这个数组最多放 100 个整数。

如果后来发现需要放 200 个，就不够用了。

vector 可以理解为：

会自动变长的数组。

当我们需要更多空间时，它可以继续往后加元素。

2. vector 的概念

vector 是 C++ STL 里面的一种容器。

初学时可以先这样理解：

vector 就是一个可以变长的数组。

普通数组：

大小固定，不能随便变长。

vector：

可以不断 push_back 加入新元素。

3. 定义方式：一维 vector

定义一个存整数的 vector：

vector<int> a;

意思是：

a 是一个可以存很多 int 的动态数组。

如果想一开始就有 n 个位置：

vector<int> a(n);

注意：

vector 下标从 0 开始。

如果：

vector<int> a(5);

可以访问：

a[0], a[1], a[2], a[3], a[4]

4. 定义方式：二维 vector

二维 vector 可以理解为：

很多个 vector 排成一排。

定义：

vector<int> g[100];

意思是：

g[0], g[1], g[2] ... 每一个都是一个 vector<int>。

比如：

g[6].push_back(1);
g[6].push_back(2);
g[6].push_back(3);

表示：

6 这个位置后面存了 1、2、3。

5. 访问方式：下标访问

vector 可以像数组一样用下标访问。

vector<int> a;
a.push_back(10);
a.push_back(20);
a.push_back(30);

cout << a[0] << endl; // 10
cout << a[1] << endl; // 20
cout << a[2] << endl; // 30

注意：

a[0] 是第 1 个元素。
a[1] 是第 2 个元素。
a[2] 是第 3 个元素。

6. 常用函数：push_back

push_back 的作用：

在 vector 的最后加入一个元素。

例子：

vector<int> a;

a.push_back(5);
a.push_back(8);
a.push_back(10);

此时 a 中的内容是：

5 8 10

7. 常用函数：pop_back

pop_back 的作用：

删除 vector 最后一个元素。

例子：

vector<int> a;
a.push_back(5);
a.push_back(8);
a.push_back(10);

a.pop_back();

原来是：

5 8 10

删除最后一个后变成：

5 8

注意：

pop_back 只删除，不返回被删除的值。

8. 常用函数：size

size() 的作用：

返回 vector 里面有几个元素。

例子：

vector<int> a;
a.push_back(5);
a.push_back(8);

cout << a.size() << endl;

输出：

2

9. 常用函数：clear

clear() 的作用：

清空 vector 中的所有元素。

例子：

vector<int> a;
a.push_back(5);
a.push_back(8);

a.clear();

cout << a.size() << endl;

输出：

0

10. 常用函数：back 和 front

back()：

访问最后一个元素。

front()：

访问第一个元素。

例子：

vector<int> a;
a.push_back(5);
a.push_back(8);
a.push_back(10);

cout << a.front() << endl; // 5
cout << a.back() << endl;  // 10

注意：

使用 front 和 back 前，要保证 vector 里面有元素。

11. 常用函数：begin 和 end

begin() 和 end() 常用在排序中。

例如：

sort(a.begin(), a.end());

意思是：

把整个 vector 从小到大排序。

初学时先记住这个写法即可。

12. vector 完整小例子

#include <bits/stdc++.h>
using namespace std;

void solve() {
    vector<int> a;

    a.push_back(3);
    a.push_back(1);
    a.push_back(2);

    sort(a.begin(), a.end());

    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

输出：

1 2 3

---

二、vector 应用：约数表

1. 什么是约数？

如果一个数 x 能整除 n，那么 x 就是 n 的约数。

例如：

6 的约数有：1, 2, 3, 6

因为：

6 % 1 == 0
6 % 2 == 0
6 % 3 == 0
6 % 6 == 0

2. 什么是约数表？

约数表就是：

提前把每个数的约数都存起来。

例如：

divs[1] 存 1 的约数
divs[2] 存 2 的约数
divs[3] 存 3 的约数
divs[4] 存 4 的约数

每个数的约数个数不一样。

比如：

1 的约数：1
6 的约数：1 2 3 6
12 的约数：1 2 3 4 6 12

所以用二维 vector 很方便。

3. 二维 vector 存约数

vector<int> divs[100];

含义：

divs[i] 里面存 i 的所有约数。

例如：

divs[6].push_back(1);
divs[6].push_back(2);
divs[6].push_back(3);
divs[6].push_back(6);

5. 代码理解

这句：

for (int j = i; j <= n; j += i)

表示：

i 是 j 的约数。

比如 i = 3 时：

j = 3, 6, 9, 12, ...

说明：

3 是 3、6、9、12 的约数。

所以：

divs[j].push_back(i);

把 i 放进 j 的约数表里。

---

三、stack 栈

1. 栈的概念

栈是一种数据结构。

它的特点是：

先进后出。

也可以说：

后放进去的，先拿出来。

英文常说：

Last In First Out

简称：

LIFO

2. 生活例子：一摞盘子

把盘子一个一个放到桌上：

先放 1 号盘子
再放 2 号盘子
再放 3 号盘子

拿盘子时，一般从最上面拿：

先拿 3 号
再拿 2 号
最后拿 1 号

这就是：

先进后出。

3. stack 的定义方式

定义一个存整数的栈：

stack<int> s;

意思是：

s 是一个栈，里面可以存 int。

4. 栈只能访问栈顶

栈和数组不一样。

数组可以访问：

a[1], a[2], a[3]

但是栈不能随便访问中间元素。

栈只能访问：

栈顶元素。

栈顶就是：

最后放进去的那个元素。

5. stack 常用函数

函数	作用
push(x)	把 x 放入栈顶
pop()	删除栈顶元素
top()	查看栈顶元素
empty()	判断栈是否为空
size()	栈中元素个数

6. stack 小例子

#include <bits/stdc++.h>
using namespace std;

void solve() {
    stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.top() << endl; // 3
    s.pop();
    cout << s.top() << endl; // 2
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

7. 栈的安全提醒

使用：

s.top();
s.pop();

之前，最好先判断：

if (!s.empty()) {
    // 才能访问栈顶或弹出
}

如果栈是空的，还去 top() 或 pop()，程序可能出错。

---

四、stack 应用：括号匹配

1. 什么是括号匹配？

判断一个括号字符串是否合法。

例如：

()      合法
(())    合法
()()    合法
(()     不合法
)()     不合法

2. 为什么用栈？

括号是成对出现的。

而且：

越靠后的左括号，一定越先被右括号匹配。

例如：

( ( ) )

第二个 ( 会先和第一个 ) 匹配。

这正好符合栈的特点：

后进去的先出来。

3. 判断规则

从左到右扫描字符串：

遇到左括号 '('，入栈。
遇到右括号 ')'，尝试匹配一个左括号。

如果遇到 ) 时栈是空的：

说明没有左括号可以匹配，不合法。

扫描完后，如果栈不为空：

说明还有左括号没匹配，不合法。

否则合法。

4. 过程例子

字符串：

(())

过程：

当前字符	操作	栈中内容
(	入栈	(
(	入栈	((
)	弹出	(
)	弹出	空

最后栈空，说明合法。

---

五、stack 应用：火车进出站

1. 题目意思

给定火车入栈顺序：

1, 2, 3, ..., n

再给一个出栈顺序，问这个顺序能不能实现。

例如：

n = 5
出栈顺序：4 5 3 2 1

我们要判断：

能不能通过一个栈模拟出这个出站顺序。

2. 核心思想

当前想让某个数字出栈。

如果栈顶就是它：

直接出栈。

如果栈顶不是它：

继续把还没进站的火车压入栈。

如果所有火车都进栈了，栈顶还是不是它：

说明这个出栈顺序不可能。

3. 模拟例子

入栈顺序：

1 2 3 4 5

目标出栈：

4 5 3 2 1

先想出 4：

压入 1, 2, 3, 4
栈顶是 4，弹出

再想出 5：

压入 5
栈顶是 5，弹出

再想出 3：

栈顶是 3，弹出

最后 2、1 也能弹出。

所以合法。

六、queue 队列

1. 队列的概念

队列和生活中的排队一样。

它的特点是：

先来先出。

也就是：

先排队的人，先办理。

英文常说：

First In First Out

简称：

FIFO

2. 生活例子：食堂排队

食堂窗口排队：

小明先来
小红后到
小刚再后到

打饭顺序应该是：

小明 -> 小红 -> 小刚

这就是队列。

3. queue 的定义方式

定义一个存整数的队列：

queue<int> q;

意思是：

q 是一个队列，里面可以存 int。

4. 队列只能访问队首

队列不能随便访问中间元素。

它最常访问的是：

队首元素。

队首就是：

最早进入队列、现在排在最前面的人。

5. queue 常用函数

函数	作用
push(x)	把 x 加到队尾
pop()	删除队首元素
front()	查看队首元素
empty()	判断队列是否为空
size()	队列中元素个数

6. queue 小例子

#include <bits/stdc++.h>
using namespace std;

void solve() {
    queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    cout << q.front() << endl; // 1
    q.pop();
    cout << q.front() << endl; // 2
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

7. 队列和栈的区别

容器	特点	生活例子
stack	先进后出	一摞盘子
queue	先来先出	排队打饭

简单记：

栈：后来的先走。
队列：先来的先走。

---

七、queue 应用：银行取号 1

1. 题目背景

银行有两类客户：

VIP 客户
普通客户

规则：

VIP 客户内部按来的顺序办理。
普通客户内部也按来的顺序办理。
但是 VIP 总是排在普通客户前面。

2. 为什么用两个队列？

因为：

VIP 有自己的顺序。
普通客户也有自己的顺序。

所以可以开两个队列：

queue<int> vip;
queue<int> normal;

VIP 来了，就进 vip 队列。
普通客户来了，就进 normal 队列。

3. 办理业务时怎么选人？

每次窗口空了：

如果 vip 队列不空，先办理 vip。
否则办理普通客户。

这就满足：

VIP 总是排在普通客户前面。

4. 简化代码

假设输入若干事件：

1 x 表示 VIP 客户 x 来了
2 x 表示普通客户 x 来了
3 表示办理一个人

八、queue 应用：银行取号 2

1. 和银行取号 1 的区别

银行取号 2 中，每个人办理业务的时间固定。

题目可能会要求：

当前正在办理业务的人是谁？
什么时候办理结束？

所以我们除了维护队列，还要维护：

当前是否有人正在办理；
当前办理的人是谁；
当前业务什么时候结束。

2. 需要哪些变量？

可以考虑：

int nowPerson;
int finishTime;
bool busy;

含义：

nowPerson：当前正在办理的人。
finishTime：当前业务结束时间。
busy：窗口是否正在办理业务。

3. 为什么最好先处理第一个人？

大纲中提醒：

这个题最好先处理第一个人，因为第一个人一定要办理业务。

意思是：

一开始窗口是空的，第一个来到的人可以直接开始办理。

这样后面模拟会更清楚。

4. 模拟思路

每来一个事件时，先检查：

当前时间是否已经到了 finishTime。
如果到了，说明上一个人办理结束，窗口空了。

然后：

新来的客户进入对应队列。
如果窗口空了，就从队列中选下一个人开始办理。

选人规则仍然是：

VIP 优先；
VIP 没人再普通客户。

5. 这类题的重点

银行取号 2 难点不是队列函数，而是：

时间变化；
当前窗口状态；
正在办理的是谁。

做题时建议先在纸上画表：

时间	事件	VIP 队列	普通队列	正在办理
1	VIP 5 来了	5	空	5
2	普通 8 来了	空	8	5
4	5 办完	空	8	8

---

九、综合应用：排队

1. 题目背景

这是 VIP 排队的扩展版。

这次不是简单分成 VIP 和普通客户，而是：

每个同学属于一个班级。
同一个班级的同学要排在一起。
班级之间按第一个到来的同学顺序排队。

2. 为什么要给每个班级开一个队列？

因为每个班级内部也要保持顺序。

所以：

每个班级开一个队列，存这个班级正在排队的同学。

例如：

queue<int> cls[1000];

表示：

cls[1] 是 1 班队列
cls[2] 是 2 班队列
cls[3] 是 3 班队列

3. 还需要一个班级队列

除了每个班级自己的队列，还需要一个队列存：

当前有哪些班级在排队。

例如：

queue<int> line;

里面存的是班级编号。

如果 line 中是：

2 5 1

表示：

先办理 2 班，再办理 5 班，再办理 1 班。

4. 为什么需要桶记录班级？

大纲中说：

用桶维护每个同学的班级，以及当前班级是不是在队列里面。

这句话可以拆成两件事：

第一件：

知道每个同学属于哪个班级。

可以用数组：

int belong[100000];

belong[x] 表示同学 x 属于哪个班。

第二件：

知道某个班级现在是否已经在总队列里。

可以用数组：

bool inq[1000];

如果：

inq[c] == true

说明 c 班已经在总队列里。

5. 入队规则

如果同学 x 来了，先找到他的班级：

int c = belong[x];

然后把他加入自己班级的队列：

cls[c].push(x);

如果这个班级之前不在总队列里：

if (!inq[c]) {
    line.push(c);
    inq[c] = true;
}

6. 出队规则

办理时，先看总队列最前面的班级：

int c = line.front();

从这个班级队列中取一个人：

cout << cls[c].front() << endl;
cls[c].pop();

如果这个班级的人都走完了：

if (cls[c].empty()) {
    line.pop();
    inq[c] = false;
}

7. 综合排队题的理解

这题看起来复杂，其实只是在维护两层队列：

第一层：班级排队。
第二层：每个班级内部的同学排队。

出队时：

先确定当前排在最前面的班级；
再从这个班级里取最前面的同学。

---

十、本节课总结

1. vector

vector 是：

可以变长的数组。

常用函数：

push_back, pop_back, size, clear, back, front, begin, end

2. stack

stack 是：

先进后出。

常用函数：

push, pop, top, empty, size

适合：

括号匹配、火车进出站、需要看最近加入元素的问题。

3. queue

queue 是：

先来先出。

常用函数：

push, pop, front, empty, size

适合：

排队、银行取号、按先后顺序处理的问题。

4. 栈和队列对比

容器	谁先出来	常见场景
stack	后进去的先出来	括号、火车、回退
queue	先进去的先出来	排队、取号、按顺序处理