资源描述：
《(数据结构) 第四章 队列 -严军勇.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章队列●本章要点●队列的定义及基本运算●队列的存储结构及运算实现●队列的应用举例●本章难点●循环队列、队列的链式存储结构及其运算的实现●4.1队列的定义和基本运算在排队买东西时，通常要遵循：最先排队的人可以先买到东西出队。这种先进先出的规则应用在数据结构中称为队列。队列是程序设计中经常用的一种数据结构，其逻辑结构是线性结构，存储结构有顺序存储和链式存储两种存储方法。其操作特点和栈相反，队列只能在线性表的一端进行插入（入队），另一端进行删除（出队），和日常生活中的队列相似，因此队列又称为“先进先出”表（FirstInFirstOut，简称FIFO结构）。●4.1.1
2、队列的定义队列（Queue）是线性表的一种特殊情况，其所有的插入操作限定在表的一端进行，而所有的删除操作则限定在表的另一端进行。允许插入的一端叫做队尾（rear），允许删除的一端称为队头（front）。队列的插入运算称为入队，删除运算称为出队。没有元素的队列称为空队列。第一个入队的元素也是第一个出队的元素。设Q=(a1,a2,a3,…，an-1,an)队列结构，队头元素为a1，队尾元素为an，队列中元素是按照a1,a2,a3,…，an-1,an顺序进入的，退出队列也只能是这个次序。a1a2a3… an-1an出队入队●4.1.2队列的基本运算队列的基本操作除了入队（插
3、入）和出队（删除）外，还有队列的初始化、判断队列是否为空、判断队列是否满及取队头元素等。队列的抽象类型定义ADTQueue{Data={ai
4、ai∈Elemtype,i=1,2,…,n,n≥0}R1={(ai-1,ai)
5、ai-1,ai∈Data,i=2,3,,…,n,n≥0}其中，an是队尾元素，a1是队头元素。●4.1.2队列的基本运算⑴队列初始化⑵入队列⑶出队列⑷取队头元素⑸队列空判断⑹销毁队列(7)清空队列(8)输出队列(9)返回队列的长度⒈顺序队列队列的顺序存储结构称为顺序队列，是用一组连续的存储单元依次存放队列中的元素。在C语言中用一维数组来存放队列中的元
6、素。因为队列的队头和队尾的位置是变化的，所以还需附设两个指针front和rear，front指针指向队列头元素的位置，rear指针指向队列尾元素的位置。约定front指针指向队列头元素所在位置的前一个位置，而rear指针指向实际队尾元素所在位置，当队列为空时，令Sq->front=Sq->rear=-1。●4.1.3队列的顺序存储结构顺序队的类型定义#defineMAXSIZE1024typedefstruct{Elemtypedata[MAXSIZE];intrear,front;}SeqQueue;定义一个指向队列的指针变量typedefSeqQueue*Sq;8
7、76543210Sq->rearSq->reara6a5a4Sq->frontSq->reara9a8a7Sq->frontSq->reara3a2a1●4.1.3队列的顺序存储结构Sq->frontSq->frontfront=rear=-1空队front=-1rear=2有3个元素front=5rear=8假溢出现象front=2rear=5一般情况队列元素个数：m=(Sq->rear)-(Sq->front)队满：m=MAXSIZE队空：m=0Q[0]Q[1]Q[2]Q[3]Q[4]Q[5]Q[6]Q[7]GHSq->front=5Sq->rear=7由于入队的
8、同时可能有些元素出队，队尾指针到最后，无法插入，但队列并不满，即队中元素个数少于MAXSIZE，这种现象称为假溢出。●4.1.3队列的顺序存储结构⒉循环队列对于前面的假溢出问题，将顺序队列构造为一个环状的空间。称为循环队列。Q[0]Q[1]Q[2]Q[3]Q[4]Q[maxsize-1]ABCDSq->front=0Sq->rear=4maxsize-101234ABCDSq->rearSq->front●4.1.3队列的顺序存储结构构造成循环队列后，指针和队列元素的关系不变。在入队时，循环队列的尾指针if(Sq->rear+1>=MAXSIZE)Sq->rear=0
9、;elseSq->rear++;运用“模运算”Sq->rear=(Sq->rear+1)%MAXSIZE;在出队时，循环队列的头指针Sq->front=(Sq->front+1)%MAXSIZE;取模运算的目的是为了将指针的取值从队尾下标MAXSIZE-1返到0。●4.1.3队列的顺序存储结构BCDSq->rearSq->frontABCDAEGF一般情况队列满时空队列●4.1.3队列的顺序存储结构Sq->rearSq->frontSq->rearSq->front为了区分循环队列是空还是满，可以有两种方法：一种方法是可以设定一个标志位flag，当插
