第4章

隊列主講教師：張彬連吉首大學(xué)4.1知識簡介

隊列（queue）是限定在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表。將插入的一端稱為隊尾（rear），刪除的一端稱為隊頭（front）。

假設(shè)隊列有n個元素(a1,a2,…,an)，稱a1為隊頭元素，an為隊尾元素。隊列中的元素按照a1,a2,…,an進(jìn)入隊列，退出隊列也只能按照這個次序依次退出。隊列的操作是按照先進(jìn)先出的原則進(jìn)行的，所以隊列也稱為先進(jìn)先出（FirstInFirstOut，F(xiàn)IFO）的線性表。隊列的示意圖如下圖所示。4.1.1隊列的定義4.1知識簡介

采用順序存儲結(jié)構(gòu)的隊列稱為順序隊列，在順序隊列中附設(shè)兩個整型變量front和rear分別指示對頭元素和隊尾元素的位置。為了使所有位置操作一致，rear實際指向隊尾元素的下一個位置。4.1.2隊列的順序存儲——循環(huán)隊列

隊列的順序存儲結(jié)構(gòu)描述如下：#defineMAXSIZE100;//順序隊列的最大長度typedefstruct{QElemType*base;//存儲空間的首地址intfront;//隊頭位置intrear;//隊尾位置

}SqQueue;4.1知識簡介

在順序隊列中出隊和入隊操作都是往空間后面的方向移動，從而導(dǎo)致假溢出。為了解決假溢出，將存儲隊列的數(shù)組頭尾相接，形成一個環(huán)，稱為循環(huán)隊列。循環(huán)隊列通過求模運算來實現(xiàn)。如果不做任何處理，在循環(huán)隊列中隊空和隊滿的條件是相同的。為了區(qū)分隊空和隊滿，采用少用一個元素空間的方法來解決，即當(dāng)隊列空間大小為n時，有n-1個元素時就認(rèn)為隊滿。4.1.2隊列的順序存儲——循環(huán)隊列

循環(huán)隊列Q中隊空和隊滿的條件為：隊空的條件：Q.front=Q.rear隊滿的條件：(Q.rear+1)%MAXSIZE=Q.front4.1知識簡介

當(dāng)進(jìn)行入隊操作時，隊列不能為滿，當(dāng)進(jìn)行出隊操作時，隊列不能為空。注意隊列空時，Q.front和Q.rear不一定等于0。循環(huán)隊列的隊空和隊滿如下圖所示。4.1.2隊列的順序存儲——循環(huán)隊列4.1知識簡介

采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的隊列稱為鏈隊列。通常用單鏈表來表示鏈隊列。一個鏈隊列需要兩個分別指向隊頭和隊尾的指針才能唯一確定。4.1.3隊列的鏈?zhǔn)酱鎯Α滉犃?/p>

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)描述如下：typedefstructQNode{//結(jié)點類型

QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;4.1知識簡介

為了操作方便，給鏈隊列添加一個頭結(jié)點，隊頭指針始終指向頭結(jié)點。下圖所示為一個非空鏈隊列Q，Q.front指向頭結(jié)點。圖4-3(b)顯示了一個空的鏈隊列，Q.front指向頭結(jié)點，Q.rear也指向頭結(jié)點，Q.front和Q.rear相等。4.1.3隊列的鏈?zhǔn)酱鎯Α滉犃?.1知識簡介4.1.3隊列的鏈?zhǔn)酱鎯Α滉犃?/p>

下圖所示為一個空的鏈隊列，Q.front指向頭結(jié)點，Q.rear也指向頭結(jié)點，Q.front和Q.rear相等。

鏈?zhǔn)疥犃性谶M(jìn)行入隊操作時，不存在空間限制。在進(jìn)行出隊操作時，隊列不能為空，當(dāng)Q.front=Q.rear時，鏈隊列為空，此時不能進(jìn)行出隊操作。4.2實驗?zāi)康?/p>

通過本章的實驗，加深對隊列的性質(zhì)、隊列的順序存儲和鏈?zhǔn)酱鎯σ约盎静僮鞯戎R的理解，培養(yǎng)學(xué)生用隊列解決實際問題的能力，同時鍛煉學(xué)生實際編程和算法設(shè)計的能力。4.3實驗范例

