队列及其应用课件

☞5.1队列的基本概念5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用☞5.1队列的基本概念第5章队列及其应用1☞5.1.1队列的定义5.1.2队列的基本运算

5.1队列的基本概念☞5.1.1队列的定义5.1队列的基本概念2定义队列是满足下列条件的数据元素集合：(1)有限个具有相同数据类型的数据元素的集合，D={ai|i=1，2，…，n}，ai为数据元素。(2)数据元素之间的关系为R={<ai，ai+1>|ai，ai+1∈D，i=1，2，…，n}；(3)a1为队头元素，an为队尾元素；数据元素按a1，a2，…，an的次序入队，也以相同的次序出队。

定义队列是满足下列条件的数据元素集合：3由定义可以看出，队列是由一组同类型数据元素(a1，a2，…，an)组成的线性序列。其中，ai(1≤i≤n)可以是原子类型(如整型、实型、字符型等)、或是结构类型的数据元素。在一个队列中，元素ai-1是ai的唯一直接前驱，ai+1是ai的唯一直接后继；而队头元素a1无前驱，队尾元素an无后继。因此，队列属于线性逻辑结构。

由定义可以看出，队列是由一组同类型数据元素(a14即：队列是限定仅在一端进行插入，而在另一端进行删除操作的线性表。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。即：队列是限定仅在一端进行插入，而在另一端进行删除操作的线性5队列的特点

☞根据队列的定义可知，最先入队的元素也是最先出队。

☞特点：先进先出（FIFO）

也就是说，队列是一种先进先出(FirstInFirstOut)的线性表，简称为FIFO表。

a1a2a3…………an出队列入队列队头front队尾rear队列的特点a1a2a3…………an出队列入队列65.1.1队列的定义☞5.1.2队列的基本运算

5.1队列的基本概念5.1.1队列的定义5.1队列的基本概念7☞定义在该逻辑结构上的运算有以下几种基本运算：

(1)置空队：InitQueue(Q)，InitQueue运算的结果是将队列Q置成空队列。(2)判队空：QueueEmpty(Q)，如果队列为空，则QueueEmpty返回1，否则QueueEmpty返回0。(3)判队满：QueueFull(Q)，如果队满，则QueueFull返回1，否则QueueFull返回0。

☞定义在该逻辑结构上的运算有以下几种基本运算：8(4)入队：Add(Q，x)，Add在队列Q的队尾插入元素x。(5)出队：Delete(Q)，Delete从队列Q中删除队头元素。

(4)入队：Add(Q，x)，Add在队列Q的队尾插95.1队列的基本概念☞5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用5.1队列的基本概念第5章队列及其应用10☞5.2.1顺序队列的概念及数据类型5.2.2循环队列5.2.3循环队列的运算实现5.2顺序队列及其基本算法☞5.2.1顺序队列的概念及数据类型5.2顺序队列及其基11☞

采用顺序存储结构的队列称为顺序队列。☞它是利用一批地址连续的存储单元依次存放自队头到队尾的数据元素,同时设一个尾指针rear指向队尾元素的当前位置。☞由于队列的操作是删除在头、插入在尾，可另设一头指针front指向队头的位置，我们约定指向队头的前一个位置。☞通常用一维数组来实现队列的顺序存储。顺序队列☞采用顺序存储结构的队列称为顺序队列。顺序队列12typedefstruct{datatypedata[maxlen];intfront,rear;}SeqQueue;SeqQueue*Q;0123maxlen-1nfrontrear··················dataQ顺序队列的数据类型：typedefstruct{0123maxlen-130123maxlen-1nfrontrear··················dataQ☞

front和rear的初始值在队列初始化时均置为０。☞

入队时尾指针加１，并将新元素插入所指的位置。出队时头指针加１，然后删去所指的元素，并返回被删元素。

约定：在非空队列里，头指针始终指向队头元素前的空位，而尾指针始终指向队尾元素。0123maxlen-1nfrontrear········14０１２３0123

(a)队列初始为空０１２３（c)a出队frontrearfront（b）a,b,c入队abcfrontabcfrontbc(d)b出队０１２３frontrearrearrearrearrearfront０１２３15☞队空：Q->front=Q->rear☞队满：Q->rear=maxsize-1☞队长：Q->rear-Q->front☞入队：将队尾指针加一，即Q->rear=Q->rear+1，再将新元素按rear指示位置加入☞出队：将队头指针加一，即Q->front

=Q->front

+1，再将front指示的元素取出。此时：☞队空：Q->front=Q->rear此时：16可以看出：

☞尾指针rear已指到数组的最后一个元素，即rear=maxlen-1,若这时入队，则产生“溢出”；

☞此时经过一定数量的出队后，头指针front可指向队列的中间，即数组的前面部分有闲置的空间——这种有可用空间存在的溢出称“假溢出”问题：如何利用数组前面的可用空间？可以看出：175.3.1顺序队列的数据类型☞5.3.2循环队列5.3.3循环队列的运算实现5.3队列的顺序存储5.3.1顺序队列的数据类型5.3队列的顺序存18问题的提出：在顺序队列中，入队时在队尾增加元素，尾指针rear后移；出队时，则是头指针front后移。这样，在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用，在进行一定数量的入队和出队后，可能会出现有可用空间存在的溢出——“假溢出”循环队列问题的提出：在顺序队列中，入队时在队尾增加元素，尾指针re19解决的方法：将data[0]看作是data[maxlen-1]后的下一个存储位置。

即：将向量空间看成是一个首尾相接的圆环。并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（maxsize-1）时，其加1操作的结果是指向向量的下界0。解决的方法：将data[0]看作是data[maxlen-20

显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。0123456frontghkefrontabfrontfrontreardrearrearrearrearfrontrear例：循环队列的操作显然，因为循环队列元素的空间可以被利用，除215.3.1顺序队列的数据类型5.3.2循环队列☞5.3.3循环队列的运算实现5.3队列的顺序存储5.3.1顺序队列的数据类型5.3队列的顺序存22讨论：在循环队列中执行入队和出队操作：入队：

if(Q->rear==maxlen–1)Q->rear=0;elseQ->rear=Q->rear+1;Q->data[Q->rear]=x；0123456ghkefrontdrearrearrearrear入队：讨论：在循环队列中执行入队和出队操作：入队：if(Q23或采用模运算：

Q->rear=(1+Q->rear)%maxlen

Q->data[Q->rear]=x；或采用模运算：24或Q->front=(1+Q->front)%maxleneabdrear0123456frontfrontfrontkfront出队：if(Q->front==maxlen–1)Q->front=0;elseQ->front=Q->front+1;或Q->front=(1+Q->front)25frontghkeabdrear0123456frontghkeabdrear0123456rearrearrearrearfrontfrontfrontfrontfrontfront入队出队队满队空讨论：队空与队满的描述frontghkeabdrear0123456frontgh26队空：Q->rear=Q->front队满：Q->rear=Q->front可见，队空与队满有相同的描述方式：问题：如何区分队空与队满状态？队空：Q->rear=Q->front可见，队空与队满有27解决方法：

(1)

设置一入队或出队标志，以区分最后一次操作是入队还是出队。这样，当头尾两个指针相等时，由该标志可以判断出满和空。(2)

少用一个元素空间，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。解决方法：28fronthkeabdrear0123456fronthkeabdrear0123456rearrearrearfrontfrontfrontfrontfrontfront入队出队队满:(1+Q->rear)%maxlen==Q->front

队空Q->rear==Q->front即：fronthkeabdrear0123456fronthke29基于方法(2)的各算法描述如下：

(1)置空队

按前面的讨论，队列为空时，其头尾指针相等。

SeqQueue*

InitQueue(SeqQueue*Q){Q->front=0；Q->rear=0；returnQ；}

基于方法(2)的各算法描述如下：30(2)判队空将头尾指针是否相等作为队列是否为空的等价条件。

intQueueEmpty(SeqQueue*S){if(Q->front==Q->rear)return1；elsereturn0；//队空时返回1，不空返回0}

(2)判队空将头尾指针是否相等作为队列是否为空的等31(3)判队满按前面的约定，“队满”是指仅剩一个空位置时的状态，即：尾指针的下一个位置就是头指针所指的位置。intQueueFull(SeqQueue*Q){if(Q->front==(Q->rear+1)%maxlen) return1；elsereturn0；//队满时返回1，不满返回0}

(3)判队满按前面的约定，“队满”是指仅剩一32(4)取队头元素首先要判断队是否空，然后才能求解。

datatypeGetHead(SeqQueue*Q){datatypex;if(QueueEmpty(Q))return(error);else{x=Q->data[(Q->front+1)%maxlen];returnx;}}(4)取队头元素首先要判断队是否空，然后才能求33(5)入队入队前，要判断队是否满

voidAdd(SeqQueue*S，Datatypex){if(!QueueFull(Q)){//若队不满，则进行入队运算 Q->rear=(Q->rear+1)%maxlen；Q->data[Q->rear]=x；}elseprintf(“queuefull”)；}

(5)入队入队前，要判断队是否满34(6)出队出队前，判断队是否空。

voidDelete(SeqQueue*S){if(!QueueEmpty(Q))//若队不空，则进行出队运算 Q->front=(Q->front+1)%maxlen； elseprintf(“queueempty”)；}

(6)出队出队前，判断队是否空。35思考题：1、如何求解队列中元素的个数？2、如果对前面所讨论的循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。思考题：1、如何求解队列中元素的个数？36循环队列基本算法性能分析

可以看出，循环队列的各基本运算均与队列中元素的个数无关，即与问题的规模无关，其出队与入队运算也不需要移动元素。所以，各基本运算的时间复杂度均为O(1)。

另外。循环队列的5种基本运算执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各算法的空间性能均较好。只是对于data数组长度的定义很难把握好，如果定义过大，会造成必不可少的空间浪费。循环队列基本算法性能分析375.1队列的基本概念5.2顺序队列及其基本算法☞5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用5.1队列的基本概念第5章队列及其应用38☞5.3.1链队列的概念及数据类型5.3.2链队列的运算实现

5.3链队列及其基本运算☞5.3.1链队列的概念及数据类型5.3链队列及其基本39链队列

☞队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。链队列40a2an∧a1frontrear头结点队头结点队尾结点typedefstruct{LinkList*front,*rear;}LinkQueue;

LinkQueue*Q;链队列的类型Qa2an∧a1frontrear头结点队头结点队尾结点t41则头指针为Q－>front尾指针为Q－>rear这样，确定了头指针和尾指针后，在链队列上实现上述的运算可参照链表的运算。

a2an∧a1frontrearQ则头指针为Q－>fronta2an∧a1fro425.3.1链队列的概念及数据类型☞5.3.2链队列的运算实现

5.3链队列及其基本运算5.3.1链队列的概念及数据类型5.3链队列及其43(1)建空队∧QSeqQueue*SetQueue(){LinkQueue*Q；Q=malloc(sizeof(LinkQueue))；Q->front=malloc(sizeof(Linklist))；Q->front->next=NULL；Q->rear=Q->front；returnQ；}(1)建空队∧QSeqQueue*SetQueue()44(2)判队空intQueueEmpty(LinkQueue*Q){if(Q->front==Q->rear)return1；elsereturn0；//队空时返回1，不空返回0}(3)链队列不存在队满。(2)判队空intQueueEmpty(LinkQu45(4)入队入队时，仅对队尾操作p∧a2ana1frontrearQx∧(4)入队入队时，仅对队尾操作p∧a2ana1frontr46LinkQueue*Add(LinkQueue*Q，Datatypex){

//将元素x入队列QLinkQueue*p；p=malloc(sizeof(Linklist))；//建立新节点空间，以存放xp->data=x；p->next=NULL；Q->rear->next=p； //将新节点插入到尾节点后Q->rear=p； //尾指针指向新的尾节点returnQ；}LinkQueue*Add(LinkQueue*Q，D47(5)出队考虑:(1)出队时，在链表中删除队头结点。(2)若队列Q中只有一个元素时怎么操作?pua2an∧a1frontrearQ(5)出队考虑:(1)出队时，在链表中删除队头结点。pua48

p=Q->front->nextQ->front->next=p–>nextpif(Q->rear==p)Q->rear=Q->front;a1a2an∧frontrearQ出队操作：考虑队列中只有一个元素时free(p);若队列Q中只有一个元素时怎么操作?p=Q->front->nextpi49LinkQueue*Delete(LinkQueue*Q){Linklist*p；if(!QueueEmpty(Q)){//若队不空，则进行出队运算p=Q->front->next；Q->front->next=p->next；if(p->next=NULL)//若链队列的长度为1，需修改尾指针Q->rear=Q->front；free(p)；returnQ；}elseprintf(“queueempty”)；}LinkQueue*Delete(LinkQueue*50链队列基本算法性能分析

可以看出，链队列实际上是运算受限制的链表，其插入和删除运算在表的两端进行。所有基本运算均与队列的长度无关，算法的时间复杂度为O(1)。链队列的空间性能与链表的空间性能相同。链队列基本算法性能分析515.1队列的基本概念5.2顺序队列及其基本算法5.3链队列及其基本算法☞5.4队列的应用举例——基数排序问题第5章队列及其应用5.1队列的基本概念第5章队列及其应用52一、多关键字排序

在许多实际的排序的应用中，所涉及的排序字段往往不止一个。例如：对一个学生成绩表（线性表）进行排序。表中每一个记录有三个域：姓名、总分、数学成绩。要求先按总分排序，对总分相同的记录再按数学分数排序。——这个排序问题涉及两个字段。一、多关键字排序在许多实际的排序的应用中，所涉及的53下面，我们以一副扑克牌的排序过程为例，介绍多关键字排序的方法。

我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。若规定花色和面值的顺序如下：花色：梅花<方块<红桃<黑桃面值：A<2<3<…<10<J<Q<K下面，我们以一副扑克牌的排序过程为例，介绍多关键字排54进一步规定花色的高于面值，则一副扑克牌从小到大的顺序为：梅花A，2，…K；方块A，2，…K；红桃A，2，…K；黑桃A，2，…K。

具体进行排序时有两种做法，其中一种是先按花色分成有序的四类，然后再按面值对每一类从小到大排序。该方法称为“高位优先”排序法。进一步规定花色的高于面值，则一副扑克牌从小到大的顺序为55另一种做法是分配与收集交替进行。

首先按面值从小到大把牌摆成13叠（每叠4张牌），然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4叠，每叠有13张牌，最后把这4叠牌按花色的次序收集到一起，于是就得到了上述有序序列。该方法称为“低位优先”排序法，如下图所示。另一种做法是分配与收集交替进行。56队列及其应用课件57二、链式基数排序基数排序属于上述“低位优先”排序法，通过反复进行分配与收集操作完成排序。下面我们以实例来介绍基数排序的思想。【例】一组记录的关键字为：(278，109，63，930，589，184，505，269，8，83)试采用基数排序方法对其进行排序。二、链式基数排序58(278，109，63，930，589，184，505，269，8，83)我们将上述单关键字看成由若干个关键字复合而成。

上述这组关键字的值都在0≤K≤999的范围内，我们可以把每一个数位上的十进制数字看成是一个关键字，即将关键字K看成由三个关键字K0，K1，K2组成。其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。

(278，109，63，930，589，184，505，2659因为十进制的基数是10，所以，每个数位上的数字都可能是0～9中的任何一个。我们先按关键字K2来分配所有参与排序的元素，将K2=0的元素放在一组、K2=1的元素放在一组、……、K2=9的元素放在一组。

因为十进制的基数是10，所以，每个数位上的数字都可能60再按K2的值由0到9的顺序收集各组元素，形成序列(930,063,083,184,505,278,008,109,589,269)再按K2的值由0到9的顺序收集各组元素，形成序列61对上述序列中的元素再按关键字K1来分配。然后，再按K1的值由0到9的顺序收集各组元素，形成序列(505，008，109，930，063，269，278，083，184，589)。

对上述序列中的元素再按关键字K1来分配。然后，再按K1的值由62对上述序列中的元素再按关键字K0来分配。然后，再按K0的值由0到9的顺序收集各组元素，形成序列(008，063，083，109，184，267，278，505，589，930)问题2：这10个“容器”是什么？数据结构？问题1：基数排序思想？对上述序列中的元素再按关键字K0来分配。然后，再按K0的值由63可以看出，基数排序的思想是：

首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序。以此类推，由低位到高位，由次关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键字(主关键字)对记录进行排序后，基数排序完成。可以看出，基数排序的思想是：首先将待排序的记录分成64链式基数排序算法实现的技术要点：

要实现上述基数排序的过程，需要解决3个问题。问题一：每次分配记录所形成的各组序列以何种结构存储？问题二：如何收集各组记录？问题三：如何描述由待排序关键字分成的若干个子关键字？链式基数排序算法实现的技术要点：65由上例可以看出，各组记录的收集是本着“先进入该组的记录将首先被收集”的原则。这与队列的“先进先出”的原则相一致。这样，各组序列就以队列来描述。因为要进行多次的分配与收集，为节省存储空间及运算方便，我们采用链队列来存储各组序列。由上例可以看出，各组记录的收集是本着“先进入该组的记66

链队列的数量与基数一致，若基数为RAX，则令f[0]～f[RAX-1]分别指向RAX个链队列的队头节点，令r[0]～r[RAX-1]分别指向RAX个队列的队尾节点。每次分配前，将RAX个链队列置空：for(i=0；i<=RAX-1；++i)f[i]=r[i]=NULL；

。链队列的数量与基数一致，若基数为RAX，则令f[67

对各链队列所表示的序列进行收集时，应从链队列f[0]开始，当链队列f[j+1]不为NULL时，将链队列f[j]与其首尾相接：i=0；while(f[i]==NULL)i++；//查找第一个不空的链队列for(j=i，k=i+1；k<=RAX-1；++k)if(f[k]!=NULL){r[j]->next=f[k]；j=k；}

对各链队列所表示的序列进行收集时，应从链队列f[68对于问题一，一个简单的方法是，在存储待排序记录时，就将关键字按分成子关键字来存储。为了运算方便，我们采用与链队列中节点一致的节点结构，以单链表来存储待排序的一组记录及收集后的记录序列。节点的类型可以定义为：#defineM3//M为待排记录中子关键字的个数typedefstructnode{keytypekey[M]；structnode*next；}Rnode；对于问题一，一个简单的方法是，在存储待排序记录时，就将关键字69

若关键字为整型数据，则存放待排序记录的单链表可以这样构造：

#defineN8 //N为待排记录的个数Rnode*L，*p；L=NULL；//链表L初始化为空for(i=1；i<=N；++i){//头插法建单链表Lp=malloc(sizeof(Rnode))；for(j=0；j<=M-1；++j) //分别输入M个子关键字scanf(“%d”，&(p->key[j]))；p->next=L；L=p；}

若关键字为整型数据，则存放待排序记录的单链表可以这70

综上所述，以链表来存储待排序记录，基数排序算法如下：

#defineM3//M为待排记录中子关键字的个数#defineRAX10 //RAX为基数typedefstructnode{keytypekey[M]；structnode*next；}Rnode；Rnode*f[RAX]，*r[RAX]；综上所述，以链表来存储待排序记录，基数排序算法如71Rnode*SetList(){ //建待排序记录组成的单链表LRnode*L，*p；inti，j；L=NULL； //链表L初始化为空for(i=1；i<=n；++i){//头插法建单链表L，n为待排序记录个数p=(Rnode*)malloc(sizeof(Rnode))；for(j=0；j<=M-1；++j)//分别输入M个子关键字 scanf("%d"，&(p->key[j]))；p->next=L；L=p；}returnL；}Rnode*SetList(){ //建待排序记录组72voidDistribute(Rnode*L，inti){//扫描链表L，按第i个关键字将各记录分配到相应的链队列中

Rnode*p；inti，j；for(i=0；i<=RAX-1；++i)//将RAX个链队列初始化为空 f[i]=r[i]=NULL；p=L；while(p!=NULL){L=L->next；j=p->key[i]；//用记录中第i位关键字的值即为相应的队列号if(f[j]==NULL)f[j]=p；//将节点*p分配到相应的链队列中f[j]elser[j]->next=p；r[j]=p；r[j]->next=NULL；p=L；}}voidDistribute(Rnode*L，inti73Rnode*Collect(){//从链队列f[0]开始，依次收集各链队列中的节点Rnode*L；inti=0，j；while(f[i]==NULL)i++；//查找第一个不空的链队列L=f[i]；for(j=i，k=i+1；k<=RAX-1；++k)if(f[k]!=NULL){r[j]->next=f[k]；j=k；}returnL；}Rnode*Collect(){74Rnode*RadixSort(intn){//对n个记录进行基数排序Rnode*L；L=SetList()； //建待排序记录组成的单链表Lfor(i=M-1；i>=0；--i){ //分别按M个子关键字对待排序列进行分配和收集Distribute(L，i)；L=Collect()；}returnL；}Rnode*RadixSort(intn){//对75从算法中容易看出，对于ｎ个记录（每个记录含M个子关键字，每个子关键字的取值范围为RAX个值）进行链式排序的时间复杂度为Ｏ(M(ｎ+RAX))，其中每一趟分配算法的时间复杂度为Ｏ(ｎ)，每一趟收集算法的时间复杂度为Ｏ(RAX)，整个排序进行M趟分配和收集，所需辅助空间为２×RAX个队列指针。当然，由于需要链表作为存储结构，则相对于其它以顺序结构存储记录的排序方法而言，还增加了ｎ个指针域空间。从算法中容易看出，对于ｎ个记录（每个记录含M76习题1、在循环队列中，判断队空和队满有几种方法。2、简述基数排序问题的算法思路。3、假设CQ[1..10]是一个循环队列，初始状态为front=rear=1，画出做完下列运算后队列的头尾指针的状态变化情况，若不能入队，请指出元素，并说明理由。d，e，b，g，h入队d，e出队i，j，k，l，m入队b出队n，o，p，q，r入队习题774、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

4、设循环队列的容量为40（序号从0到39），现经过一系列的78TheendTheend79☞5.1队列的基本概念5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用☞5.1队列的基本概念第5章队列及其应用80☞5.1.1队列的定义5.1.2队列的基本运算

5.1队列的基本概念☞5.1.1队列的定义5.1队列的基本概念81定义队列是满足下列条件的数据元素集合：(1)有限个具有相同数据类型的数据元素的集合，D={ai|i=1，2，…，n}，ai为数据元素。(2)数据元素之间的关系为R={<ai，ai+1>|ai，ai+1∈D，i=1，2，…，n}；(3)a1为队头元素，an为队尾元素；数据元素按a1，a2，…，an的次序入队，也以相同的次序出队。

定义队列是满足下列条件的数据元素集合：82由定义可以看出，队列是由一组同类型数据元素(a1，a2，…，an)组成的线性序列。其中，ai(1≤i≤n)可以是原子类型(如整型、实型、字符型等)、或是结构类型的数据元素。在一个队列中，元素ai-1是ai的唯一直接前驱，ai+1是ai的唯一直接后继；而队头元素a1无前驱，队尾元素an无后继。因此，队列属于线性逻辑结构。

由定义可以看出，队列是由一组同类型数据元素(a183即：队列是限定仅在一端进行插入，而在另一端进行删除操作的线性表。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。即：队列是限定仅在一端进行插入，而在另一端进行删除操作的线性84队列的特点

☞根据队列的定义可知，最先入队的元素也是最先出队。

☞特点：先进先出（FIFO）

也就是说，队列是一种先进先出(FirstInFirstOut)的线性表，简称为FIFO表。

a1a2a3…………an出队列入队列队头front队尾rear队列的特点a1a2a3…………an出队列入队列855.1.1队列的定义☞5.1.2队列的基本运算

5.1队列的基本概念5.1.1队列的定义5.1队列的基本概念86☞定义在该逻辑结构上的运算有以下几种基本运算：

(1)置空队：InitQueue(Q)，InitQueue运算的结果是将队列Q置成空队列。(2)判队空：QueueEmpty(Q)，如果队列为空，则QueueEmpty返回1，否则QueueEmpty返回0。(3)判队满：QueueFull(Q)，如果队满，则QueueFull返回1，否则QueueFull返回0。

☞定义在该逻辑结构上的运算有以下几种基本运算：87(4)入队：Add(Q，x)，Add在队列Q的队尾插入元素x。(5)出队：Delete(Q)，Delete从队列Q中删除队头元素。

(4)入队：Add(Q，x)，Add在队列Q的队尾插885.1队列的基本概念☞5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用5.1队列的基本概念第5章队列及其应用89☞5.2.1顺序队列的概念及数据类型5.2.2循环队列5.2.3循环队列的运算实现5.2顺序队列及其基本算法☞5.2.1顺序队列的概念及数据类型5.2顺序队列及其基90☞

采用顺序存储结构的队列称为顺序队列。☞它是利用一批地址连续的存储单元依次存放自队头到队尾的数据元素,同时设一个尾指针rear指向队尾元素的当前位置。☞由于队列的操作是删除在头、插入在尾，可另设一头指针front指向队头的位置，我们约定指向队头的前一个位置。☞通常用一维数组来实现队列的顺序存储。顺序队列☞采用顺序存储结构的队列称为顺序队列。顺序队列91typedefstruct{datatypedata[maxlen];intfront,rear;}SeqQueue;SeqQueue*Q;0123maxlen-1nfrontrear··················dataQ顺序队列的数据类型：typedefstruct{0123maxlen-920123maxlen-1nfrontrear··················dataQ☞

front和rear的初始值在队列初始化时均置为０。☞

入队时尾指针加１，并将新元素插入所指的位置。出队时头指针加１，然后删去所指的元素，并返回被删元素。

约定：在非空队列里，头指针始终指向队头元素前的空位，而尾指针始终指向队尾元素。0123maxlen-1nfrontrear········93０１２３0123

(a)队列初始为空０１２３（c)a出队frontrearfront（b）a,b,c入队abcfrontabcfrontbc(d)b出队０１２３frontrearrearrearrearrearfront０１２３94☞队空：Q->front=Q->rear☞队满：Q->rear=maxsize-1☞队长：Q->rear-Q->front☞入队：将队尾指针加一，即Q->rear=Q->rear+1，再将新元素按rear指示位置加入☞出队：将队头指针加一，即Q->front

=Q->front

+1，再将front指示的元素取出。此时：☞队空：Q->front=Q->rear此时：95可以看出：

☞尾指针rear已指到数组的最后一个元素，即rear=maxlen-1,若这时入队，则产生“溢出”；

☞此时经过一定数量的出队后，头指针front可指向队列的中间，即数组的前面部分有闲置的空间——这种有可用空间存在的溢出称“假溢出”问题：如何利用数组前面的可用空间？可以看出：965.3.1顺序队列的数据类型☞5.3.2循环队列5.3.3循环队列的运算实现5.3队列的顺序存储5.3.1顺序队列的数据类型5.3队列的顺序存97问题的提出：在顺序队列中，入队时在队尾增加元素，尾指针rear后移；出队时，则是头指针front后移。这样，在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用，在进行一定数量的入队和出队后，可能会出现有可用空间存在的溢出——“假溢出”循环队列问题的提出：在顺序队列中，入队时在队尾增加元素，尾指针re98解决的方法：将data[0]看作是data[maxlen-1]后的下一个存储位置。

即：将向量空间看成是一个首尾相接的圆环。并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（maxsize-1）时，其加1操作的结果是指向向量的下界0。解决的方法：将data[0]看作是data[maxlen-99

显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。0123456frontghkefrontabfrontfrontreardrearrearrearrearfrontrear例：循环队列的操作显然，因为循环队列元素的空间可以被利用，除1005.3.1顺序队列的数据类型5.3.2循环队列☞5.3.3循环队列的运算实现5.3队列的顺序存储5.3.1顺序队列的数据类型5.3队列的顺序存101讨论：在循环队列中执行入队和出队操作：入队：

if(Q->rear==maxlen–1)Q->rear=0;elseQ->rear=Q->rear+1;Q->data[Q->rear]=x；0123456ghkefrontdrearrearrearrear入队：讨论：在循环队列中执行入队和出队操作：入队：if(Q102或采用模运算：

Q->rear=(1+Q->rear)%maxlen

Q->data[Q->rear]=x；或采用模运算：103或Q->front=(1+Q->front)%maxleneabdrear0123456frontfrontfrontkfront出队：if(Q->front==maxlen–1)Q->front=0;elseQ->front=Q->front+1;或Q->front=(1+Q->front)104frontghkeabdrear0123456frontghkeabdrear0123456rearrearrearrearfrontfrontfrontfrontfrontfront入队出队队满队空讨论：队空与队满的描述frontghkeabdrear0123456frontgh105队空：Q->rear=Q->front队满：Q->rear=Q->front可见，队空与队满有相同的描述方式：问题：如何区分队空与队满状态？队空：Q->rear=Q->front可见，队空与队满有106解决方法：

(1)

设置一入队或出队标志，以区分最后一次操作是入队还是出队。这样，当头尾两个指针相等时，由该标志可以判断出满和空。(2)

少用一个元素空间，即将仅剩一个空位置时的状态当作满状态，也就是不让rear指针赶上front指针。解决方法：107fronthkeabdrear0123456fronthkeabdrear0123456rearrearrearfrontfrontfrontfrontfrontfront入队出队队满:(1+Q->rear)%maxlen==Q->front

队空Q->rear==Q->front即：fronthkeabdrear0123456fronthke108基于方法(2)的各算法描述如下：

(1)置空队

按前面的讨论，队列为空时，其头尾指针相等。

SeqQueue*

InitQueue(SeqQueue*Q){Q->front=0；Q->rear=0；returnQ；}

基于方法(2)的各算法描述如下：109(2)判队空将头尾指针是否相等作为队列是否为空的等价条件。

intQueueEmpty(SeqQueue*S){if(Q->front==Q->rear)return1；elsereturn0；//队空时返回1，不空返回0}

(2)判队空将头尾指针是否相等作为队列是否为空的等110(3)判队满按前面的约定，“队满”是指仅剩一个空位置时的状态，即：尾指针的下一个位置就是头指针所指的位置。intQueueFull(SeqQueue*Q){if(Q->front==(Q->rear+1)%maxlen) return1；elsereturn0；//队满时返回1，不满返回0}

(3)判队满按前面的约定，“队满”是指仅剩一111(4)取队头元素首先要判断队是否空，然后才能求解。

datatypeGetHead(SeqQueue*Q){datatypex;if(QueueEmpty(Q))return(error);else{x=Q->data[(Q->front+1)%maxlen];returnx;}}(4)取队头元素首先要判断队是否空，然后才能求112(5)入队入队前，要判断队是否满

voidAdd(SeqQueue*S，Datatypex){if(!QueueFull(Q)){//若队不满，则进行入队运算 Q->rear=(Q->rear+1)%maxlen；Q->data[Q->rear]=x；}elseprintf(“queuefull”)；}

(5)入队入队前，要判断队是否满113(6)出队出队前，判断队是否空。

voidDelete(SeqQueue*S){if(!QueueEmpty(Q))//若队不空，则进行出队运算 Q->front=(Q->front+1)%maxlen； elseprintf(“queueempty”)；}

(6)出队出队前，判断队是否空。114思考题：1、如何求解队列中元素的个数？2、如果对前面所讨论的循环队列采用设置运算标志的方法来区分队列的满和空的状态，试给出对应的各运算的实现。思考题：1、如何求解队列中元素的个数？115循环队列基本算法性能分析

可以看出，循环队列的各基本运算均与队列中元素的个数无关，即与问题的规模无关，其出队与入队运算也不需要移动元素。所以，各基本运算的时间复杂度均为O(1)。

另外。循环队列的5种基本运算执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各算法的空间性能均较好。只是对于data数组长度的定义很难把握好，如果定义过大，会造成必不可少的空间浪费。循环队列基本算法性能分析1165.1队列的基本概念5.2顺序队列及其基本算法☞5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用5.1队列的基本概念第5章队列及其应用117☞5.3.1链队列的概念及数据类型5.3.2链队列的运算实现

5.3链队列及其基本运算☞5.3.1链队列的概念及数据类型5.3链队列及其基本118链队列

☞队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。链队列119a2an∧a1frontrear头结点队头结点队尾结点typedefstruct{LinkList*front,*rear;}LinkQueue;

LinkQueue*Q;链队列的类型Qa2an∧a1frontrear头结点队头结点队尾结点t120则头指针为Q－>front尾指针为Q－>rear这样，确定了头指针和尾指针后，在链队列上实现上述的运算可参照链表的运算。

a2an∧a1frontrearQ则头指针为Q－>fronta2an∧a1fro1215.3.1链队列的概念及数据类型☞5.3.2链队列的运算实现

5.3链队列及其基本运算5.3.1链队列的概念及数据类型5.3链队列及其122(1)建空队∧QSeqQueue*SetQueue(){LinkQueue*Q；Q=malloc(sizeof(LinkQueue))；Q->front=malloc(sizeof(Linklist))；Q->front->next=NULL；Q->rear=Q->front；returnQ；}(1)建空队∧QSeqQueue*SetQueue()123(2)判队空intQueueEmpty(LinkQueue*Q){if(Q->front==Q->rear)return1；elsereturn0；//队空时返回1，不空返回0}(3)链队列不存在队满。(2)判队空intQueueEmpty(LinkQu124(4)入队入队时，仅对队尾操作p∧a2ana1frontrearQx∧(4)入队入队时，仅对队尾操作p∧a2ana1frontr125LinkQueue*Add(LinkQueue*Q，Datatypex){

//将元素x入队列QLinkQueue*p；p=malloc(sizeof(Linklist))；//建立新节点空间，以存放xp->data=x；p->next=NULL；Q->rear->next=p； //将新节点插入到尾节点后Q->rear=p； //尾指针指向新的尾节点returnQ；}LinkQueue*Add(LinkQueue*Q，D126(5)出队考虑:(1)出队时，在链表中删除队头结点。(2)若队列Q中只有一个元素时怎么操作?pua2an∧a1frontrearQ(5)出队考虑:(1)出队时，在链表中删除队头结点。pua127

p=Q->front->nextQ->front->next=p–>nextpif(Q->rear==p)Q->rear=Q->front;a1a2an∧frontrearQ出队操作：考虑队列中只有一个元素时free(p);若队列Q中只有一个元素时怎么操作?p=Q->front->nextpi128LinkQueue*Delete(LinkQueue*Q){Linklist*p；if(!QueueEmpty(Q)){//若队不空，则进行出队运算p=Q->front->next；Q->front->next=p->next；if(p->next=NULL)//若链队列的长度为1，需修改尾指针Q->rear=Q->front；free(p)；returnQ；}elseprintf(“queueempty”)；}LinkQueue*Delete(LinkQueue*129链队列基本算法性能分析

可以看出，链队列实际上是运算受限制的链表，其插入和删除运算在表的两端进行。所有基本运算均与队列的长度无关，算法的时间复杂度为O(1)。链队列的空间性能与链表的空间性能相同。链队列基本算法性能分析1305.1队列的基本概念5.2顺序队列及其基本算法5.3链队列及其基本算法☞5.4队列的应用举例——基数排序问题第5章队列及其应用5.1队列的基本概念第5章队列及其应用131一、多关键字排序

在许多实际的排序的应用中，所涉及的排序字段往往不止一个。例如：对一个学生成绩表（线性表）进行排序。表中每一个记录有三个域：姓名、总分、数学成绩。要求先按总分排序，对总分相同的记录再按数学分数排序。——这个排序问题涉及两个字段。一、多关键字排序在许多实际的排序的应用中，所涉及的132下面，我们以一副扑克牌的排序过程为例，介绍多关键字排序的方法。

我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。若规定花色和面值的顺序如下：花色：梅花<方块<红桃<黑桃面值：A<2<3<…<10<J<Q<K下面，我们以一副扑克牌的排序过程为例，介绍多关键字排133进一步规定花色的高于面值，则一副扑克牌从小到大的顺序为：梅花A，2，…K；方块A，2，…K；红桃A，2，…K；黑桃A，2，…K。

具体进行排序时有两种做法，其中一种是先按花色分成有序的四类，然后再按面值对每一类从小到大排序。该方法称为“高位优先”排序法。进一步规定花色的高于面值，则一副扑克牌从小到大的顺序为134另一种做法是分配与收集交替进行。

首先按面值从小到大把牌摆成13叠（每叠4张牌），然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4叠，每叠有13张牌，最后把这4叠牌按花色的次序收集到一起，于是就得到了上述有序序列。该方法称为“低位优先”排序法，如下图所示。另一种做法是分配与收集交替进行。135队列及其应用课件136二、链式基数排序基数排序属于上述“低位优先”排序法，通过反复进行分配与收集操作完成排序。下面我们以实例来介绍基数排序的思想。【例】一组记录的关键字为：(278，109，63，930，589，184，505，269，8，83)试采用基数排序方法对其进行排序。二、链式基数排序137(278，109，63，930，589，184，505，269，8，83)我们将上述单关键字看成由若干个关键字复合而成。

上述这组关键字的值都在0≤K≤999的范围内，我们可以把每一个数位上的十进制数字看成是一个关键字，即将关键字K看成由三个关键字K0，K1，K2组成。其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。

(278，109，63，930，589，184，505，26138因为十进制的基数是10，所以，每个数位上的数字都可能是0～9中的任何一个。我们先按关键字K2来分配所有参与排序的元素，将K2=0的元素放在一组、K2=1的元素放在一组、……、K2=9的元素放在一组。

因为十进制的基数是10，所以，每个数位上的数字都可能139再按K2的值由0到9的顺序收集各组元素，形成序列(930,063,083,184,505,278,008,109,589,269)再按K2的值由0到9的顺序收集各组元素，形成序列140对上述序列中的元素再按关键字K1来分配。然后，再按K1的值由0到9的顺序收集各组元素，形成序列(505，008，109，930，063，269，278，083，184，589)。

对上述序列中的元素再按关键字K1来分配。然后，再按K1的值由141对上述序列中的元素再按关键字K0来分配。然后，再按K0的值由0到9的顺序收集各组元素，形成序列(008，063，083，109，184，267，278，505，589，930)问题2：这10个“容器”是什么？数据结构？问题1：基数排序思想？对上述序列中的元素再按关键字K0来分配。然后，再按K0的值由142可以看出，基数排序的思想是：

首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序。以此类推，由低位到高位，由次关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键字(主关键字)对记录进行排序后，基数排序完成。可以看出，基数排序的思想是：首先将待排序的记录分成143链式基数排序算法实现的技术要点：

要实现上述基数排序的过程，需要解决3个问题。问题一：每次分配记录所形成的各组序列以何种结构存储？问题二：如何收集各组记录？问题三：如何描述由待排序关键字分成的若干个子关键字？链式基数排序算法实现的技术要点：144由上例可以看出，各组记录的收集是本着“先进入该组的记录将首先被收集”的原则。这与队列的“先进先出”的原则相一致。这样，各组序列就以队列来描述。因为要进行多次的分配与收集，为节省存储空间及运算方便，我们采用链队列来存储各组序列。由上例可以看出，各组记录的收集是本着“先进入该组的记145

链队列的数量与基数一致，若基数为RAX，则令f[0]～f[RAX-1]分别指向RAX个链队列的队头节点，令r[0]～r[RAX-1]分别指向RAX个队列的队尾节点。每次分配前，将RAX个链队列置空：for(i=0；i<=RAX-1；++i)f[i]=r[i]=NULL；

。链队列的数量与基数一致，若基数为RAX，则令f[146

对各链队列所表示的序列进行收集时，应从链队列f[0]开始，当链队列f[j+1]不为NULL时，将链队列f[j]与其首