夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt

查看资料信息、公开预览和下载状态。

共 142 页PDF · 2.0MB
下载

文档在线预览

公开展示前 10 页
100%
1
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第1页预览
2
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第2页预览
3
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第3页预览
4
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第4页预览
5
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第5页预览
6
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第6页预览
7
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第7页预览
8
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第8页预览
9
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第9页预览
10
《004-第四讲-录播_2026考研专业课_202026计算机_202026计算机_2026年启航计算机408_03.基础讲练_03.玩转数据结构_01.电子版ppt》第10页预览

本文档共 142 页 剩余 132 页未展示,请下载后查阅

下载

文档文本内容

第四讲:队列
主讲人:刘财政
B站:@计算机考研刘财政考纲要求CON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★CON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考纲框架
队列定义
队列的操作考点一: 队列的概念
排队的场景考点一: 队列的概念
【问题】 银行个人储户的储蓄业务。
【想法】 先来先服务原则,模拟排队,储户叫号后排在队尾,窗口顺次叫号。
如何保存正在等待的储户顺序?
用队列保存
在实际问题的处理过程中,有些数据具有先到先处理的特点考点一: 队列的概念
【问题】 多个用户共享打印机,保证打印功能。
【想法】 先来先服务原则,设置打印缓冲区,先送到缓冲区的先打印。
如何保存等待打印的文件? 用队列保存
在实际问题的处理过程中,有些数据具有先到先处理的特点操
考点一: 队列的概念
作
【问题】 上述的操作能否使用线性表来实现?
不
确
顺
定
序
链
性
表
线性表
表
移
遍
动
历
元
难
素考点一: 队列的概念
队列:只允许在表的一端进行插入操作,在另一端进行删除操作
线性表
端点1 端点2
队列只能选取一个端点进行插入操作,另一个端点进行删除操作考点一: 队列的概念
队列:只允许在表的一端进行插入操作,在另一端进行删除操作
(a , a , …, a , a )
1 2 n-1 n
a a … a a a … a
1 2 n 1 2 n
队头 队尾
队列 栈
队尾:允许插入的一端,相应地,位于队尾的元素称为队尾元素
队头:允许删除的一端,相应地,位于队头的元素称为队头元素考点一: 队列的概念
⚫ 进行插入的一端称做队尾(rear)。
⚫ 进行删除的一端称做队首或队头(front)。
⚫ 向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素。
⚫ 从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。
出队
进队
队头 队尾
队列示意图考点一: 队列的概念
假设:有三个元素按a、b、c的次序依次入队,且每个元素只允许进一
次队,则出队序列是什么?
答:出队序列只有一种情况:a b c
插入:入队、进队
出队 a b c 入队
删除:出队
空队列:不含任何数据元素的队列
任何时候执行出队操作,一定是哪个元素呢?
队列的操作特性:先进先出(First In First Out,FIFO)考点一: 队列的概念
队列的主要特点是先进先出,所以又把队列称为先进先出表。
例如:
只能按上桥的次序过桥
假如5个人过独木桥
这里独木桥就是一个队列考点一: 队列的概念
队列抽象数据类型=逻辑结构+基本运算(运算描述)
队列的基本运算如下:
 InitQueue(&q):初始化队列。构造一个空队列q。
 DestroyQueue(&q):销毁队列。释放队列q占用的存储空间。
 QueueEmpty(q):判断队列是否为空。若队列q为空,则返回真;否则返回假。
 enQueue(&q,e):进队列。将元素e进队作为队尾元素。
 deQueue(&q,&e):出队列。从队列q中出队一个元素,并将其值赋给e。考点一: 队列的概念
