查看“栈和队列”的源代码

https://www.bilibili.com/video/BV1hg411V7Bm?p=58
[[文件:栈和队列.png|无|缩略图|600x600像素]]



=== 队列（Queue） ===
[[文件:队列.png|无|缩略图|257x257像素]]
先进先出（FIFO——first in first out）

队尾（rear）进行插入操作

队头（front）进行删除操作



=== 栈（Stack） ===
[[文件:栈.png|无|缩略图|264x264像素]]先进先出（FILO——first in last out）

栈顶（top）：进行插入和删除操作的一端称为栈顶

栈底（bottom）：固定不变，不可进行插入和删除操作

进栈/压栈：Push the Stack

出栈/退栈/弹栈：Pop the Stack





例：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。
[[文件:出栈序列.png|无|缩略图|900x900像素]]
{| class="wikitable"
! colspan="5" |a<sub>in</sub>
|-
! colspan="2" |a<sub>out</sub>
! colspan="3" |b<sub>in</sub>
|-
! colspan="2" |b<sub>in</sub>
! colspan="2" |b<sub>out</sub>
!c<sub>in</sub>
|-
!b<sub>out</sub>
!c<sub>in</sub>
!a<sub>out</sub>
!c<sub>in</sub>
!c<sub>out</sub>
|-
!c<sub>in</sub>
!c<sub>out</sub>
!c<sub>in</sub>
!c<sub>out</sub>
!b<sub>out</sub>
|-
!c<sub>out</sub>
!b<sub>out</sub>
!c<sub>out</sub>
!a<sub>out</sub>
!a<sub>out</sub>
|}





这个问题适合倒推考虑，先列出所有可能的排列组合，然后按照目标的排列组合，

按照目标排列组合的顺序我们就知道哪个是后进栈的，

（因为后进先出，然后根据“元素按照a、b、c的次序入栈”，那么1个字母如果入栈了，那么它前面的字母也一定入过栈了，虽然可能已经出栈了也可能没出栈，看后面）





注意：

当有多个函数构成嵌套调用时（如：递归调用），按照“后调用先返回”的原则，函数之间的信息传递和控制转移可以用“栈”来实现。



=== 考点1：栈和队列的概念 ===
以下关于栈和队列的叙述中，错误的是（）。

A、栈和队列都是线性的数据结构

B、栈和队列都不允许在非端口位置插入和删除元素

C、一个序列经过一个初始为空的栈后，元素的排列次序一定不变  √

D、一个序列经过一个初始为空的队列后，元素的排列次序不变


=== 考点2：出栈序列判断 ===
若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替进行。

但不允许连续三次进行出栈操作，则不可能得到的出栈序列是（）。

A、dcebfa

B、cbdaef

C、bcaefd

D、afedcb  √

题解：

'''<big>指定元素要出栈，那么它前面的元素和它本身一定要先进栈</big>'''

I表示input，入栈

O表示output，出栈
{| class="wikitable"
|A
|I
a
|I
b
|I
c
|I
d
|'''<big>O</big>'''
'''<big>d</big>'''
|'''<big>O</big>'''
'''<big>c</big>'''
|I
e
|'''<big>O</big>'''
'''<big>e</big>'''
|'''<big>O</big>'''
'''<big>b</big>'''
|I
f
|'''<big>O</big>'''
'''<big>f</big>'''
|'''<big>O</big>'''
'''<big>a</big>'''
|无连续三次出栈（三连O）
|-
|B
|I
a
|I
b
|I
c
|'''<big>O</big>'''
'''<big>c</big>'''
|'''<big>O</big>'''
'''<big>b</big>'''
|I
d
|'''<big>O</big>'''
'''<big>d</big>'''
|'''<big>O</big>'''
'''<big>a</big>'''
|I
e
|'''<big>O</big>'''
'''<big>e</big>'''
|I
f
|'''<big>O</big>'''
'''<big>f</big>'''
|无连续三次出栈（三连O）
|-
|C
|I
a
|I
b
|'''<big>O</big>'''
'''<big>b</big>'''
|I
c
|'''<big>O</big>'''
'''<big>c</big>'''
|'''<big>O</big>'''
'''<big>a</big>'''
|I
d
|I
e
|'''<big>O</big>'''
'''<big>e</big>'''
|I
f
|'''<big>O</big>'''
'''<big>f</big>'''
|'''<big>O</big>'''
'''<big>d</big>'''
|无连续三次出栈（三连O）
|-
|D
|I
a
|'''<big>O</big>'''
'''<big>a</big>'''
|I
b
|I
c
|I
d
|I
e
|I
f
|'''<big>O</big>'''
'''<big>f</big>'''
|'''<big>O</big>'''
'''<big>e</big>'''
|'''<big>O</big>'''
'''<big>d</big>'''
|'''<big>O</big>'''
'''<big>c</big>'''
|'''<big>O</big>'''
'''<big>b</big>'''
|连续三次出栈（三连O）
|}
所以答案是选项D


=== 考点3：栈的用途 ===
函数调用和返回控制是用（）实现的。

A、哈希表

B、符号表

C、栈  √

D、优先队列


=== 总结 ===
栈和队列

* 队列：先进先出
* 栈：先进后出
** 出栈序列判断
** 用于函数调用