elem 1 2 3 …… …… int ElemType int N front rear
将front称为队列的队头 front称为队列的队头 指针， 指针，且指向实际队头 元素的前一个位置； 元素的前一个位置；将 rear称为队列的队尾指 rear称为队列的队尾指 针，且指向实际队尾元 素。 顺序队列的基本信息
1 6
2 3
a、b、c、d依 次入队后
1
a
b c
2
a、b出队后
1 6
2
c d
6 5 2 3 6f
e d
5
初始状态
4 1 6 1
3 4 5
3 4
g
h
2 3
满状态时
1 6
f c e g 空状态时 h 2
e、f、g、h依 次入队后
全 出 队
5 1
g h i e
4 2 3
i入队
5
d
4
c出队
front
3 2 6 3 2 4 6
初始状态
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear 0 1 1 2 B 6 C、D、E、 F依次入 5 队且B 队且B出 4 队 3 2 1 front rear 1 2 3
特殊在对操作的限定
主要是对与元素有关的操作的限定 读元素 GetHead( Q, &e ) 修改元素 PutHead ( &Q, e ) 插入元素 EnQueue( &Q, e ) 删除元素 DeQueue( &S,&e ) 允许插入操作的一端称为队尾 允许删除操作的一端称为队头 GetElem ( L, i , &e ) PutElem ( &L, i , e ) ListInsert( &L, i , e ) ListDelete( &L, i , &e ) GetElem ( L, 1 , &e ) PutElem ( &L, 1 , e ) ListInsert( &L, n+1 , e ) ListDelete( &L, 1 , &e ) 入 队 a1 a2 a3 …… an 出 队 队 头 队 尾
约定： 为队尾元素， 约定： an为队尾元素， a1为队头元素
用图示： 用图示： a1 或
a2
a3……Βιβλιοθήκη an-1an（ a1， a2 ，a3，……， an ） ，
队列是长度可变的线性结构
返回P2 返回P2
队列基本操作的定义
InitQueue（&Q） （ ）
构造一个空队列Q 构造一个空队列
结构初始化 结构销毁
1 2 6
front rear 6 6
这时，队列的初始状态就是： 这时，队列的初始状态就是：
3 5 4
入队和出队时， 且，入队和出队时，队头和队尾指针不再是 简单的加1，而是模6（ ） 简单的加 ，而是模 （N）加1
返回P14 返回P14
循环队列队空和队满的条件
观察在循环队列时入队和出队操作时的状态变化：（ 观察在循环队列时入队和出队操作时的状态变化：（N=6） ：（ ）
引用型 加工型 加工型 加工型
PutHead( &Q, e )
初始条件： 初始条件：栈S已存在且非空 已存在且非空 操作结果： 修改队列 修改队列Q的队头元素的值 操作结果：用e修改队列 的队头元素的值
EnQueue（ &Q，e） （ ， ）
初始条件：队列 已存在 初始条件：队列Q已存在 操作结果：插入元素e为队列 为队列Q的新的队尾元素 操作结果：插入元素 为队列 的新的队尾元素
DestroyQueue (&Q)
初始条件：队列 已存在 初始条件：队列Q已存在 操作结果：队列Q被销毁 操作结果：队列 被销毁
ClearQueue (&Q)
初始条件：队列 已存在 初始条件：队列Q已存在 加工型 操作结果：将队列Q 操作结果：将队列 清为空队列
QueueEmpty(Q)
初始条件：队列 已存在 初始条件：队列Q已存在 操作结果：若队列Q为空队列 则返回TRUE，否则返回 操作结果：若队列 为空队列 则返回 ，否则返回FALSE
C B
初始状态
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear 0 1 1 2 B 6 C、D、E、 F依次入 5 队且B 队且B出 4 队 3 2 1 front rear 1 3 4
队列的操作被限定在表的两端进行
队列也被称为先进先出表
线性表有两个端点 a1 a2 a3 …… an 头 尾 对于队列而言， 对于队列而言，则 只能对头端和尾端 的元素进行操作 对元素可以做任 意位序的操作
返回P2 返回P2
队列的逻辑结构 用二元组表示： 用二元组表示：
L=（D，R） （ ， ） D={ai | ai ∈ElemSet，i=1，2，……n，n≥0} ， ， ， ， R={<ai-1，ai> | ai-1，ai ∈D，i= 2，……n} ， ，
6f 5
d
5
d
3
恋
rear
4
4
续循环队列队空和队满的条件
观察循环队列的变化得出： 观察循环队列的变化得出：
队满的条件是队头指针和队尾指针相同 队空的条件也是队头指针和队尾指针相同
因此，必须修改一个条件，以区分两种不同的状态： 因此，必须修改一个条件，以区分两种不同的状态：
保留队头指针和队尾指针相同作为队空的条件 牺牲一个单元，使队满的条件为： 牺牲一个单元，使队满的条件为：
D C B
初始状态
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear 0 1 1 2 B 6 C、D、E、 F依次入 5 队且B 队且B出 4 队 3 2 1 front rear 1 4 5 E D C B
初始状态
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear 0 1 1 2 B 6 C、D、E、 F依次入 5 队且B 队且B出 4 队 3 2 1 front rear 1 2 6 F E D C B
初始状态
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear 0 1 1 2 B 6 C、D、E、 F依次入 5 队且B 队且B出 4 队 3 2 1 front rear 1 5 6 F E D C B
数据结构
刘晋萍
785297343@ 785297343@ QQ:785297343
第五讲 队列
队列的概念 队列的逻辑结构 队列基本操作的定义 队列的存储结构
顺序存储结构
循环队列
问题 观察
链式存储结构
队列基本操作的实现
基于顺序结构 基于链式结构
习题 习题
结束
队列的概念
队列是特殊的线性表
Q： 6 421 12 3 5 23 4 3 1 2 11
而这时实际还有一 个单元空间， 个单元空间，这就 是所谓牺牲一个单 元。
front rear
1 6
这时， 的尾指针模6加 等于 的头指针） 等于Q的头指针 这时，Q.rear%6+1=Q.front=1（Q的尾指针模 加1等于 的头指针） （ 的尾指针模
•队列 队列Q 队列
SqQueue Q
结 构 描 述
struct qsqstr { ElemType elem[N]; int front，rear; ， }; typedef struct qsqstr SqQueue;
•队头指针和队尾指针 队头指针和队尾指针
Q.front 和 Q.rear
•队头元素和队尾元素 队头元素和队尾元素
Q.elem[Q.front] 和 Q.elem[Q.rear-1]
关于队列的假溢出问题
观察队列在入队和出队操作时的状态变化：（ 观察队列在入队和出队操作时的状态变化：（N=6） ） ：（ 6 5 4 3 2 1 front rear 0 0 A入队 6 5 4 3 2 1 front rear A 0 0 1 B入队 6 5 4 3 2 1 front rear B A 0 1 2 A出队 6 5 4 3 2 1 front rear B A 0 1 1 2 C、D、E、 F依次入 队且B 队且B出 队