出队 入队
InitQueue
a a … a
1 2 n
输入:无
功能:初始化队列,创建一个空队列
输出:无
DestroyQueue
输入:无
功能:销毁队列,释放队列所占用的存储空间
输出:无
EnQueue
输入:元素值x
功能:在队尾插入一个元素
输出:如果插入成功,队尾增加了一个元素;否则返回失败信息考点一: 队列的概念
出队 入队
DeQueue
a a … a
1 2 n
前置条件:队列已存在
功能:删除队头元素
输出:如果删除成功,返回被删元素值;否则给出失败信息
GetQueue
输入:无
功能:读取队头元素
输出:若队列不空,返回队头元素;否则给出失败信息
Empty
输入:无
功能:判断队列是否为空
输出:如果队列为空,返回1,否则,返回0考点一: 队列的概念
队列中元素逻辑关系与线性表的相同,队列可以采用与线性表相同的存储结构。
逻辑结构
队列
顺序表 链 表
顺序队
链队 存储结构【政哥题型总结】考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
队列的特点是先进先出,栈的特点是后进先出,根据题意,元素入栈、出栈、
入队列、出队列。
由于队列是FIFO,并改变元素的顺序。
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g
4
Size = 2
3
2
b 1
top a 0考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g
4
Size = 1
3
2
b 1
top a 0考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g
4
Size = 3
3
2
d
c 1
top a 0考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g
4
Size = 1
3
2
d
c 1
top a 0考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
因此,入栈序列是a,b,c,d,e,f,g,出栈序列是b,d,c,f,e,a,g
4
Size = 3
3
f 2
1
e
top a 0考点一: 队列的概念
1.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S,若每个
元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容
量至少是( )。
A.1 B.2 C.3 D.4
C【解析】即出栈顺序是b,d,c,f,e,a,g,结合入栈顺序是a,b,c,d,e,f,g,可推出进
栈出栈顺序为
Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S
,e), Push(S,f),Pop(S,f),Pop(S,e), Pop(S,a), Push(S,g),Pop(S,g),栈内元素最
多为(a,c,d),(a,e,f)。假设初始所需容量为0,每做一次Push进行一次
“+1”操作,每做一次Pop进行一次“-1”操作,记录容量的最大值为3,故
选择C项。考点一: 队列的概念
2.允许对队列进行的操作有( )。
A.对队列中的元素排序
B.取出最后进队的元素
C.在队头元素之前插入元素
D.删除队头元素考点一: 队列的概念
2.允许对队列进行的操作有( )。
A.对队列中的元素排序
B.取出最后进队的元素
C.在队头元素之前插入元素
D.删除队头元素
D【解析】队列的基本操作有两个:①进队,在队尾插入元素;②出队,将队首
元素删除。THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点二:顺序队列的定义
顺序队列:队列的顺序存储结构 例:aaaa依次入队
1 2 3 4
0 1 2 3 4
a a a a
1 2 3 4
rear
如何改造数组实现队列的顺序存储? 入队操作的时间性能?
如何表示队头:用数组的一端作为队头,从下标 0 处开始存放
如何表示队尾:设变量rear存储队尾元素所在的下标的下一个
位置考点二:顺序队列的定义
顺序队列:队列的顺序存储结构
队列
逻辑结构
(a,a,…,a,…,a)
1 2 i n
直接映射
0 f f+1 r MaxSize-1
存储结构
… a … a … … f r
1 n
data
front rear
顺序队的示意图考点二:顺序队列的定义
顺序队列:队列的顺序存储结构
例:aa依次出队
1 2
0 1 2 3 4
a a a a
1 2 3 4
rear
如何改造数组实现队列的顺序存储?
如何表示队头:用数组的一端作为队头,从下标 0 处开始存放
如何表示队尾:设变量rear存储队尾元素所在的下标的下一个
位置考点二:顺序队列的定义
顺序队列:队列的顺序存储结构
例:aa依次出队
1 2
0 1 2 3 4
a a a
2 3 4
rear
如何改造数组实现队列的顺序存储? 出队操作的时间性能?
如何表示队头:用数组的一端作为队头,从下标 0 处开始存放
如何表示队尾:设变量rear存储队尾元素所在的下标的下一个
位置考点二:顺序队列的定义
如何改进出队操作的时间性能? 例:aa依次出队
1 2
0 1 2 3 4
a a a a
1 2 3 4
front rear
入队、出队时间性能均是O(1)
设置队头、队尾两个位置指针
约定:队头front指向队头元素,队尾rear指向队尾元素的后一个位置考点二:顺序队列的定义
队列的移动有什么特点? 例:aa依次出队
1 2
0 1 2 3 4
a a a
2 3 4
front rear
整个队列向数组下标较大方向移动 单向移动性考点二:顺序队列的定义
顺序队列:队列的顺序存储结构
顺序队类型SqQueue声明如下:
#define QUEQUESIZE 100
typedef int ElemType;
typedef struct queue {
ElemType data[QUEQUESIZE];
int front; // 指向队头元素
int rear; // 指向队尾元素的下一个位置
} SqQueue;
因为队列两端都在变化,所以需要两个指针来标识队列的状态。THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(1)顺序队列的初始化,顺序队列的初始化时,队列是空的,数组的下标是
0~ MAX_QUEUE_SIZE-1,此时front和rear均指向下标0的位置。考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(1)队列中有4个元素a ,a ,a ,a ,此时front执行队首元素a ,rear指向队尾
1 2 3 4 1
元素a 的下一个空位置
4考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(2)入队操作:先让放入元素,再rear++;,先将a 放入到下标4的位置,也
5
就是Queue_array[rear],再将rear从4加到5考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(3)出队操作:先出元素,再front++;此时front是0,先取出下标为front
的元素,也就是Queue_array[front],再让front++,front变为1考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(4)队列空的条件:我们在前面讲述ont指向队首元素,rear执行队尾元素的下
一个空位置,当front == rear时,表示队列为空。考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(5)队列满和假溢出。当a ,a ,a ,a ,a ,a ,a ,a ,a ,a 依次入队,此时rear执行
1 2 3 4 5 6 7 8 9 10
位置10,队列满了,于是当rear == MAX_QUEUE_SIZE,队列满。考点三:顺序队列的性质和操作
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
(6)在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元
素的下一位置。
顺序队列中存在“假溢出”现象。尽管队列中实际元素个数可能远远小于
数组大小,但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现
象称为假溢出。THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点四: 循环队列的定义
数组的大小设置为10,也就是下标是0~9,元素是a ,a ,a ,a ,a ,a ,a ,a ,a ,a 。
1 2 3 4 5 6 7 8 9 10
【当队列不空时,front指向队首元素,rear执行队尾元素的下一个空位置】
在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元
素的下一位置。
顺序队列中存在“假溢出”现象。尽管队列中实际元素个数可能远远小于
数组大小,但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现
象称为假溢出。考点四: 循环队列的定义
为充分利用空间,克服上述“假溢出”现象的方法是:将为队列分
配的向量空间看成为一个首尾相接的圆环【逻辑上循环】,并称这种队
列为循环队列;
有循环队列QU[0,5],其初始状态是front=rear=0,
rear
front
1
0
5 2
3
4
循环队列考点四: 循环队列的定义
把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储
队列元素的表从逻辑上看成一个环,称为环形队列或循环队列。
a
例
rear c 4
如
2 front
3 b
b 3
1
2
a
4
0
front 1
c
0
rear
当rear=4时,不能再进队
当rear=4时,下一步到位置0,可以进队考点四: 循环队列的定义
a
2 front
b
3
1
4
0
c
rear
这种循环意义下的加1操作可以描述为:
if (i+1 == QUEQUESIZE )
i = 0;
else
i++ ;
其中: i代表队首指针(front)或队尾指针(rear)
用模运算可简化为:i=(i+1) % QUEQUESIZE ;考点四: 循环队列的定义
0 1 2 3 4
循环队列的存储结构定义
a a a
2 3 4
front rear
#define QUEQUESIZE 100
typedef int ElemType;
typedef struct queue {
ElemType data[QUEQUESIZE];
int front; // 指向队头元素
int rear; // 指向队尾元素的下一个位置
} SqQueue;
因为队列两端都在变化,所以需要两个指针来标识队列的状态。考点四: 循环队列的定义
0 1 2 3 4
循环队列的存储结构定义
a a a
2 3 4
front rear
#define QUEQUESIZE 100
typedef int ElemType;
typedef struct queue {
ElemType data[QUEQUESIZE];
int front; // 指向队头元素
int rear; // 指向队尾元素的下一个位置
} SqQueue;
因为队列两端都在变化,所以需要两个指针来标识队列的状态。考点四: 循环队列的定义
b
2
c
3
1 a
4
0
d
front
rear
实际上内存地址一定是连续的,不可能是环形的,这里是通过逻辑方
式实现环形队列,也就是将rear++和front++改为:
⚫ rear=(rear+1)% QUEQUESIZE
⚫ front=(front+1)% QUEQUESIZE考点四: 循环队列的定义
循环队列的基本运算
b
2
2 c front
3
1 a
3
1
4
0
4
0
rear
front
rear (b)a、b、c进队
(a)空队考点四: 循环队列的定义
循环队列的基本运算
front
b
2
3
2 1
c
3
1
4
0
4
0
front
rear
rear
(d)出队2次
(c)出队一次考点四: 循环队列的定义
现在约定rear=front为队空,以下两种情况都满足该条件:
2 2
3 3
1 1
4
4 0 0
front
front
rear rear
初始状态
进队的所有元素均出队
那么如何设置队满的条件呢?考点四: 循环队列的定义
入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故
队空和队满时头尾指针均相等。因此,无法通过front=rear来判断队列
“空”还是“满”。
front
b
2
3 2
rear a
1
3
1
c
4
0
4
0
e
d
front
rear
满状态
空状态考点四: 循环队列的定义
为了区别循环队列的空和满状态,共有三种方法,
(1)设置初始标记: bool flag=false
①当入队列时,让rear往后移动,让flag=true
②当出队列时,让front往后移动,让flag=false
③当队列为空时: rear == front && flag==false
④当队列为满时: rear == front && flag == true
(2)计数len表示队列中有效元素个数
①当队列为空时,len== 0
②当有元素入队时,len++,当len和队列的QUEQUESIZE相等时,代表队列已满
(3)牺牲一个单元法
我们约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满。
①当循环队列为空:front==rear 。
②当循环队列满:(rear+1) % QUEQUESIZE ==front。考点四: 循环队列的定义
环形队列的三种实现方式:
方式一:在非空队列里,队首指针始终指向队头元素,而队尾指针始
终指向队尾元素的下一位置。
rear
2
3
1 b
4
0
a
front
非空状态考点四: 循环队列的定义
环形队列的三种实现方式:
方式一:在非空队列里,队首指针始终指向队头元素,而队尾指针始
终指向队尾元素的下一位置。
⚫ 初始化: front = rear = 0
⚫ 在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元
素的下一位置。。
⚫ 队空条件:front = rear
⚫ 队满条件:(rear+1)% QUEQUESIZE = front
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len = (rear – front + QUEQUESIZE ) % QUEQUESIZE考点四: 循环队列的定义
已知front、rear,求队中元素个数len = ?
front
2 rear
3
1
c
4
0
a
b
len =(1-3)=-2 
len =(1-3+ QUEQUESIZE)=3
len =(1-3+ QUEQUESIZE)% QUEQUESIZE =3 考点四: 循环队列的定义
已知front、rear,求队中元素个数len = ?
MaxSize=5
b
rear
2
c
3
1 a
4
0
front
len=(3-0)=3
len=rear-front ?
len=(3-0+ QUEQUESIZE)=8 
len=(3-0+ QUEQUESIZE)% QUEQUESIZE =3 考点四: 循环队列的定义
环形队列的三种实现方式:
方式二:在非空队列里,队首指针始终指向队头元素的前一个位置,而
队尾指针始终指向队尾元素。
rear
2
3
1 b
4
0
a
front
非空状态考点四: 循环队列的定义
环形队列的三种实现方式:
方式二:在非空队列里,队首指针始终指向队头元素的前一个位置,而
队尾指针始终指向队尾元素。
⚫ 初始化: front = rear = 0
⚫ 在非空队列里,队首指针始终指向队头元素的前一个位置,而队尾指针
始终指向队尾元素。
⚫ 队空条件:front = rear
⚫ 队满条件:(rear+1)% QUEQUESIZE = front
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len = (rear – front + QUEQUESIZE ) % QUEQUESIZE考点四: 循环队列的定义
环形队列的三种实现方式:
方式三:在非空队列里,队首指针始终指向队头元素,而队尾指针始终
指向队尾元素。【加入len表示元素个数】
rear
2
3
1 b
4
0
a
front
非空状态考点四: 循环队列的定义
环形队列的三种实现方式:
方式三:在非空队列里,队首指针始终指向队头元素,而队尾指
针始终指向队尾元素。
⚫ 在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队
尾元素。
⚫ 队空条件:len = 0;
⚫ 队满条件:len = QUEQUESIZE ;
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len【政哥题型总结】考点四: 循环队列的定义
1、设循环队列中数组的下标是0~N-1,其队头队尾指针分别为f和r (f指向队
首元素的前一位置,r指向队尾元素),则其元素个数为________。
A.r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N考点四: 循环队列的定义
1、设循环队列中数组的下标是0~N-1,其队头队尾指针分别为f和r (f指向队
首元素的前一位置,r指向队尾元素),则其元素个数为________。
A.r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N
⚫ 在非空队列里,f指向队首元素的前一位置,r指向队尾元素。
⚫ 队空条件:front = rear
⚫ 队满条件:(rear+1)% QUEQUESIZE = front
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len = (rear – front + QUEQUESIZE ) % QUEQUESIZE考点四: 循环队列的定义
1、设循环队列中数组的下标是0~N-1,其队头队尾指针分别为f和r (f指向队
首元素的前一位置,r指向队尾元素),则其元素个数为________。
A.r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N
D【解析】加入新元素时,循环队列可以用来解决假溢出问题, 当队列后面的满
了,就从头在开始,形成头尾相接的循环。存在两种情况:
(1)当rear大于front时,循环队列的长度:rear-front。
(2)当rear小于front时,循环队列的长度:分为两部分计算rear-0和N-front。将
两部分的长度合并到一起即为: rear-front+N。两种情况合为一种,元素个数
等于总长度,是(rear-front+N)% N。题目中队列存储空间为N,队头f,队尾r。
因此元素个数为(r-f+N)%N考点四: 循环队列的定义
2、设C语言数组 Data[m+1]作为循环队列的存储空间,front为队头指针,
rear为队尾指针,则执行出队操作的语句为
A. front=front+1 B. front=(front+1)%m
C. rear=(rear+1) %m D. front=(front+1)%(m+1)考点四: 循环队列的定义
2、设C语言数组 Data[m+1]作为循环队列的存储空间,front为队头指针,
rear为队尾指针,则执行出队操作的语句为
A. front=front+1 B. front=(front+1)%m
C. rear=(rear+1) %m D. front=(front+1)%(m+1)
⚫ 在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元素
的下一位置。
⚫ 队空条件:front = rear
⚫ 队满条件:(rear+1)% QUEQUESIZE = front
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len = (rear – front + QUEQUESIZE ) % QUEQUESIZE考点四: 循环队列的定义
2、设C语言数组 Data[m+1]作为循环队列的存储空间,front为队头指针,
rear为队尾指针,则执行出队操作的语句为
A. front=front+1 B. front=(front+1)%m
C. rear=(rear+1) %m D. front=(front+1)%(m+1)
D【解析】入队操作:rear=(rear+1)%MAX_QUEUE_SIZE。大家注意这个题,
循环队列存储在数组Data[0..m]中,其空间大小为m+1。考点四: 循环队列的定义
3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0
和3。则从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和1考点四: 循环队列的定义
3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0
和3。则从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和1
front
2
a
3
1
4
0
b
rear
初始状态考点四: 循环队列的定义
3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0
和3。则从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和1
front
a 2 2
3 3
1 1
4 0 4 0
b b
front
rear rear
初始状态 删除一个元素考点四: 循环队列的定义
3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0
和3。则从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和1
rear
2
3 2
1
3
1
d
4
0
4
b 0
b
c
front
rear front
加入两个元素
删除一个元素考点四: 循环队列的定义
3.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0
和3。则从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和1
B【解析】循环队列中,先删除一个元素,即队头元素出队,队头指针加1,
front=(front+1) % QUEQUESIZE = (3+1) % 6 = 4;再加入一个元素,队尾指
针加1,rear=(rear+1) % QUEQUESIZE = (0+1) % 6 = 1;最后加入一个元素,
队尾指针加1,rear = (rear+1) % QUEQUESIZE = (1+1) % 6 = 2。考点四: 循环队列的定义
4、若循环队列以数组 Q[0..m-1]作为其存储结构,变量 rear 表示循环
队列中的队尾元素 的实际位置,其移动按 rear=(rear+1) Mod m 进行,
变量 length 表示当前循环队列 中的元素个数,则循环队列的队首元素
的实际位置是( )
A.rear-length B.(rear-length+m) Mod m
C.(1+rear+m-length) Mod m D.M-length考点四: 循环队列的定义
环形队列的三种实现方式:
方式二:在非空队列里,队首指针始终指向队头元素的前一个元素,而队
尾指针始终指向队尾元素。
rear
2
3
1 b
4
0
a
front
非空状态考点四: 循环队列的定义
⚫ 初始化: front = rear = 0
⚫ 在非空队列里,队首指针始终指向队头元素的前一个元素,而队尾指针
始终指向队尾元素。
⚫ 队空条件:front = rear
⚫ 队满条件:(rear+1)% QUEQUESIZE = front
⚫ 进队e操作:rear=(rear+1)% QUEQUESIZE; 将e放在rear处
⚫ 出队操作:front=(front+1)% QUEQUESIZE; 取出front处元素e;
⚫ 元素个数:len = (rear – front + QUEQUESIZE ) % QUEQUESIZE考点四: 循环队列的定义
4、若循环队列以数组 Q[0..m-1]作为其存储结构,变量 rear 表示循环
队列中的队尾元素的实际位置,其移动按 rear=(rear+1) Mod m 进行,
变量 length 表示当前循环队列中的元素个数,则循环队列的队首元素
的实际位置是( )
A.rear-length B.(rear-length+m) Mod m
C.(1+rear+m-length) Mod m D.M-length
⚫ 元素个数:len = (rear – front +
rear
2
QUEQUESIZE ) % QUEQUESIZE
3
1 b
⚫ 于是:front = (rear –len +
4
0
QUEQUESIZE ) % QUEQUESIZE
a
front
非空状态考点四: 循环队列的定义
4、若循环队列以数组 Q[0..m-1]作为其存储结构,变量 rear 表示循环
队列中的队尾元素的实际位置,其移动按 rear=(rear+1) Mod m 进行,
变量 length 表示当前循环队列中的元素个数,则循环队列的队首元素
的实际位置是( )
A.rear-length B.(rear-length+m) Mod m
C.(1+rear+m-length) Mod m D.M-length
⚫于是:front = (rear –len + rear
2
QUEQUESIZE ) % QUEQUESIZE 3
1 b
⚫首元素的实际位置 = (front + 1) %
4
0
QUEQUESIZE
a
front
非空状态考点四: 循环队列的定义
4、若循环队列以数组 Q[0..m-1]作为其存储结构,变量 rear 表示循环
队列中的队尾元素的实际位置,其移动按 rear=(rear+1) Mod m 进行,
变量 length 表示当前循环队列中的元素个数,则循环队列的队首元素
的实际位置是( )
A.rear-length B.(rear-length+m) Mod m
C.(1+rear+m-length) Mod m D.M-length
⚫于是:front = (rear –len + rear
2
QUEQUESIZE ) % QUEQUESIZE
3
1 b
⚫首元素的实际位置 = (1+rear+m-
4
0
length) mod m
a
front
非空状态THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点五: 循环队列的操作
循环队列的操作,需要额外提示的两个注意点是:
(1)入队,需要先判断队列是不是已经存满
(2)出队,需要先判断队列是否是已经空考点五: 循环队列的操作
循环队列的初始化
void InitQueue(SqQueue& q) {
q.front = 0;
q.rear = 0;
}考点五: 循环队列的操作
入队的函数
EnQueue
输入:元素值 e
功能:在队尾插入一个元素
输出:如果插入成功,队尾增加了一个元素;否则返回失败信息
插入操作是否成功
操作接口: bool EnQueue(SqQueue& q, ElemType e)考点五: 循环队列的操作
0 1 2 3 4
入队的函数
a a e
3 4
// 成功,返回true
// 失败,返回false
rear
front
bool EnQueue(SqQueue& q, ElemType e) {
if ((q.rear + 1) % QUEQUESIZE == q.front) {
return false; // 队列满
}
q.data[q.rear] = e; // 元素e入队
q.rear = (q.rear + 1) % QUEQUESIZE; // 队尾指针循环加1
return true;
}考点五: 循环队列的操作
出队的函数
DeQueue
前置条件:队列已存在
功能:删除队头元素
输出:如果删除成功,返回被删元素值;否则给出失败信息
删除操作是否成功
操作接口: bool DeQueue(SqQueue& q, ElemType& e)考点五: 循环队列的操作
0 1 2 3 4
出队的函数
a a a
2 3 4
// 成功,返回true
// 失败,返回false front rear
bool DeQueue(SqQueue& q, ElemType& e) {
if (q.front == q.rear) {
return false; // 队列为空
}
e = q.data[q.front]; // 队头元素出队
q.front = (q.front + 1) % QUEQUESIZE; // 队头指针循环加1
return true;
}THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考纲框架
队头指针 front 队尾指针 rear
两类结点
数据结点
入队:尾插
基础操作
出队: 头插
链式队列
入队:尾插;尾改头不改
基本要点 出队:头出:头改尾不改
Attention:最后一个元素,头尾都要改
初始化:定义头尾指针
基本代码
入队:尾插;尾改头不改
出队:头出;头改尾不改考点六: 链队列的定义
链队列:队列的链接存储结构
队列
逻辑结构 (a,a,…,a,…,a)
1 2 i n
映射
队头 队尾
存储结构
a a … a ∧
1 2 n
队尾指针
队头指针
链队示意图考点六: 链队列的定义
通常将队头和队尾两个指针合起来:
q
队头 队尾
…
front a a a ∧
1 2 n
rear
链队组成:
(1)存储队列元素的单链表结点
(2)指向队头和队尾指针的链队结点考点六: 链队列的定义
链队列:队列的链接存储结构
head
a a a a
1 2 i n ∧
front rear
P:用链表的哪一端作为队头?哪一端作为队尾?
A:链头作为队头,出队时间为O(1)
设置队尾指针rear
链尾作为队尾,入队时间为O(n)
P:链队列需要加头结点吗?考点六: 链队列的定义
链队的进队和出队操作演示
q
front ∧
(a)空队
rear ∧
q
队头 队尾
(b)a、b、c进队 front a b c ∧
rear
q
front b c ∧
(c)出队一次
rear考点六: 链队列的定义
单链表中数据结点类型DataNode声明如下:
typedef int ElemType;
typedef struct QNode {
ElemType data; // 数据域
struct QNode* next; // 指针域
} QNode;
链队结点类型LinkQuNode声明如下:
typedef struct LinkQueue {
QNode* front; // 队头指针
QNode* rear; // 队尾指针
} LinkQueue;THANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点七: 链队列的操作
链队列的实现方式
链队列是“头出尾插”的单链表,链队的操作实际上是单链表的操作,只不过
是删除在表头进行,插入在表尾进行。在具体实现时,有带头结点和不带头结
点的两种方式
(1)带头结点的链队列
空队列时,front和rear均指向头结点,请大家注意,front是头指针,rear是
尾指针。考点七: 链队列的操作
链队列的实现方式
(1)带头结点的链队列
将x所在的结点入队列(尾插;尾插法),对应的操作是:(插入操作,改尾,
不改头) p->next = rear ->next; rear->next = p;考点七: 链队列的操作
链队列的实现方式
(1)带头结点的链队列
将y所在的结点入队列(尾插法哟),对应的操作是(插入操作,改尾,不改
头):p->next = rear ->next; rear->next = p;考点七: 链队列的操作
链队列的实现方式
(1)带头结点的链队列
将x所在的结点出队列(头出),对应的操作是(删除操作,改头,不改尾):
p = front->next; front->next = p->next; free(p);考点七: 链队列的操作
链队列的实现方式
(1)带头结点的链队列
将y所在的结点出队列(头出),请注意此时队列中只有一个元素,对应的操
作是(当删除最后一个元素时,头尾都要改):p = front-next;front-next
= null; rear->next = null;(头尾的下一个结点,都置为空);考点七: 链队列的操作
链队列的实现方式
(1)不带头结点的链队列
空队列时,front和rear均指向NULL,大家注意,front是头指针,rear是尾指针。考点七: 链队列的操作
链队列的实现方式
(1)不带头结点的链队列
将x所在的结点入队列(尾插;尾插法),对应的操作是:(插入操作,改尾,
也改头,因为初始状态下front和rear均指向NULL) front ->next = rear->next
= p;考点七: 链队列的操作
链队列的实现方式
(1)不带头结点的链队列
将y所在的结点入队列(尾插;尾插法),对应的操作是(插入操作,改尾,不
改头):p->next = rear ->next; rear->next = p;考点七: 链队列的操作
链队列的实现方式
(1)不带头结点的链队列
将x所在的结点出队列(头出),对应的操作是(删除操作,改头,不改尾):
p = front->next; front->next = p->next; free(p);考点七: 链队列的操作
链队列的实现方式
(1)不带头结点的链队列
将y所在的结点出队列(头出),请注意此时队列中只有一个元素,对应的操作
是(当删除最后一个元素时,头尾都要改):p = front->next;front = rear
= NULL;(头尾都置为空);【政哥题型总结】考点七: 链队列的操作
1.在一个链队列中,设f和r分别为队首和队尾指针,则插入s所指结点的运算
是( )。
A.r->next=s;r=s
B.r->next=s;s->next=NULL;r=s
C.s->next=r;r=s
D.s->next=f;f=s考点七: 链队列的操作
1.在一个链队列中,设f和r分别为队首和队尾指针,则插入s所指结点的运算
是( )。
A.r->next=s;r=s
B.r->next=s;s->next=NULL;r=s
C.s->next=r;r=s
D.s->next=f;f=s
链式队列的插入是尾插法,
q
队头 队尾
front a b
rear
c ∧考点七: 链队列的操作
1.在一个链队列中,设f和r分别为队首和队尾指针,则插入s所指结点的运算
是( )。
A.r->next=s;r=s
B.r->next=s;s->next=NULL;r=s
C.s->next=r;r=s
D.s->next=f;f=s
链式队列的插入是尾插法,
q
队头 队尾
front a b c ∧
rear考点七: 链队列的操作
1.在一个链队列中,设f和r分别为队首和队尾指针,则插入s所指结点的运算
是( )。
A.r->next=s;r=s
B.r->next=s;s->next=NULL;r=s
C.s->next=r;r=s
D.s->next=f;f=s
B【解析】链队列是头出尾插的单链表,要插入结点,执行尾插操作(尾插法),
其中r是尾指针,于是有r->next=s;s->next=NULL;r=s。考点七: 链队列的操作
2.若用单链表来表示队列,则应该选用( )。
A.带头指针的非循环链表 B.带头指针的循环链表
C.带尾指针的非循环链表 D.带尾指针的循环链表考点七: 链队列的操作
2.若用单链表来表示队列,则应该选用( )。
A.带头指针的非循环链表 B.带头指针的循环链表
C.带尾指针的非循环链表 D.带尾指针的循环链表
队列的链式存储结构简称为链队列,它是限制仅在表头进行删除操作和表尾进
行插入操作的单链表。
front x y ∧
rear
头出尾插的单链表;需要方便的寻找头和尾考点七: 链队列的操作
2.若用单链表来表示队列,则应该选用( )。
A.带头指针的非循环链表 B.带头指针的循环链表
C.带尾指针的非循环链表 D.带尾指针的循环链表
A B C D
头出 O(1) O(1) O(n) O(1)
尾插 O(n) O(n) O(1) O(1)考点七: 链队列的操作
2.若用单链表来表示队列,则应该选用( )。
A.带头指针的非循环链表 B.带头指针的循环链表
C.带尾指针的非循环链表 D.带尾指针的循环链表
D【解析】链队列是头出尾插的单链表,其要求是方便找到头和尾。为了便于
操作,都是给定循环链表,一般有以下两种情况。
(1)若是单链表,一般给定带尾指针的循环单链表。
(2)若是双链表,一般给定带头指针或尾指针的循环双链表。考点七: 链队列的操作
链队列的操作
(1)、链队列的初始化
构造一个空队列,即只创建一个链队头结点,其front和rear域均置为NULL,
不创建数据元素结点。
// 成功,返回true
// 失败,返回false
bool InitQueue(LinkQueue& q) {
q.front = q.rear = (QNode*)malloc(sizeof(QNode));
if (!q.front) {
return false;
}
q.front->next = NULL;
return true;
}考点七: 链队列的操作
链队列的操作
(2)入队EnQueue( q,e )
链队列的入队操作;插入操作一般不用判断队列是否满。
考虑情况:
⚫ 原队列为空
⚫ 原队列非空考点七: 链队列的操作
链队列的操作
// 成功,返回true
// 失败,返回false
bool EnQueue(LinkQueue& q, ElemType e) {
QNode* p = (QNode*)malloc(sizeof(QNode));
if (!p) {
return false;
}
p->data = e; // 设置新结点
p->next = NULL;
q.rear->next = p;
q.rear = p; // 尾插法,将新结点插入到队尾
return true;
}
q
p
a a … a ∧
1 2 n
e考点七: 链队列的操作
链队列的操作
(3)出队EnQueue( q,e )
链队列的出队操作;插入操作首先要判断队列是否为空,(虽然链队列不存在
队列满的情况,但是存在队列为空的情况);同时需要判断是否删除的是最后
一个元素。考点七: 链队列的操作
链队列的操作
// 成功,返回true
// 失败,返回false
bool DeQueue(LinkQueue& q, ElemType& e) {
if (q.front == q.rear) {
return false; // 队列为空
}
QNode* p = q.front->next;
e = p->data;
q.front->next = p->next; // 删除队头结点
if (q.rear == p) {
q.rear = q.front; // 当前队列只有一个结点时防止尾指针丢失
}
free(p);
return true; p 删除
} q
…
a a a ∧
1 2 nTHANKSCON T EN T S
目录
考点一 队列的概念 ★★
考点二 顺序队列的定义
考点三 顺序队列的性质和操作 ★★★
考点四 循环队列的定义 ★★★★
考点五 循环队列的操作 ★★★★★
考点六 链队列的定义 ★
考点七 链队列的操作 ★
考点八 双端队列 ★★★考点八: 双端队列
所谓双端队列是指两端都可以进行进队和出队操作的队列,将队列的两端分
别称为前端和后端,两端都可以入队和出队。
其元素的逻辑结构仍是线性结构。
线性表
后端进
前端出
前端进 后端出
前端 后端考点八: 双端队列
输入受限的双端队列,即一个端点允许插入和删除,另一个端点只允许删除的双端队列。
线性表
前端出
后端出
前端进
前端 后端考点八: 双端队列
输出受限的双端队列,即一个端点允许插入和删除,另一个端点只允许插入的双端队列。
线性表
前端出
后端入
前端进
前端 后端【政哥题型总结】考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad
C【解析】假设此队列只允许在左端出队,那么在此队列中越左的元素越早出
队,此时应该将较早出队的元素放在队列较左端,队列中数据元素的最终次序
应该与上述出队序列相同,考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad
A选项,对于b a c d e序列,先将a入队,由于b应该比a先出队,因此将b从队
列左端入队使b在a的左边;c应该比a后出队,将c从队列右端入队使c在a的右
边;d应该比a后出队,将d从队列右端入队使d在c的右边;e应该比d后出队,
将e从队列右端入队使e在d的右边,最终队列中序列为bacde,从左端依次出队
可以得到bacde。考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad
B选项,对于d b a c e序列,先将a入队,b比a先出队,因此将b从队列左端
入队使b在a的左边;c应该比a后出队,将c从队列右端入队使c在a的右边;d
比a先出队,因此将d从队列左端入队使d在b的左边;e应该比a后出队,将e
从队列右端入队使e在c的右边,此时队列中序列为d b a c e,出队序列也为d
b a c e。考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad
C选项,对于d b c a e序列,先将a入队,b比a先出队,因此将b从队列左端
入队使b在a的左边;c比a先出队,因此将c从队列左端入队,因为b比c先入队,
因此队列中不可能出现bca序列,因此C选项错误。若队列在右端出队,则具
体操作如图3,依旧无法出现bca序列。考点八: 双端队列
1、某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、
c、d、e元素进队,则不可能得到的顺序是( )。
A. bacde B. dbace C. dbcae D. ecbad
D选项,对于e c b a d序列,先将a入队,b比a先出队,因此将b从队列左端
入队使b在a的左边;c比a先出队,因此将c从队列左端入队使c在b的左边;d
应该比a后出队,将d从队列右端入队使d在a的右边;e比a先出队,因此将e从
队列左端入队使e在c的左边;此时队列中元素序列为ecbad,出队序列也是
ecbad。THANKS