“栈和队列”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
（建立内容为“https://www.bilibili.com/video/BV1hg411V7Bm?p=58”的新页面）
 
 
（未显示同一用户的19个中间版本）
第1行： 第1行：
 
https://www.bilibili.com/video/BV1hg411V7Bm?p=58
 
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、优先队列
 +
 +
 +
=== 总结 ===
 +
栈和队列
 +
 +
* 队列：先进先出
 +
* 栈：先进后出
 +
** 出栈序列判断
 +
** 用于函数调用

2022年9月18日 (日) 10:40的最新版本

https://www.bilibili.com/video/BV1hg411V7Bm?p=58

栈和队列.png


队列（Queue）

队列.png

先进先出（FIFO——first in first out）

队尾（rear）进行插入操作

队头（front）进行删除操作


栈（Stack）

栈.png

先进先出（FILO——first in last out）

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

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

进栈/压栈：Push the Stack

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



例：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。

出栈序列.png
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、优先队列


总结

栈和队列

  • 队列：先进先出
  • 栈：先进后出
    • 出栈序列判断
    • 用于函数调用
取自“https://www.jihongchang.top/index.php?title=栈和队列&oldid=2063”