2021年队列.ppt

☞ 什么是队列
链队列
顺序队列
队列的应用举例
栈
队 列
队列
2021/1/15
1
一、什么是队列
队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。
a1 a2 a3 ………… an
出队列
入队列
队尾 rear
队头 front
允许删除的一端称为队头(front)
允许插入的一端称为队尾(rear)
队列中没有元素时称为空队列
队列
2021/1/15
2
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。
队列
2021/1/15
3
二、队列的特点
根据队列的定义可知，最先放入队列的元素最先出队列。
特点 ：先进先出
也就是说，队列是一种后进先出的线性表，简称为FIFO (First In First Out)表。
队列
2021/1/15
4
例1：有一个栈，进 栈 序列为A、B、C，试给出所有可能的出 栈 序列。
不可能产生输出序列 CAB
A进 B进 C进 C出 B出 A出 CBA
A进 A出 B进 B出 C进 C出 ABC
A进 A出 B进 C进 C出 B出 ACB
A进 B进 B出 A出 C进 C出 BAC
A进 B进 B出 C进 C出 A出 BCA
队列
队列
只可能产生的输出序列 ABC
队列
2021/1/15
5
三、队列的抽象数据类型
ADT Queue
{
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为队尾，a1 端为队头。
基本操作：
InitQueue (&Q)
//操作结果：构造一个空队列Q 。
DestroyQueue (& Q)
//操作结果：队列Q被销毁。
ClearQueue (& Q)
//操作结果：将Q清为队列
队列
2021/1/15
6
QueueEmpty (Q)
//操作结果：若队列Q为空队列，则返回TRUE，否则FALSE。
QueueLength (Q)
//操作结果：返回Q的元素个数，即队列的长度。
GetHead(Q, &e)
//操作结果：用e返回Q的队头元素。
EnQueue (&Q, e)
//操作结果：插入元素e为新的队尾元素。
DeQueue (&Q, &e)
//操作结果：删除Q的队头元素，并用e返回其值。
}//ADT Stack
队列
2021/1/15
7
什么是队列
☞ 链队列
顺序队列
队列的应用举例
栈
队 列
队列
2021/1/15
8
显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。
链队列：用链表来存储队列
队头指针 为
队尾指针 为
a2
an
∧
a1
front
rear
头结点
队头结点
队尾结点
Q
队列
2021/1/15
9
typedef struct QNode
{
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
队尾
队头
front
rear
Q
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
} LinkQueue;
LinkQueue Q;
队列
2021/1/15
10