XP02 DAY6 栈、队列学习笔记
一、VECTOR 动态数组
1. 为什么要学习 VECTOR？
以前我们常用普通数组：
普通数组的特点是：
比如：
这个数组最多放 100 个整数。
如果后来发现需要放 200 个，就不够用了。
vector 可以理解为：
当我们需要更多空间时，它可以继续往后加元素。
2. VECTOR 的概念
vector 是 C++ STL 里面的一种容器。
初学时可以先这样理解：
普通数组：
vector：
3. 定义方式：一维 VECTOR
定义一个存整数的 vector：
意思是：
如果想一开始就有 n 个位置：
注意：
如果：
可以访问：
4. 定义方式：二维 VECTOR
二维 vector 可以理解为：
定义：
意思是：
比如：
表示：
5. 访问方式：下标访问
vector 可以像数组一样用下标访问。
注意：
6. 常用函数：PUSH_BACK
push_back 的作用：
例子：
此时 a 中的内容是：
7. 常用函数：POP_BACK
pop_back 的作用：
例子：
原来是：
删除最后一个后变成：
注意：
8. 常用函数：SIZE
size() 的作用：
例子：
输出：
9. 常用函数：CLEAR
clear() 的作用：
例子：
输出：
10. 常用函数：BACK 和 FRONT
back()：
front()：
例子：
注意：
11. 常用函数：BEGIN 和 END
begin() 和 end() 常用在排序中。
例如：
意思是：
初学时先记住这个写法即可。
12. VECTOR 完整小例子
输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、VECTOR 应用：约数表
1. 什么是约数？
如果一个数 x 能整除 n，那么 x 就是 n 的约数。
例如：
因为：
2. 什么是约数表？
约数表就是：
例如：
每个数的约数个数不一样。
比如：
所以用二维 vector 很方便。
3. 二维 VECTOR 存约数
含义：
例如：
5. 代码理解
这句：
表示：
比如 i = 3 时：
说明：
所以：
把 i 放进 j 的约数表里。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、STACK 栈
1. 栈的概念
栈是一种数据结构。
它的特点是：
也可以说：
英文常说：
简称：
2. 生活例子：一摞盘子
把盘子一个一个放到桌上：
拿盘子时，一般从最上面拿：
这就是：
3. STACK 的定义方式
定义一个存整数的栈：
意思是：
4. 栈只能访问栈顶
栈和数组不一样。
数组可以访问：
但是栈不能随便访问中间元素。
栈只能访问：
栈顶就是：
5. STACK 常用函数
函数 作用 push(x) 把 x 放入栈顶 pop() 删除栈顶元素 top() 查看栈顶元素 empty() 判断栈是否为空 size() 栈中元素个数
6. STACK 小例子
7. 栈的安全提醒
使用：
之前，最好先判断：
如果栈是空的，还去 top() 或 pop()，程序可能出错。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、STACK 应用：括号匹配
1. 什么是括号匹配？
判断一个括号字符串是否合法。
例如：
2. 为什么用栈？
括号是成对出现的。
而且：
例如：
第二个 ( 会先和第一个 ) 匹配。
这正好符合栈的特点：
3. 判断规则
从左到右扫描字符串：
如果遇到 ) 时栈是空的：
扫描完后，如果栈不为空：
否则合法。
4. 过程例子
字符串：
过程：
当前字符 操作 栈中内容 ( 入栈 ( ( 入栈 (( ) 弹出 ( ) 弹出 空
最后栈空，说明合法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、STACK 应用：火车进出站
1. 题目意思
给定火车入栈顺序：
再给一个出栈顺序，问这个顺序能不能实现。
例如：
我们要判断：
2. 核心思想
当前想让某个数字出栈。
如果栈顶就是它：
如果栈顶不是它：
如果所有火车都进栈了，栈顶还是不是它：
3. 模拟例子
入栈顺序：
目标出栈：
先想出 4：
再想出 5：
再想出 3：
最后 2、1 也能弹出。
所以合法。
六、QUEUE 队列
1. 队列的概念
队列和生活中的排队一样。
它的特点是：
也就是：
英文常说：
简称：
2. 生活例子：食堂排队
食堂窗口排队：
打饭顺序应该是：
这就是队列。
3. QUEUE 的定义方式
定义一个存整数的队列：
意思是：
4. 队列只能访问队首
队列不能随便访问中间元素。
它最常访问的是：
队首就是：
5. QUEUE 常用函数
函数 作用 push(x) 把 x 加到队尾 pop() 删除队首元素 front() 查看队首元素 empty() 判断队列是否为空 size() 队列中元素个数
6. QUEUE 小例子
7. 队列和栈的区别
容器 特点 生活例子 stack 先进后出 一摞盘子 queue 先来先出 排队打饭
简单记：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、QUEUE 应用：银行取号 1
1. 题目背景
银行有两类客户：
规则：
2. 为什么用两个队列？
因为：
所以可以开两个队列：
VIP 来了，就进 vip 队列。
普通客户来了，就进 normal 队列。
3. 办理业务时怎么选人？
每次窗口空了：
这就满足：
4. 简化代码
假设输入若干事件：
八、QUEUE 应用：银行取号 2
1. 和银行取号 1 的区别
银行取号 2 中，每个人办理业务的时间固定。
题目可能会要求：
所以我们除了维护队列，还要维护：
2. 需要哪些变量？
可以考虑：
含义：
3. 为什么最好先处理第一个人？
大纲中提醒：
意思是：
这样后面模拟会更清楚。
4. 模拟思路
每来一个事件时，先检查：
然后：
选人规则仍然是：
5. 这类题的重点
银行取号 2 难点不是队列函数，而是：
做题时建议先在纸上画表：
时间 事件 VIP 队列 普通队列 正在办理 1 VIP 5 来了 5 空 5 2 普通 8 来了 空 8 5 4 5 办完 空 8 8
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、综合应用：排队
1. 题目背景
这是 VIP 排队的扩展版。
这次不是简单分成 VIP 和普通客户，而是：
2. 为什么要给每个班级开一个队列？
因为每个班级内部也要保持顺序。
所以：
例如：
表示：
3. 还需要一个班级队列
除了每个班级自己的队列，还需要一个队列存：
例如：
里面存的是班级编号。
如果 line 中是：
表示：
4. 为什么需要桶记录班级？
大纲中说：
这句话可以拆成两件事：
第一件：
可以用数组：
belong[x] 表示同学 x 属于哪个班。
第二件：
可以用数组：
如果：
说明 c 班已经在总队列里。
5. 入队规则
如果同学 x 来了，先找到他的班级：
然后把他加入自己班级的队列：
如果这个班级之前不在总队列里：
6. 出队规则
办理时，先看总队列最前面的班级：
从这个班级队列中取一个人：
如果这个班级的人都走完了：
7. 综合排队题的理解
这题看起来复杂，其实只是在维护两层队列：
出队时：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、本节课总结
1. VECTOR
vector 是：
常用函数：
2. STACK
stack 是：
常用函数：
适合：
3. QUEUE
queue 是：
常用函数：
适合：
4. 栈和队列对比
容器 谁先出来 常见场景 stack 后进去的先出来 括号、火车、回退 queue 先进去的先出来 排队、取号、按顺序处理
