栈和队列

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、一个序列经过一个初始为空的队列后，元素的排列次序不变