本节内容
双端队列
王道考研/CSKAOYAN.COM双端队列
插入
1 2 3 4 5
删除
栈
:只允许从一端插入和删除的线性表
删除 1 2 3 4 5 插入
队列 若只使用其中
:只允许从一端插入、另一端删除的线性表
一端的插入、
删除操作,则
效果等同于栈
插入 插入
1 2 3 4 5
删除 删除
双端队列
:只允许从两端插入、两端删除的线性表
王道考研/CSKAOYAN.COM双端队列
插入 插入
1 2 3 4 5
删除 删除
双端队列:只允许从两端插入、两端删除的线性表
插入
1 2 3 4 5
删除 删除
输入受限的双端队列:只允许从一端插入、两端删除的线性表
插入 插入
1 2 3 4 5
删除
输出受限的双端队列:只允许从两端插入、一端删除的线性表
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
栈
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
栈
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
栈
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
栈
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
栈
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
14种合法
卡特兰数:
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
出栈序列
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1 1 1
$ !
𝐶 = 𝐶 = 14
#$ "
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2 n + 1 4 + 1
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24 删除
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输入受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3 栈中合法的序列,双
端队列中一定也合法
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24 删除
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输入受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
1 2 3 4
!
𝐴 = 4! = 24 删除
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输入受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入
!
𝐴 = 4! = 24 删除
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输入受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入 插入
1 3 2 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输出受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3 栈中合法的序列,双
端队列中一定也合法
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入 插入
2 1 3 4
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输出受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入 插入
1
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输出受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM考点:判断输出序列合法性
若数据元素输入序列为 1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
插入 插入
!
𝐴 = 4! = 24
删除
!
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
输出受限的双端队列
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,3 3,4,1,2 4,3,1,2
1,4,3,2 2,4,3,1 3,4,2,1 4,3,2,1
王道考研/CSKAOYAN.COM知识回顾与重要考点
在栈中合法的输出
序列,在双端队列
中必定合法
回忆:栈的变种——共享栈
王道考研/CSKAOYAN.COM