循環(huán)隊列的實現(xiàn)。要求建立可以處理整數(shù)的循環(huán)隊列，并實現(xiàn)入隊、出隊等基本操作。4.3.1范例14.3實驗范例1、問題分析4.3.1范例1

循環(huán)隊列的入隊和出隊操作不需要移動元素，只需改變頭尾的位置即可。在具體實現(xiàn)時，循環(huán)隊列使用一段連續(xù)的空間來存儲隊列元素，有兩個下標(biāo)，一個是隊首元素位置front，另一個是隊尾位置下標(biāo)rear，用于指示隊尾元素的下一個位置。在插入元素（入隊操作）時，只需將元素插入到rear指示的位置，并將rear向后移動一位；在刪除元素（出隊操作）時，只需將front指示位置的元素刪除，并將front向后移動一位。在入隊和出隊操作時，為了保證front和rear的正確性，當(dāng)front和rear加1后需對隊列的最大長度取余。

在編程實現(xiàn)時，先應(yīng)定義隊列數(shù)據(jù)結(jié)構(gòu)，然后將隊列進(jìn)行初始化，分配存放隊列元素的空間，然后再設(shè)計入隊和出隊等操作函數(shù)。4.3實驗范例2、算法描述4.3.1范例1

先將隊列元素類型定義為整型，然后定義隊列結(jié)構(gòu)體類型。#defineMAXSIZE100//順序隊列的最大長度typedefintQElemType;typedefstructSqQueue{QElemType*base;//存儲空間的首地址

intfront;//隊頭位置

intrear;//隊尾位置

}SqQueue;4.3實驗范例2、算法描述4.3.1范例1

初始化循環(huán)隊列。在初始化隊列的時候，主要是為該隊列分配存放元素的空間，調(diào)用malloc()函數(shù)實現(xiàn)，分配MAXSIZE*sizeof(QElemType)字節(jié)大小的空間，并將空間首地址賦值給base。如果空間分配失敗，則退出程序。如果分配成功，則初始化隊頭和隊尾位置，將rear和front初始化為0（對應(yīng)數(shù)組的0下標(biāo)）。接著返回1表示操作成功。

