第4章 队列.ppt

第4章队列
●本章要点
●队列的定义及基本运算
●队列的存储结构及运算实现
●队列的应用举例
●本章难点
●循环队列、队列的链式存储结构及其运算的实现
● 队列的定义和基本运算
在排队买东西时,通常要遵循:最先排队的人可以先买到东西出队。这种先进先出的规则应用在数据结构中称为队列。
队列是程序设计中经常用的一种数据结构,其逻辑结构是线性结构,存储结构有顺序存储和链式存储两种存储方法。
其操作特点和栈相反,队列只能在线性表的一端进行插入(入队),另一端进行删除(出队),和日常生活中的队列相似,因此队列又称为“先进先出”表(First In First Out,简称FIFO结构)。
● 队列的定义
队列(Queue)是线性表的一种特殊情况,其所有的插入操作限定在表的一端进行,而所有的删除操作则限定在表的另一端进行。允许插入的一端叫做队尾(rear),允许删除的一端称为队头(front)。
队列的插入运算称为入队,删除运算称为出队。没有元素的队列称为空队列。第一个入队的元素也是第一个出队的元素。
设Q=(a1,a2,a3,…,an-1,an)队列结构,队头元素为a1,队尾元素为an,队列中元素是按照a1,a2,a3,…,an-1,an顺序进入的,退出队列也只能是这个次序。
a1 a2 a3 … an-1 an
出队
入队
● 队列的基本运算
队列的基本操作除了入队(插入)和出队(删除)外,还有队列的初始化、判断队列是否为空、判断队列是否满及取队头元素等。
队列的抽象类型定义
ADT Stack{
Data={ai| ai∈Elemtype,i=1,2,…,n,n≥0}
R1={(ai-1,ai)| ai-1,ai ∈Data, i=2,3, ,…,n,n≥0}
其中,an是栈顶元素,a1是栈底元素。
● 队列的基本运算
⑴队列初始化(init_queue( ) )
建立一个空队列,准备存放数据。
⑵入队列(Enqueue(Q,x))
在队尾插入一个新的数据元素。
⑶出队列(Outqueue(q,x))
从队头删除一个元素,队列发生变化。
⑷取队头元素(frontqueue(Q,x))
取队头数据使用,不删除该数据元素,队列不变。
⑸队列空判断(isEmptyqueue(Q))
判断队列是否为空,是出队列和取队头元素时常用的操作。
⑹判断队列是否满(isFullqueue(Q))
判断队列是否满,是入队列时常用的操作。
⒈顺序队列
队列的顺序存储结构称为顺序队列,是用一组连续的存储单元依次存放队列中的元素。在C语言中用一维数组来存放队列中的元素。因为队列的队头和队尾的位置是变化的,所以还需附设两个指针front和rear,front指针指向队列头元素的位置,rear指针指向队列尾元素的位置。约定front指针指向队列头元素所在位置的前一个位置,而队尾元素rear指向实际队尾元素所在位置,当队列为空时,令Sq->front=Sq->rear=-1。
● 队列的顺序存储结构
顺序队的类型定义
#define MAXSIZE 1024
typedef struct
{Elemtype data[MAXSIZE];
int rear,front;
}SeqQueue;
定义一个指向队列的指针变量
typedef SeqQueue *Sq;
8
7
6
5
4
3
2
1
0
Sq->rear
Sq->rear
a6
a5
a4
Sq->front
Sq->rear
a9
a8
a7
Sq->front
Sq->rear
a3
a2
a1
● 队列的顺序存储结构
Sq->front
Sq->front
front=rear=-1
空队
front=-1 rear=2
有3个元素
front=5 rear=8
假溢出现象
front=2 rear=5
一般情况
⒈初始化
Init_queue(sequeue *sq)
{Sq=(SeqQueue *(malloc(sizeof(SeqQueue));
Sq->front=-1;
Sq->rear=-1;
}
● 队列的顺序存储结构
⒉入队
队列不满时,队尾指针加1,元素入队。
算法
int Enqueue(SeqQueue *Sq,int x)
{if (Sq->rear >=MAXSIZE-1)
return(0);
else
{(Sq->rear)++;
Sq->data[Sq->rear]=x;
return(1);
}
● 队列的顺序