數(shù)據(jù)結(jié)構(gòu) 隊列

1、5.1 何謂隊列隊列數(shù)據(jù)結(jié)構(gòu)規(guī)定：在有序列表中數(shù)據(jù)的輸出、輸入是分別由不同端進(jìn)行處理，輸出端稱為前端(front)，輸入端稱為后端(rear)，這樣會使得先存入的數(shù)據(jù)會先被取出，也就是具有先進(jìn)先出FIFO的特性。1隊列的應(yīng)用也很多，下面列出幾個較常見的：1.圖形的廣度優(yōu)先搜索法。2.優(yōu)先隊列，此種隊列在取出元素時是根據(jù)所存元素的某項特性值或優(yōu)先權(quán)而取出具最小或最大數(shù)值的元素。3.操作系統(tǒng)中的工作調(diào)度，若工作的優(yōu)先權(quán)相同，則采用先到先做的原則。4.用于“spooling” (假脫機，信息暫存,當(dāng)信息需進(jìn)一步處理時，對其進(jìn)行暫時存貯)，先將輸出數(shù)據(jù)寫在磁盤上，再由打印機把先存入者先處理的順序?qū)?shù)據(jù)

2、輸出。隊列和堆棧一樣也可使用兩種結(jié)構(gòu)：數(shù)組結(jié)構(gòu)和鏈表結(jié)構(gòu)。 2抽象數(shù)據(jù)類型Queue元素：無限制，由應(yīng)用決定結(jié)構(gòu)：保持元素先進(jìn)先出的特性。操作：(1)void Init(Queue &Q)/初始化生成一個空棧(2)void Addqueue(Element e,Queue &Q)/入隊操作(3)void Delqueue(Elment &e,Queue &Q)/出隊操作(4)Element Top(Queue Q)/讀隊首元素值(5)bool Empty(Queue Q)/判隊列空操作(6)bool Full(Queue Q)/判隊列滿操作35.2用數(shù)組仿真隊列 隊列本身是有序列表，若使用數(shù)組

3、的結(jié)構(gòu)來存儲隊列的結(jié)構(gòu)，則隊列結(jié)構(gòu)數(shù)組的聲明如下:struct queueint queueMaxSize；int front；int rear；其中MaxSize是該隊列的最大容量。因為隊列的輸出、輸入分別從前后端來處理，因此需要兩個變量front和rear分別記錄隊列前后端的索引值，front會隨著數(shù)據(jù)輸出而變動，而rear則是隨著數(shù)據(jù)輸入而改變。 4初始化隊列void init(queue &q)q.front=-1;q.rear=-1; 5判斷隊列空empty函數(shù)bool empty(queue q)return(q.front=q.rear);6判斷隊列滿full函數(shù)bool ful

4、l(queue q)return (q.rear =maxsize-1); 7當(dāng)我們將數(shù)據(jù)存入隊列時稱為“addqueue” ，addqueue的處理主要有兩個步驟：(1)將隊尾指針往前移：rear+1； (2)若尾指針rear小于等于隊列的最大索引值MaxSize-1，則將數(shù)據(jù)存入rear所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。8入隊addqueue函數(shù)void addqueue(queue &q,char x)q.rear +;q.data q.rear =x; 9從隊列中取出數(shù)據(jù)項稱為“delqueue” ，delqueue的操作可分為4個步驟：(1)檢查隊列中是否有數(shù)據(jù)存在。 (2)若頭指

5、針front等于尾指針rear，則表示隊列中無數(shù)據(jù)。(3)若頭指針front不等于尾指針rear，則將隊列頭指針往前移front+1。(4)取出隊頭指針?biāo)傅臄?shù)組元素內(nèi)容。 10出隊delqueue函數(shù)void delqueue(queue &q,char &x)q.front +;x=q.data q.front ; 11顯示隊列數(shù)據(jù)print函數(shù)void print(queue q)int i;for(i=q.front +1;i=q.rear ;i+)coutsetw(4)q.data i;coutdata =x;New-next =NULL;if(q.rear =NULL)q.fron

