栈和队列
https://www.bilibili.com/video/BV1hg411V7Bm?p=58
队列（Queue）
先进先出（FIFO——first in first out）
队尾（rear）进行插入操作
队头（front）进行删除操作
栈（Stack）
先进先出（FILO——first in last out）
栈顶（top）：进行插入和删除操作的一端称为栈顶
栈底（bottom）：固定不变，不可进行插入和删除操作
进栈/压栈：Push the Stack
出栈/退栈/弹栈：Pop the Stack
例：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。
| ain | ||||
|---|---|---|---|---|
| aout | bin | |||
| bin | bout | cin | ||
| bout | cin | aout | cin | cout |
| cin | cout | cin | cout | bout |
| cout | bout | cout | aout | aout |
这个问题适合倒推考虑，先列出所有可能的排列组合，然后按照目标的排列组合，
按照目标排列组合的顺序我们就知道哪个是后进栈的，
（因为后进先出，然后根据“元素按照a、b、c的次序入栈”，那么1个字母如果入栈了，那么它前面的字母也一定入过栈了，虽然可能已经出栈了也可能没出栈，看后面）
注意：
当有多个函数构成嵌套调用时（如：递归调用），按照“后调用先返回”的原则，函数之间的信息传递和控制转移可以用“栈”来实现。
考点1：栈和队列的概念
以下关于栈和队列的叙述中，错误的是（）。
A、栈和队列都是线性的数据结构
B、栈和队列都不允许在非端口位置插入和删除元素
C、一个序列经过一个初始为空的栈后，元素的排列次序一定不变 √
D、一个序列经过一个初始为空的队列后，元素的排列次序不变
考点2：出栈序列判断
若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替进行。
但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（）。
A、dcebfa
B、cbdaef
C、bcaefd
D、afedcb √
题解：
指定元素要出栈，那么它前面的元素和它本身一定要先进栈
I表示input，入栈
O表示output，出栈
| A | I
a |
I
b |
I
c |
I
d |
O
d |
O
c |
I
e |
O
e |
O
b |
I
f |
O
f |
O
a |
无连续三次出栈（三连O） |
| B | I
a |
I
b |
I
c |
O
c |
O
b |
I
d |
O
d |
O
a |
I
e |
O
e |
I
f |
O
f |
无连续三次出栈（三连O） |
| C | I
a |
I
b |
O
b |
I
c |
O
c |
O
a |
I
d |
I
e |
O
e |
I
f |
O
f |
O
d |
无连续三次出栈（三连O） |
| D | I
a |
O
a |
I
b |
I
c |
I
d |
I
e |
I
f |
O
f |
O
e |
O
d |
O
c |
O
b |
连续三次出栈（三连O） |
所以答案是选项D
考点3：栈的用途
函数调用和返回控制是用（）实现的。
A、哈希表
B、符号表
C、栈 √
D、优先队列
总结
栈和队列
- 队列：先进先出
- 栈：先进后出
- 出栈序列判断
- 用于函数调用