4.3實驗范例2、算法描述4.3.1范例1intInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));if(!Q.base){exit(-1);//內(nèi)存分配失敗，退出程序}Q.front=Q.rear=0;return1;//初始化成功}

初始化循環(huán)隊列函數(shù)可以定義如下：

4.3實驗范例2、算法描述4.3.1范例1

入隊列操作需先判斷隊列是否已滿，如果已滿則返回0，表示入隊失??；否則，將元素添加到隊尾的位置，即Q.base[Q.rear]。接著將rear后移一個位置，確保循環(huán)隊列的循環(huán)使用，rear加1后需對最大長度取余，即(Q.rear+1)%MAXSIZE來更新隊尾指針的位置。4.3實驗范例2、算法描述4.3.1范例1intEnQueue(SqQueue&Q,QElemTypee){//檢查隊列是否已滿if((Q.rear+1)%MAXSIZE==Q.front){return0;//隊列已滿，入隊失敗}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return1;//入隊成功}將元素item加入隊列Q的函數(shù)EnQueue定義如下：4.3實驗范例2、算法描述4.3.1范例1

出隊操作需先判斷隊列是否為空，如果為空則返回0，表示出隊失敗；否則，列不為空，先取出隊首元素Q.base[Q.front]，并將其賦值給item。接著將front后移一個位置，確保循環(huán)隊列的循環(huán)使用，front加1后需對最大長度取余，即(Q.front+1)%MAXSIZE來更新隊首指針的位置，將item中的值返回。4.3實驗范例2、算法描述4.3.1范例1intDeQueue(SqQueue&Q,QElemType&e){//檢查隊列是否為空if(Q.rear==Q.front){return0;//隊列為空，出隊失敗}e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;return1;//出隊成功}出隊函數(shù)DeQueue定義如下：4.3實驗范例2、算法描述4.3.1范例1voidPrintQueue(SqQueueQ){intpos=Q.front;//從隊頭開始while(pos!=Q.rear){printf("%d",Q.base[pos]);pos=(pos+1)%MAXSIZE;}printf("\n");}

接著定義函數(shù)輸出循環(huán)隊列中的元素，從隊頭位置開始，一直到隊尾位置逐個輸出。輸出元素的函數(shù)可以定義如下：4.3實驗范例2、算法描述4.3.1范例1

在主函數(shù)中分別調(diào)用這些函數(shù)，檢查操作是否正確。先定義循環(huán)隊列q，接著初始化隊列q，將1到10這10個數(shù)逐個入隊，然后輸出隊列中的元素。接著將隊列中的前5個數(shù)出隊并逐個輸出，最后輸出出隊后隊列中的元素。4.3實驗范例2、算法描述4.3.1范例1intmain(){SqQueuemyQueue;inti;InitQueue(myQueue);//入隊操作示例，將1到10逐個入隊for(i=1;i<=10;i++){EnQueue(myQueue,i);}printf("入隊后隊列中的元素:\n");PrintQueue(myQueue);main函數(shù)定義如下：//出隊操作示例，將前5個元素出隊printf("將5個元素出隊：\n");QElemTypeitem;for(i=1;i<=5;i++){DeQueue(myQueue,item);printf("%d",item);}printf("\n");printf("出隊后隊列中的元素:\n");PrintQueue(myQueue);return0;}4.3實驗范例3、算法分析4.3.1范例1

因為隊列的出隊、入隊操作不需要移動元素，直接修改front和rear即可，因此這些函數(shù)的復(fù)雜度都為O(1)。遍歷隊列中的元素需要逐個輸出隊列中的元素，所以輸出的時間復(fù)雜度為O(n)。4.3實驗范例

鏈隊列的實現(xiàn)。要求：建立一個鏈隊列處理整型數(shù)據(jù)，并在鏈隊列上實現(xiàn)入隊、出隊等基本操作。4.3.2范例24.3實驗范例1、問題分析4.3.2范例2

為了建立隊列，首先需要定義一個鏈隊列結(jié)點類型用于存儲隊列中的元素。接著定義鏈隊列類型，鏈隊列包括兩個指針：front指針指向隊頭結(jié)點，rear指針指向隊尾結(jié)點。接著初始化隊列，初始化隊列就指向頭結(jié)點。

入隊操作即在鏈隊列的尾部插入一個新結(jié)點。具體實現(xiàn)方法是，先創(chuàng)建一個新的結(jié)點，將需要入隊的元素存儲在新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到原來的隊尾結(jié)點之后，最后更新隊尾指針為新結(jié)點。4.3實驗范例1、問題分析4.3.2范例2

出隊操作即刪除鏈隊列的頭部結(jié)點，并返回其存儲的元素。具體實現(xiàn)方法是，先將隊頭結(jié)點從鏈隊列中摘除，然后將隊頭指針指向新的隊頭結(jié)點，最后返回被刪除結(jié)點的數(shù)據(jù)域。如果刪除的結(jié)點同時也是隊尾結(jié)點，此時須將隊尾指針rear指向頭結(jié)點。4.3實驗范例2、算法描述4.3.2范例2

先定義結(jié)點類型，然后定義鏈隊列類型。typedefstructQNode{QElemTypedata;//數(shù)據(jù)域structQNode*next;//指針域}QNode,*QueuePtr;typedefstructLinkQueue{QueuePtrfront;//隊頭指針QueuePtrrear;//隊尾指針}LinkQueue;4.3實驗范例2、算法描述4.3.2范例2LinkQueue是隊列類型，內(nèi)部有兩個指針，一個指向隊頭結(jié)點一個指向隊尾結(jié)點。因此，初始化空鏈隊列就是要初始化LinkQueue中的front和rear，將兩個指針都指向頭結(jié)點。初始化鏈隊列Q的函數(shù)設(shè)計如下：intInitQueue(LinkQueue&Q){Q.front=(QNode*)malloc(sizeof(QNode));//生成頭結(jié)點if(Q.front==NULL)//生成結(jié)點失敗exit(-1);Q.rear=Q.front;//尾指針指向頭結(jié)點Q.front->next=NULL;//將頭結(jié)點next域賦空return1;}4.3實驗范例2、算法描述4.3.2范例2

初始化之后就可以將元素入隊，入隊就是在鏈表的尾部插入新結(jié)點。先創(chuàng)建一個新結(jié)點，然后將數(shù)據(jù)存入新結(jié)點的數(shù)據(jù)域，再把新結(jié)點加入到隊列的尾部并更新尾指針（剛加入的結(jié)點是新的尾結(jié)點）。4.3實驗范例2、算法描述4.3.2范例2

在鏈隊列Q中加入一個新的數(shù)據(jù)e的函數(shù)如下：intEnQueue(LinkQueue&Q,QElemTypee){QNode*s=(QNode*)malloc(sizeof(QNode));//生成結(jié)點if(s==NULL)//生成結(jié)點失敗return0;s->data=e;//將e存入結(jié)點的數(shù)據(jù)域s->next=NULL;Q.rear->next=s;//將結(jié)點s插到隊尾Q.rear=s;//隊尾指針后移return1;}4.3實驗范例2、算法描述4.3.2范例2

出隊操作是將隊頭元素出隊。在進(jìn)行該操作時，先應(yīng)判斷隊列是否為空，如果隊列為空，則操作失敗。否則，將隊頭結(jié)點從隊列中摘除，并把出隊結(jié)點中的數(shù)據(jù)保存到變量e，再釋放該結(jié)點所占內(nèi)存空間，最后返回出隊元素。如果刪除的結(jié)點剛好是隊尾結(jié)點，刪除后需將隊尾指針rear指向頭結(jié)點。4.3實驗范例2、算法描述4.3.2范例2

出隊函數(shù)定義如下：intDeQueue(LinkQueue&Q,QElemType&e){QNode*s;if(Q.front==Q.rear)return0;

//隊空

s=Q.front->next;//s指向隊頭元素Q.front->next=s->next;//將隊頭元素從隊列中移出if(Q.rear==s)//如果刪除的結(jié)點就是尾結(jié)點Q.rear=Q.front;//尾指針指向頭結(jié)點e=s->data;//將刪除的元素保存free(s);//釋放被刪除結(jié)點return1;}4.3實驗范例2、算法描述4.3.2范例2

如果在程序中不再使用已有的鏈隊列時，應(yīng)該將其銷毀從而釋放內(nèi)存空間。銷毀鏈隊列時一般從頭部開始逐個刪除結(jié)點并釋放結(jié)點的內(nèi)存空間。在刪除結(jié)點時，以免在刪除結(jié)點后無法訪問到下一個結(jié)點，釋放結(jié)點時，需要先保存該結(jié)點的下一個結(jié)點的地址。4.3實驗范例2、算法描述4.3.2范例2

銷毀鏈隊列函數(shù)定義如下：voidDestroyQueue(LinkQueue&Q){QNode*s;while(Q.front!=NULL)//隊列不空{(diào)s=Q.front->next;//保存隊頭結(jié)點的下一個結(jié)點的地址free(Q.front);//釋放隊頭結(jié)點Q.front=s;}Q.rear=NULL;}4.3實驗范例2、算法描述4.3.2范例2

在對隊列進(jìn)行入隊和出隊操作后，需要檢測操作是否成功，或者要查看隊列中有哪些元素，而不是把隊列中的元素出隊，可以設(shè)計一個輸出隊列中所有元素的函數(shù)，該函數(shù)相當(dāng)于遍歷一個鏈表。4.3實驗范例2、算法描述4.3.2范例2

輸出隊列中元素的函數(shù)可定義如下：voidPrintQueue(LinkQueueQ){QNode*p;printf("隊列中的元素有：");p=Q.front->next;//從隊頭開始輸出while(p!=NULL)//直到隊尾的前一個位置{printf("%5d",p->data);p=p->next;}printf("\n");}4.3實驗范例2、算法描述4.3.2范例2

函數(shù)設(shè)計完之后便可以在main()中進(jìn)行驗證，先定義一個鏈隊列，然后初始化該鏈隊列，元素入隊，輸出隊列中元素，出隊，再輸出隊列中的元素，銷毀等。4.3實驗范例2、算法描述4.3.2范例2main()函數(shù)可以定義如下：#include<stdlib.h>#include<stdio.h>typedefintQElemType;intmain()//主函數(shù){LinkQueueque;//定義一個鏈隊列QElemTypevalue;intnum,i;if(InitQueue(que)){printf("隊列初始化成功！\n");//入隊printf("輸入需要入隊的元素個數(shù)：");scanf("%d",&num);i=1;printf("輸入需要入隊的元素：");while(i<=num){scanf("%d",&value);if(EnQueue(que,value)==1)printf("%d入隊成功！\n",value);else{printf("%d入隊失??！\n",value);break;}i++;

}4.3實驗范例2、算法描述4.3.2范例2main()函數(shù)可以定義如下：PrintQueue(que);//出隊if(DeQueue(que,value)==1){printf("隊頭元素出隊成功！\n");printf("出隊的元素為：%5d\n",value);PrintQueue(que);}else{printf("隊頭元素出隊失??！\n");}DestroyQueue(que);}return0;}4.3實驗范例3、算法分析4.3.2范例2

在進(jìn)行入隊和出隊操作時，只需要在隊尾插入新結(jié)點或者刪除隊頭結(jié)點，因此只需修改隊尾指針或者隊頭指針的指向即可，它們的時間復(fù)雜度都為O(1)。在打印輸出隊列中所有元素時，需要從隊頭開始依次訪問每個結(jié)點，因此時間復(fù)雜度為O(n)，其中n為隊列的長度。4.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：使用隊列打印楊輝三角

楊輝三角是公元1261年，我國宋代數(shù)學(xué)家楊輝在其著作《詳解九章算法》中給出的一個用數(shù)字排列起來的三角形陣。由于楊輝在書中引用了賈憲著的《開方作法本源》和“增乘開方法”，因此這個三角形也稱“賈憲三角”。在歐洲，這個三角形叫帕斯卡三角形，是帕斯卡在1654年研究出來的，比楊輝晚了近400年時間。楊輝三角是中國古代數(shù)學(xué)的杰出研究成果之一，它把二項式系數(shù)圖形化，把組合數(shù)內(nèi)在的一些代數(shù)性質(zhì)直觀地從圖形中體現(xiàn)出來，是一種離散型地數(shù)與形的結(jié)合。4.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：使用隊列打印楊輝三角如上圖所示為楊輝三角的前7行。從圖可以看出，楊輝三角中第i行有i個數(shù)，每行數(shù)字是對稱的，每行的第一個和最后一個數(shù)是1，其他位置的數(shù)等于它上方兩數(shù)之和。4.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)2：實現(xiàn)一個簡單的銀行排隊叫號系統(tǒng)。

在銀行中，顧客經(jīng)常需要等待辦理業(yè)務(wù)，為了公平、有序地管理顧客的等待順序，并提高業(yè)務(wù)處理效率，銀行引入了排隊叫號系統(tǒng)。當(dāng)顧客進(jìn)入銀行時，他們會在排隊機上取一個號，這個號代表了顧客在隊列中的位置。當(dāng)銀行窗口的工作人員準(zhǔn)備好接待下一位顧客時，他們會按下叫號器上的按鈕，此時排隊系統(tǒng)會呼叫下一個號碼，被叫到號碼的顧客前往對應(yīng)的窗口辦理業(yè)務(wù)。系統(tǒng)可以實時監(jiān)測隊列長度、顧客預(yù)計等待時間等信息，并把這些數(shù)據(jù)反饋給銀行管理人員。管理人員根據(jù)這些數(shù)據(jù)可以靈活調(diào)整窗口開放數(shù)量、員工輪班時間等，以確保銀行運營的高效和顧客滿意度的提高。

要求：設(shè)計一個銀行排隊叫號系統(tǒng)，能模擬顧客到達(dá)取號、銀行工作人員準(zhǔn)備接待下一位顧客，系統(tǒng)檢測隊列長度、顧客預(yù)計等待時間等。4.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)3：實現(xiàn)鍵盤輸入循環(huán)緩沖區(qū)。

在操作系統(tǒng)中，當(dāng)程序正在執(zhí)行其他任務(wù)時，用戶可以從鍵盤上不斷鍵入所要輸入的內(nèi)容，很多文字處理軟件就是這樣工作的。系統(tǒng)在利用這種分時處理方法時，用戶鍵入的內(nèi)容不在屏幕上立刻顯示出來，直到當(dāng)前正在工作的那個進(jìn)程結(jié)束為止。但在這個進(jìn)程執(zhí)行時，系統(tǒng)是在不斷地檢查鍵盤狀態(tài)，如果檢測到用戶鍵入了一個新的字符，就立刻把它存到系統(tǒng)緩沖區(qū)中，然后繼續(xù)運行原來的進(jìn)程。在當(dāng)前工作的進(jìn)程結(jié)束后，系統(tǒng)就從緩沖區(qū)中取出鍵入的字符，并按要求進(jìn)行處理。4.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)3：實現(xiàn)鍵盤輸入循環(huán)緩沖區(qū)。

要求：寫一個模擬程序，假設(shè)有兩個進(jìn)程同時存在于一個應(yīng)用程序中，其中一個進(jìn)程在屏幕上連續(xù)顯示字符‘A’，與此同時，程序不斷檢測鍵盤是否有輸入，如果有輸入就讀入用戶輸入的字符并保存到緩沖區(qū)中。在用戶輸入時，鍵入的字符并不立即回顯在屏幕上。當(dāng)用戶鍵入一個逗號“，”時表示第一個進(jìn)程結(jié)束，第二個進(jìn)程從緩沖區(qū)中讀取那些已鍵入的字符并顯示在屏幕上。第二個進(jìn)程結(jié)束后，程序又進(jìn)入第一個進(jìn)程，重新顯示字符“A”，同時用戶又可以繼續(xù)鍵入字符，直到用戶輸入一個分號“；”鍵，才結(jié)束第一個進(jìn)程，同時也結(jié)束整個進(jìn)程。4.5任務(wù)提示

楊輝三角第1行是1，從第2行開始計算，計算第i行的同時輸出第i-1行的元素。每次將隊頭元素出隊，將出隊的元素和隊頭元素相加得到第i行的一個數(shù)，將該數(shù)入隊。每行需要計算i-2個數(shù)。在計算某行時，直接將第一個數(shù)1入隊，然后計算i-2個數(shù)并一一入隊，再將最后一個數(shù)1入隊。如果要求輸出n行，當(dāng)計算到第n行時，只輸出了前面的n-1行，第n行的數(shù)在隊列中，將隊列中的數(shù)一一出隊并輸出。任務(wù)1提示4.5任務(wù)提示算法的偽代碼描述如下：任務(wù)1提示voidYangHuiTriange(intn){InitQueue(Q);//初始化隊列QEnQueue(Q,1);//將第一行的1入隊for(i=2;i<=n;i++)//從第二行開始計算{EnQueue(Q,1);//將第一個元素1入隊//計算第i行后面的i-2個元素，并輸出第i-1行的元素for(j=1;j<=i-2;j++){DeQueue(Q,temp);//將隊頭元素出隊printf("%3d",temp);//輸出出隊元素GetFront(Q,x);//獲得隊頭元素

//計算當(dāng)前行的第j+1個元素temp=temp+x;EnQueue(Q,temp);//入隊}//將第i-1行的最后一個數(shù)出隊并輸出DeQueue(Q,x);printf("%3d",x);printf("\n");//換行

EnQueue(Q,1);//將第i行的最后一個數(shù)1入隊}//將最后一行的數(shù)輸出while(!IsEmpty(Q)){DeQueue(Q,x);printf("%3d",x);}}4.5任務(wù)提示

（1）顧客到達(dá)在排隊機上取一個號，相當(dāng)于顧客入隊操作。

（2）當(dāng)銀行窗口的工作人員按下叫號器準(zhǔn)備接待下一位顧客時，相當(dāng)于一個顧客出隊。

（3）系統(tǒng)實時監(jiān)測隊列長度、預(yù)計等待時間等信息，相當(dāng)于要遍歷隊列。

為了實現(xiàn)以上三個基本需求，首先需要定義一個隊列，隊列里面存放顧客信息。因為第（3）點有預(yù)計等待時間，因此應(yīng)該根據(jù)顧客需要辦理的業(yè)務(wù)類型如存款、取款、貸款、咨詢等對顧客需要的服務(wù)時間進(jìn)行估計。因此顧客的信息有在排隊機上取出的號碼、業(yè)務(wù)類型，預(yù)計服務(wù)時間等，而顧客本身的身份等信息不需要記錄在這個隊列。任務(wù)2提示4.5任務(wù)提示根據(jù)以上分析，先定義顧客類型結(jié)構(gòu)體如下：任務(wù)2提示typedefstructCustomerType{intno;//客戶編號

intbusinessType;//業(yè)務(wù)類型

intrequiredTime;//辦理業(yè)務(wù)需要的時間}CustomerType;4.5任務(wù)提示

然后定義一個隊列，因為銀行不可能無限制接收顧客排隊（如銀行下班之前不會讓顧客拿了號而得不到服務(wù)，預(yù)計得不到服務(wù)的顧客將不能獲得排隊的號碼），所以我們可以采用限制長度的循環(huán)隊列進(jìn)行實現(xiàn)。隊列定義如下：任務(wù)2提示typedefstructSqQueue{CustomerType*base;//存儲空間的首地址

intfront;//隊頭位置

intrear;//隊尾位置intsize;//隊列的最大長度}SqQueue;4.5任務(wù)提示然后設(shè)計一個初始化函數(shù)初始化隊列，參考如下：任務(wù)2提示voidInitQueue(SqQueue&q,intsize){q.base=(CustomerType*)malloc(size*sizeof(CustomerType));q.front=q.rear=0;q.size=size;}4.5任務(wù)提示

入隊和出隊時需對隊列的滿或空的狀態(tài)進(jìn)行判斷。實現(xiàn)判斷隊列是否為空的函數(shù)可以如下定義：任務(wù)2提示

判斷隊列是否已滿的函數(shù)如下定義：intIsQueueEmpty(SqQueueq){returnq.front==q.rear;}intIsQueueFull(SqQueueq){return(q.rear+1)%q.size==q.front;}4.5任務(wù)提示顧客數(shù)據(jù)value入隊操作如下：任務(wù)2提示intEnQueue(SqQueue&q,CustomerTypecustomer){if(IsQueueFull(q)){printf("Queueisfull!\n");return-1;}q.base[q.rear]=customer;q.rear=(q.rear+1)%q.size;//循環(huán)隊列

return0;}4.5任務(wù)提示將一個顧客出隊的操作如下：任務(wù)2提示intDeQueue(SqQueue&q,CustomerType&value){if(IsQueueEmpty(q)){printf("Queueisempty!\n");return-1;}value=q.base[q.front];q.front=(q.front+1)%q.size;//循環(huán)隊列

return0;}4.5任務(wù)提示

檢測隊列長度即是要查詢出隊列中的顧客數(shù)（隊列中元素的個數(shù)）。因為是循環(huán)隊列，當(dāng)q.rear大于等于q.front時，元素個數(shù)為q.rear–q.front；當(dāng)q.rear小于q.front時，元素個數(shù)為q.size–(q.front–q.rear)?？梢栽O(shè)計一個統(tǒng)計顧客數(shù)的函數(shù)如下：任務(wù)2提示intCountCustomer(SqQueueq){intcount=0;if(q.rear>=q.front)//計算隊列中元素數(shù)量（顧客數(shù)）

count=q.rear–q.front;else

count=q.size–(q.front–q.rear);returncount;｝4.5任務(wù)提示

預(yù)計等待時間是顧客拿到排號時估計還要等待多長時間即可獲得服務(wù)，銀行通過這個參數(shù)也將知道把所有顧客的業(yè)務(wù)辦理完大概還要多長時間。為了算出這個時間，需要遍歷所有已經(jīng)拿到排號并且在隊列中等待的顧客，即對所有顧客辦理業(yè)務(wù)所需要的時間求和。以下設(shè)計一個函數(shù)求隊列中所有顧客辦理完業(yè)務(wù)需要的總時間。任務(wù)2提示4.5任務(wù)提示任務(wù)2提示intCalculateTotalTime(SqQueueq){inttotalTime=0;if(IsQueueEmpty(q)) return0;