6、t =q.rear =New;elseq.rear -next =New;q.rear =New; 17數(shù)據(jù)輸出是從隊列的前端front處理，其步驟如下：步驟1：先保留對頭指針front所指的位置步驟2：將頭指針front指向下一個節(jié)點步驟3：取出之前保留頭指針?biāo)傅墓?jié)點內(nèi)容步驟4：釋放原隊列前端所指的節(jié)點內(nèi)容 18出隊delqueue函數(shù)void delqueue(queue &q,char &x)node *p;p=q.front ;q.front =q.front -next ;x=p-data ;delete p; 19顯示隊列print函數(shù)void print(queue q)nod

7、e *p;p=q.front ;while(p!=NULL)coutsetw(4)data ;p=p-next ;coutendl; 205.4環(huán)狀隊列 我們在5.2節(jié)中提到，當(dāng)隊尾指針rear等于MaxSize-1時，不論隊列是否有空間，都無法再將數(shù)據(jù)存于隊列中。如果要將數(shù)據(jù)往隊列前端移動以挪出空間，需要花費很多時間。為解決這樣的問題，我們使用環(huán)狀隊列，控制隊列前尾指針front、rear來充分運用隊列中的空間。環(huán)狀隊列的概念如下圖：圖略（P126） 21當(dāng)插入數(shù)據(jù)時，尾指針rear會往箭頭方向前進(jìn)，而輸出數(shù)據(jù)時，頭指針front也會往箭頭方向前進(jìn)，可看出隊列空間的利用是按照逆時針方向循環(huán)，

8、直到rear往前移動到等于front時，表示隊列己滿,無法輸入數(shù)據(jù)。從上圖看來，雖然環(huán)狀隊列看似一個封閉的圓環(huán)，但事實上環(huán)狀隊列仍然是一個線性數(shù)組，和一般隊列比較起來，主要是前后端使用技巧的差異。在此需特別注意的是，環(huán)狀隊列中的頭指針?biāo)傅臄?shù)組位置并沒有內(nèi)容值存在，輸出的值為front的下一個元素，故環(huán)狀隊列實際上所能使用的空間為MaxSize-1。 22當(dāng)尾指針rear等于MaxSize-1時需回到隊列的最前端，故當(dāng)輸入數(shù)據(jù)時，rear所指的數(shù)組元素索引值采用下列的計算方法：(rear+1)mod MaxSize若尾指針rear不斷前進(jìn)直到等于頭指針front時，那么表示隊列己滿，但如果隊列

9、為空時rear也等于front，為區(qū)分這兩種狀況，必須使用不同的條件來加以判斷。當(dāng)隊列為滿：(rear+1)mod MaxSize=front當(dāng)隊列空：front=rear 這兩個條件所代表的意義是不一樣的。 23初始化環(huán)狀隊列void init(queue &q)q.front=0;q.rear=0; 24判斷環(huán)狀隊列空empty函數(shù)bool empty(queue q)return(q.front=q.rear);25判斷環(huán)狀隊列滿full函數(shù)bool full(queue q)return (q.rear+1)%maxsize=q.front ); 26當(dāng)我們將數(shù)據(jù)存入隊列時稱為“add

10、queue” ，addqueue的處理主要有兩個步驟：(1)將隊尾指針往前移：rear+1； (2)若尾指針rear小于等于隊列的最大索引值MaxSize-1，則將數(shù)據(jù)存入rear所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。27環(huán)狀隊列入隊addqueue函數(shù)void addqueue(queue &q,char x)q.rear=(q.rear +1)%maxsize;q.data q.rear =x; 28從隊列中取出數(shù)據(jù)項稱為“delqueue” ，delqueue的操作可分為4個步驟：(1)檢查隊列中是否有數(shù)據(jù)存在。 (2)若頭指針front等于尾指針rear，則表示隊列中無數(shù)據(jù)。(3)若頭指

11、針front不等于尾指針rear，則將隊列頭指針往前移front+1。(4)取出隊頭指針?biāo)傅臄?shù)組元素內(nèi)容。 29環(huán)狀隊列出對隊delqueue函數(shù)void delqueue(queue &q,char &x)q.front=(q.front +1)%maxsize;x=q.data q.front ;30顯示環(huán)狀隊列數(shù)據(jù)print函數(shù)void print(queue q)int i;if (q.front q.rear )for(i=q.front +1;i=q.rear ;i+)coutsetw(4)q.data i;elsefor(i=q.front+1 ;imaxsize;i+)cou

12、tsetw(4)q.data i;for(i=0;i=q.rear ;i+)coutsetw(4)q.data i;coutendl;3155 雙向隊列 前面所提到的隊列為單向隊列，即從隊列后端進(jìn)行輸入、前端進(jìn)行輸出。顧名思義，雙向隊列即可從前后端進(jìn)行隊列數(shù)據(jù)的輸出及輸入，如下圖所示：這樣的結(jié)構(gòu)最常用于計算機的CPU調(diào)度。所謂“CPU調(diào)度”是在多人使用一個CPU的情況下，由于CPU在同一時間只能執(zhí)行一項工作，故將每個人欲處理的工作先存于隊列中，待CPU閑置時再從隊列中取出一項待執(zhí)行的工作進(jìn)行處理。而在雙向隊列兩端均可輸出、輸入的結(jié)構(gòu)下，正好符合在CPU調(diào)度處理上的不同請求。雙向隊列的設(shè)計有很多

13、種，在此我們根據(jù)輸出、輸入方向的限制，將其分為兩種：1.輸入限制性雙向隊列 2.輸出限制性雙向隊列 325.5.1 輸入限制性雙向隊列 “輸入限制性雙向隊列”是限制只能在隊列的一端(后端)進(jìn)行輸入，而數(shù)據(jù)的輸出則可在隊列的兩端(前后端)操作。程序?qū)嵗阂阎魂犃?，欲使用“輸入限制性雙向隊列”方式進(jìn)行數(shù)據(jù)輸出。程序源代碼： 33#include #include #define MaxSize 10int queue MaxSize ;int front = -1;int rear = -1;void addqueue (int value)rear= (rear+1) % MaxSize; i

14、f (front=rear)coutThe queue is full! !; elsequeuerear = value;int rear_delqueue () int temp;if (front = rear)return -1;temp=queuerear;rear-;if (rear0 & front!=-1)rear=MaxSize-1;return temp;34int front_delqueue ()if (front = rear)return -1; front+ ; if (front = MaxSize)front =0; return queue front ;v

15、oid main ( ) int select; int output_queue 5 ;int input_queue5=5,4,3,2,1;int temp,Position=0,i;for (i=0;i5;i+)addqueue (input_queuei);coutThe original queue order :;for (i=0;i5;i+)cout input_queuei; coutendl;35 while (front != rear) cout(1) From Front-endendl;cout(2) From Rear-end endl;cout;cinselect

16、;switch (select)case 1:temp=front_delqueue ( );output_queue Position+ =temp;break;case 2:temp=rear_delqueue() ;output_queuePosition+ =temp;break; coutendlThe output order:; for (i=0;i5;i+)coutoutput_queuei; coutendl;365.5.2輸出限制性雙向隊列 “輸出限制性雙向隊列”恰好與“輸入限制性雙向隊列”相反，它所限制的是只能在隊列的一端(前端)進(jìn)行輸出，而數(shù)據(jù)的輸入則是可以在隊列的兩端

17、（前后端）操作。所以也會有兩種情況：程序?qū)嵗阂阎魂犃?，欲使用“輸出限制性雙向隊列”方式進(jìn)行數(shù)據(jù)輸出。程序源代碼： 37#include #include struct queue_node int data; struct queue_node *next;typedef struct queue_node queue_list;typedef queue_list *link; link front = NULL; link rear = NULL; void rear_addqueue (int value) link newnode; newnode = (link) malloc

18、(sizeof(queue_list); newnode-data = value; newnode-next= NULL; if (rear=NULL)front=newnode; elserear-next =newnode; rear=newnode; 38void front_addqueue (int value) link newnode; newnode = (link) malloc(sizeof(queue_list); newnode-data = value ; newnode-next= NULL; if (front=NULL) /newnode-next=NULL;rear=newnode; elsenewnode-next=front; front=new