1、第3章 棧與隊(duì)列本章導(dǎo)讀 棧和隊(duì)列是兩種特殊的線性結(jié)構(gòu)，是線性表特例。一般，在線性表上的插入、刪除運(yùn)算等操作不受限制，而棧和隊(duì)列上的插入、刪除操作會受某種限制，對它們來說，插入和刪除運(yùn)算均是對首尾兩個元素進(jìn)行的。本章主要介紹棧和隊(duì)列的邏輯特征及其在計(jì)算機(jī)中的存儲表示、棧和隊(duì)列的基本運(yùn)算的算法描述以及棧和隊(duì)列的應(yīng)用。教學(xué)目標(biāo)通過本章學(xué)習(xí)，要求掌握以下內(nèi)容：1棧的基本概念和棧的基本運(yùn)算。2棧的應(yīng)用。3隊(duì)列的基本概念和隊(duì)列的基本運(yùn)算。4隊(duì)列的應(yīng)用。3.1 棧 3.1.1 棧的定義 棧（Stack）是限定僅在表的一端進(jìn)行插入或刪除操作的線性表。在表中允許進(jìn)行插入或刪除操作的一端稱為棧項(xiàng)（Top），而另

2、一端稱為棧底（Bottom）。不含元素的棧稱為空棧。棧的插入和刪除操作分別稱為進(jìn)棧和出棧。進(jìn)棧是將一個數(shù)據(jù)元素存放棧頂，出棧是將棧頂元素取出。若給定棧S=（a1，a2，an），如圖3-1所示的棧中，a1是棧底元素，an是棧頂元素。由于只允許在棧頂進(jìn)行插入和刪除，所以棧的操作是按“后進(jìn)先出”的原則進(jìn)行的。因此棧又稱為后進(jìn)先出表，即LIFO（Last In First Out）線性表。 圖3-1線結(jié)構(gòu)示意圖在日常生活中，有許多類似棧的例子，如刷洗盤子時，把洗凈的盤子一個接一個地向上放（相當(dāng)于進(jìn)棧），取盤子時，則從上面一個接一個地向下拿（相當(dāng)于出棧）。 棧的基本運(yùn)算有五種：1初始化棧：將棧置為空棧，

3、不含任何元素，只建立起棧頂指針。2進(jìn)棧：向棧頂插入一個新的元素。3出棧：刪除棧頂元素。 4判棧空：判斷一個棧是否為空棧。3.1.2 棧的順序存儲及其基本操作的實(shí)現(xiàn) 棧的順序存儲結(jié)構(gòu)，簡稱順序棧。它是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。與順序表的數(shù)據(jù)類型描述類似，棧的C語言描述如下：#define MAX 50 /*定義MAX為棧的最大容量，例如設(shè)為10*/int sMAX; /*定義數(shù)組s，用來存儲棧的元素，以整數(shù)為例*/int top; /*定義棧頂指針為top*/在這個描述中，假設(shè)棧中數(shù)據(jù)元素的類型是整型，數(shù)組s存放棧中數(shù)據(jù)元素，數(shù)組最大容量為MAX，棧頂指針為top

4、。 由于棧頂?shù)奈恢媒?jīng)常變動，所以要設(shè)一個棧頂指針top。棧頂指針top指向下一次進(jìn)棧的數(shù)據(jù)元素存放位置。當(dāng)棧中沒有數(shù)據(jù)元素時，棧是空棧，這時top=0。當(dāng)棧中放滿元素時，top=MAX，表示棧滿。若再有數(shù)據(jù)元素進(jìn)棧，棧將溢出，稱為“上溢（overflow）。這是一個錯誤狀態(tài)。反之，當(dāng)top=0時，再要進(jìn)行出棧操作時，則發(fā)生“下溢“（underflow）。在應(yīng)用中通常作為控制程序轉(zhuǎn)移的條件。下面以一個例子來說明棧的操作。 設(shè)有一棧s=（a，b，c，d，e），則MAX為5，它的順序存儲結(jié)構(gòu)如圖3-2所示。其中圖3-2（a）是空棧狀況；圖3-2（b）是進(jìn)棧一個元素“a”之后的棧狀況；圖3-2（c）是

5、在圖3-2（b）基礎(chǔ)上連續(xù)將元素“b、c、d、e”進(jìn)棧之后的棧狀況，此時是棧滿狀況，不允許有元素進(jìn)棧；圖3-2（d）是在圖3-2（c）基礎(chǔ)上出棧一個元素后的棧狀況。由此可見，非空棧中的棧頂指針top始終指向棧頂元素的下一個位置。圖3-2 棧的順序存儲結(jié)構(gòu) 順序棧的基本運(yùn)算有初始化棧、進(jìn)棧、出棧和判棧空。下面分別介紹棧的幾種基本運(yùn)算。 1初始化棧 初始化棧算法描述如下：void initstack（int top） /*建立一個空棧s*/ top=0; /*設(shè)置棧頂指針top為0，表示棧空*/ 2進(jìn)棧 進(jìn)棧是在棧頂插入新的元素。由于進(jìn)棧時可能會遇到棧滿，導(dǎo)致操作不能進(jìn)行，此時進(jìn)行溢出處理，返回函

6、數(shù)值0;如果棧未滿，則棧頂指針加1，插入新元素，返回函數(shù)值1。進(jìn)棧算法描述如下： #define MAX 10int top; /*定義棧頂指針為top*/ int push（int s，int x）/*x為要插入的新元素*/if（top=MAX） printf（stack overflow）; /*棧滿信息*/ return( 0); else s top=x; /*數(shù)據(jù)入棧*/top=top+1; /*當(dāng)棧不滿時，棧頂加1*/ printf（ok）; return (1); main（） /*主程序*/int aMAX=1，2，3，4，5;int x=56,i;top=5;if(push（

7、a,x）)for(i=0;itop;i+)printf(“%3d”,ai); /*函數(shù)調(diào)用*/ 例如棧為1，2，3，4，5，想讓元素“56”進(jìn)棧，調(diào)用進(jìn)棧函數(shù)后，棧的內(nèi)容成為1，2，3，4，5，56。 3出棧出棧是從棧頂刪除元素。由于出棧時可能會遇到棧空，此時進(jìn)行下溢處理，返回函數(shù)值0;如果棧不空，則使棧頂指針減1，然后將棧頂元素取出，返回函數(shù)值1。出棧算法描述如下:#define MAX 10int top;int pop（int s,int *y） if（top=0） /*如果棧空*/ printf（stack is empty）; /*輸出棧空信息*/ return 0; else /*

8、如果棧不空*/ top=top-1; /*棧頂指針減1*/*y=stop; printf（ok）; return 1; main（） /*主程序*/ int aMAX=1，2，3，4，5; int y;top=5;if(pop(a,&y）)printf(“%d”,y); /*輸出出棧元素*/ 例如棧內(nèi)容為1，2，3，4，5，調(diào)用出棧函數(shù)后，棧的內(nèi)容成為1，2，3，4。 4判棧空 如果棧空，則返回值1，如果棧不空，則返回值0。判棧空算法描述如下: void empty（int s,int top） if（top=0） /*如果棧空*/ return（1）; /*返回值1*/ else /

9、*如果棧不空*/ return（0）; /*返回值0*/ 對于進(jìn)棧算法中的“上溢”應(yīng)設(shè)法避免。避免出現(xiàn)“上溢”的惟一方法是將棧的容量加到足夠大。若一個程序使用多個棧時，往往事先難以估講每個棧所需容量，在實(shí)際應(yīng)用中一個棧發(fā)生“上溢”其他棧可能還留有很多空間，可以用移動數(shù)據(jù)元素位置的方法加以調(diào)整。以達(dá)到多個棧共享存儲空間的目的。現(xiàn)在，我們以兩個棧為例討論共享存儲空間（一維數(shù)組sMAX，MAX是預(yù)先定義的容量）的方法。可以把兩個棧的棧底分別設(shè)在給定存儲空間的兩端，然后各自向中間伸展如圖3-3所示，僅當(dāng)兩個棧的棧頂相遇時才可能發(fā)生上溢，這樣兩個棧之間可以做到互補(bǔ)余缺，使得某個棧實(shí)際可利用的最大空間大于

10、MAX/2。設(shè)第一個棧自頂向下伸展，第二個棧自底向上伸展，t1指向第一個棧的棧頂元素的下一個位置，而t2則指向第二個棧的棧頂元素的上一個位置，兩個棧的初態(tài)分別為t1=0，t2=MAX-1，上溢條件是t21=t1。雙棧的C語言描述如下：#define MAX 50 /*定義MAX為棧的最大容量，例如設(shè)為10*/int sMAX; /*定義數(shù)組s，用來存儲棧的元素，以整數(shù)為例*/int t1,t2; /*定義兩個棧頂指針分別為t1和t2*/下面介紹雙棧的進(jìn)棧、出棧的操作。進(jìn)棧向第i個棧插入元素x，若插入成功函數(shù)返回值為1，否則函數(shù)返回值為0，算法如下：#define MAX 50int sMAX;

11、int t1,t2;int pushd ( int s,int i, int x)/*元素x進(jìn)第i個棧（i=1,2）*/ if (i2) return(0); if (t2+1=t1) return(0); if(i=1) st1=x; t1+; else st2=x; t2-; return(1); main()int i,j,x,p; for(i=0;i40;j-)/*第二棧輸入數(shù)據(jù)*/ scanf(“%d”,&sj); t2=40; scanf(“%d,%d”,&p,&x); /*輸入往第p個棧插入數(shù)據(jù)x*/ if (pushd ( s,p,x) for (i=0

12、;it2;j-) printf(“%5d”,sj); (2)出棧第i個棧出棧算法。若第i（i=1,2）個棧為空，則函數(shù)返回值為0，否則函數(shù)返回值為1。#define MAX 50int sMAX;int t1,t2;int popd ( int s, int i)/*第i個棧退棧*/ int y; if (i2) return(0); if (i=1) if(t1=0) return(0); else t1-; y=st1;printf(“%d”,y);else if(t2=MAX-1) return(0); else t2+;y=st2;printf(“%d”,y); return(1);m

13、ain()int i,j,x; for(i=0;i40;j-)/*第二棧輸入數(shù)據(jù)*/ scanf(“%d”,&sj); t2=40; scanf(“%d”,&x); /*輸入第x個棧要進(jìn)行出棧操作*/ if (popd ( s,x) for (i=0;it2;j-) printf(“%5d”,sj); 3.1.3 棧的鏈?zhǔn)酱鎯捌浠静僮鞯膶?shí)現(xiàn) 當(dāng)棧的最大容量事先不能估計(jì)時，也可采用鏈表作存儲結(jié)構(gòu)，簡稱為鏈棧，其結(jié)點(diǎn)類型定義為： typedef struct node int data; /*這里以整型為例*/struct node*next; /*指針類型，存放下一個結(jié)點(diǎn)的地

14、址*/ NODE; NODE *top; /*鏈棧表頭指針，即棧頂指針*/ 設(shè)top是指向棧頂結(jié)點(diǎn)的指針，其初值為空，說明在初始狀態(tài)下，棧中沒有任何結(jié)點(diǎn)。如圖3-4（a）所示，當(dāng)把一個數(shù)據(jù)元素x入棧時，先向系統(tǒng)申請一個結(jié)點(diǎn)p，置其數(shù)據(jù)域值為x，把top結(jié)點(diǎn)作為p結(jié)點(diǎn)的直接后繼，top改指到p結(jié)點(diǎn)。如圖3-4（b）所示。出棧時，先取出棧頂結(jié)點(diǎn)中的數(shù)據(jù)，然后把該結(jié)點(diǎn)鏈域的值賦給棧頂指針top，釋放該結(jié)點(diǎn)。如圖3-4（c）所示。 圖3-4棧的插入和刪除運(yùn)算鏈棧的主要運(yùn)算有進(jìn)棧和出棧。 1進(jìn)棧當(dāng)向鏈棧插入一個新元素時，首先要向系統(tǒng)申請一個結(jié)點(diǎn)的存儲空間，將新元素的值寫入新結(jié)點(diǎn)的數(shù)據(jù)域中，然后修改棧頂指

15、針。設(shè)要插入的新元素為x，以整型為例。進(jìn)棧的算法描述如下：#include #include typedef struct node int data; /*這里以整型數(shù)據(jù)為例*/struct node*next; /*指針類型，存放下一個結(jié)點(diǎn)地址*/NODE; NODE *crea_linkstack（） /*建立鏈棧*/ NODE*top，*g; /*定義棧頂指針*/ char j; int a; top=NULL; j=getchar（）; while（j!=?） /*判斷生成鏈棧結(jié)束標(biāo)志*/ scanf（%d，&a）; g=（NODE*）malloc（sizeof（NODE）;

16、 g-data=a; g-next=top; top=g; j=getchar（）; return（top）; /*返回棧頂指針*/NODE * pushstack（NODE*top，int x） NODE*p; /*定義結(jié)點(diǎn)p*/p=（NODE*）malloc（sizeof（NODE）; p-data=x; /*將要插入的數(shù)據(jù)x存儲到結(jié)點(diǎn)p的數(shù)據(jù)域中*/ p-next=top; /*將p結(jié)點(diǎn)的指針修改為原top的指針*/ top=p; /*將top修改為p*/return(top); main（） /*主程序*/ int y=34; /*將入棧的元素*/NODE*top,*p; top=cr

17、ea_linkstack（）; /*建立鏈棧*/top=pushstack（top，y）; /*入棧*/p=top; /*輸出整個鏈棧，print為第二章編寫的輸出鏈表函數(shù)*/while (p!=NULL)printf(“%5d”,.p-data); p=p-next; 例如調(diào)用建立鏈棧函數(shù)后所建立的鏈棧數(shù)據(jù)元素為1，2，3，4，5，6，將元素34入棧，調(diào)用入棧函數(shù)后顯示為34，6，5，4，3，2，1。 2出棧當(dāng)出棧時，先取出棧頂元素的值，再修改棧頂指針，釋放原棧頂結(jié)點(diǎn)。出棧的算法描述如下：#includetypedef struct node int data; struct node*ne

18、xt;NODE; NODE*popstack（NODE*top，int*q）NODE*p; /*定義q結(jié)點(diǎn)*/ if（top!=NULL） /*如果棧不空*/ p=top; /*p指向棧頂結(jié)點(diǎn)*/ *q=top-data;/*將要讀出的數(shù)據(jù)放入*q中*/ top=top-next; /*修改top指針*/ free（p）; return（top）; /*返回棧頂指針*/3棧和隊(duì)列main（） /*主程序*/ int b; NODE*top; top=crea_linkstack（）;/ 建立鏈棧的函數(shù)見上面*/top=popstack（top，&b）;printf(“%5d”,b);

19、例如已知鏈棧數(shù)據(jù)元素為1，2，3，4，5，6，7，調(diào)用出棧函數(shù)后的顯示結(jié)果為7。3.1.4 棧的應(yīng)用舉例 棧是計(jì)算機(jī)軟件中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。比如，在編譯系統(tǒng)中的表達(dá)式求值，程序遞歸的實(shí)現(xiàn)，子程序的調(diào)用和返回地址的處理等。下面介紹棧的幾個應(yīng)用實(shí)例。 1算術(shù)表達(dá)式的計(jì)算 表達(dá)式求值是編譯系統(tǒng)中的一個基本問題，目的是把人們平時書寫的算術(shù)表達(dá)式變成計(jì)算機(jī)能夠理解并能正確求值的表達(dá)方法。算術(shù)表達(dá)式中包含算術(shù)運(yùn)算符和算術(shù)量，在各運(yùn)算符之間存在著優(yōu)先級，運(yùn)算時必須按優(yōu)先級順序進(jìn)行運(yùn)算，先運(yùn)算高級別的，后運(yùn)算低級別的，而不能簡單地從左到右進(jìn)行運(yùn)算。因此，進(jìn)行表達(dá)式運(yùn)算時，必須設(shè)置兩個棧，一個棧用于存放

20、運(yùn)算符，另一個棧用于存放操作數(shù)。在表達(dá)式運(yùn)算過程中，編譯程序從左到右進(jìn)行掃描，遇到操作數(shù)，就把操作數(shù)放入操作數(shù)棧，遇到運(yùn)算符時，要把該運(yùn)算符與運(yùn)算符棧的棧頂比較。如果該運(yùn)算符優(yōu)先級高于棧頂運(yùn)算符的優(yōu)先級，就把該運(yùn)算符進(jìn)棧，否則退棧。退棧后，在操作數(shù)棧中退出兩個元素，其中先退出的元素在運(yùn)算符右，后退出的元素在運(yùn)算符左，然后用運(yùn)算符棧中退出的棧頂元素（運(yùn)算符）進(jìn)行運(yùn)算，運(yùn)算的結(jié)果存入操作數(shù)棧中。反復(fù)進(jìn)行上述操作，直到掃描結(jié)束。此時，運(yùn)算符棧為空，操作數(shù)棧只有一個元素，即為最終的運(yùn)算結(jié)果。 例3.1 棧求表達(dá)式6-8/4+3*5的值。棧的變化見表3-1。步驟操作數(shù)棧運(yùn)算符棧說明開始123456789

21、101112131415161718666 86 8 6 8 46 6 2444 34 34 3 544 151919- /- /-+ *+ *+開始時兩個棧為空掃描到“6”，進(jìn)入操作數(shù)棧掃描到“-”，進(jìn)入運(yùn)算符棧掃描到“8”，進(jìn)入操作數(shù)棧掃描到“/”，進(jìn)入運(yùn)算符棧掃描到“4”，進(jìn)入操作數(shù)棧掃描到“+”，“/”“8”、“4”退棧 計(jì)算8/4=2進(jìn)操作數(shù)棧掃描到“+”，“-”“6”、“2”退棧6-2=4進(jìn)操作數(shù)棧掃描到“+”，進(jìn)入運(yùn)算符棧掃描到“3”，進(jìn)入操作數(shù)棧掃描到“*”，進(jìn)入運(yùn)算符棧掃描到“5”，進(jìn)入操作數(shù)棧掃描完，“*”“3”、“5”退棧3*5=15進(jìn)操作數(shù)棧“+”“4”、“15”退棧4

22、+15=19進(jìn)操作數(shù)棧表達(dá)式的值為19表3-1 用棧求表達(dá)式的值 2函數(shù)遞歸的實(shí)現(xiàn) 遞歸是程序設(shè)計(jì)中常用的方法之一。棧的一個重要的應(yīng)用是可以用來實(shí)現(xiàn)遞歸函數(shù)（或遞歸過程）。 例例3.2 通常用來說明遞歸的最簡單的例子是階乘的定義，它可以表示成： 1 （n=0,1） n1 n(n-1)! n!= 由定義可知，為了定義n的階乘，必須首先定義(n-1)的階乘，為了定義(n-1)的階乘，又必須定義(n-2)的階乘這種用自身的簡單情況來定義自己的方式，稱為“遞歸定義”。一個遞歸定義必須一步比一步簡單，最后是有終結(jié)的，決不能無限循環(huán)下去。在n的階乘的定義中，當(dāng)n為0或1時定義為1，它不再用遞歸來定義。根據(jù)

23、階乘的定義，我們編寫的C語言程序如下： int fac(int n)/*計(jì)算n! */ if(n=0|n=1) return(1); else return(n*fac(n-1);main()int n,y; scanf(“%d”,&n); y=fac(n); printf(“%d!=%d”,n,y); 函數(shù)據(jù)直接或間接調(diào)用自身稱為函數(shù)的遞歸調(diào)用。包含遞歸調(diào)用的函數(shù)稱為遞歸函數(shù)。像函數(shù)fac(n)中含直接調(diào)用函數(shù)fac，這就稱為直接遞歸調(diào)用。若函數(shù)a中調(diào)用函數(shù)b，而函數(shù)b中又調(diào)用了函數(shù)a，這就稱為間接遞歸調(diào)用。 實(shí)現(xiàn)遞歸調(diào)用的關(guān)鍵是建立一個棧。這個棧是由系統(tǒng)提供的運(yùn)行工作棧。計(jì)算機(jī)在執(zhí)

24、行遞歸算法時，是通過棧來實(shí)現(xiàn)的。在一層層遞歸調(diào)用時，系統(tǒng)自動將其返回地址和處在每一調(diào)用層的變量數(shù)據(jù)一一記下并進(jìn)棧。返回時，它們一一出棧并且被采用。圖3-5展示了遞歸調(diào)用中的執(zhí)行情況。從圖3-5可以看到fac函數(shù)共被調(diào)用4次，即fac(4)、fac(3)、 fac(2) 、fac(1)。其中fac(4)是在main函數(shù)據(jù)中調(diào)用的，其余3次是在fac函數(shù)中調(diào)用的。在某一層遞歸調(diào)用時，并未立即得到結(jié)果，而是進(jìn)一步向深度遞歸調(diào)用，直到最內(nèi)層函數(shù)執(zhí)行n=1時，fac(n)才有結(jié)果。然后在一一返回時，不斷得到中間結(jié)果，直到回到主程序得到n!的最終結(jié)果為止。圖3-5遞歸調(diào)用示意圖 實(shí)際上，遞歸是把一個不能或

25、不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決，再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決（此時分解到遞歸出口）。當(dāng)然，被分解的“小問題”和“大問題”必須具有相同的特征屬性。 雖然遞歸算法簡明精練，但運(yùn)行效率較低，時空開銷較大，并且某些高級語言沒有提代遞歸調(diào)用的語句及功能。因此，在實(shí)際應(yīng)用中往往會使用非遞歸方法。為了提高程序設(shè)計(jì)的能力，有必要進(jìn)行由遞歸方法到非遞歸方法的基本訓(xùn)練。通過前面對遞歸算法執(zhí)行的分析，我們已經(jīng)知道，系統(tǒng)內(nèi)部是借助于棧來實(shí)現(xiàn)遞歸的。因此，在設(shè)計(jì)相應(yīng)的非遞歸算法時也需要人為地設(shè)置一個棧來實(shí)現(xiàn)。具體如何實(shí)現(xiàn)將在后

26、面的有關(guān)章節(jié)中詳細(xì)介紹 3.2 隊(duì)列 3.2.1 隊(duì)列的定義 隊(duì)列（queue）是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。表中允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)首（front）。 假設(shè)隊(duì)列為Q=（a1，a2，a3，an），那么a1就是隊(duì)首元素，an則是隊(duì)尾元素。隊(duì)列中的元素是按照a1，a2，a3，an的順序進(jìn)入的，出隊(duì)列也只能按照這個次序依次退出，圖3-6是隊(duì)列的示意圖，因此，隊(duì)列又稱為先進(jìn)先出表（First In First Out，簡稱FIFO）。如果隊(duì)列中沒有任何元素，則稱為空隊(duì)列，否則稱為非空隊(duì)列。 圖3-6隊(duì)列的示意圖 在日常生活中，有許多隊(duì)列

27、的例子，如顧客排隊(duì)購物，排在隊(duì)伍前面的顧客先買，先離隊(duì)。排在隊(duì)伍后面的顧客后買，后離隊(duì)。隊(duì)列的基本運(yùn)算有五種： 1初始化隊(duì)列：將一個隊(duì)列設(shè)置為空隊(duì)列。 2入隊(duì)列：在隊(duì)尾插入一個新的元素，也稱進(jìn)隊(duì)或插入。 3出隊(duì)列：在隊(duì)首刪除一個元素，也稱退隊(duì)或刪除。 4取隊(duì)首元素：得到隊(duì)首元素的值。 5判隊(duì)空：判斷隊(duì)列是否為空隊(duì)列。 在日常生活中，有許多隊(duì)列的例子，如顧客排隊(duì)購物，排在隊(duì)伍前面的顧客先買，先離隊(duì)。排在隊(duì)伍后面的顧客后買，后離隊(duì)。隊(duì)列的基本運(yùn)算有五種： 1初始化隊(duì)列：將一個隊(duì)列設(shè)置為空隊(duì)列。 2入隊(duì)列：在隊(duì)尾插入一個新的元素，也稱進(jìn)隊(duì)或插入。 3出隊(duì)列：在隊(duì)首刪除一個元素，也稱退隊(duì)或刪除。 4取

28、隊(duì)首元素：得到隊(duì)首元素的值。 5判隊(duì)空：判斷隊(duì)列是否為空隊(duì)列。 3.2.2 隊(duì)列的順序存儲及其基本操作的實(shí)現(xiàn) 隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列（sequential queue）。順序隊(duì)列與順序表一樣，用一個一維數(shù)組來存放數(shù)據(jù)元素。在內(nèi)存中，用一組連續(xù)的存儲單元順序存放隊(duì)列中各元素。隊(duì)列的C語言描述如下： #define MAX 10 /*定義MAX為隊(duì)列最大容量，例如設(shè)為10*/ int qMAX; /*定義數(shù)組q，用來存放隊(duì)列的元素，以整數(shù)為例*/ int front=-1，rear=-1; /*定義隊(duì)首和隊(duì)尾指針，并賦初值*/ 在這個描述中，用一維數(shù)組qMAX表示隊(duì)列，其中MAX表示隊(duì)列允

29、許的最大容量，用一個指針front指示隊(duì)列的首端，用另一個指針rear來指示隊(duì)列的尾端。為方便起見，約定頭指針front總是指向隊(duì)首的前一個位置，尾指針rear指向隊(duì)尾的所在位置。 在隊(duì)列順序存儲結(jié)構(gòu)中如圖3-7所示，隊(duì)首指針和隊(duì)尾指針是數(shù)據(jù)元素的下標(biāo)。在隊(duì)列為空的初始狀態(tài)front=rear=-1。每當(dāng)向隊(duì)列中插入一個元素，尾指針rear向后移動一位，rear=rear+1。當(dāng)rear=MAX-1時，表示隊(duì)滿。每當(dāng)從隊(duì)列中刪除一個元素時，隊(duì)首指針也向后移動一位，front=front+1。經(jīng)過多次進(jìn)隊(duì)和出隊(duì)運(yùn)算，可能出現(xiàn)front=rear的時候，這時隊(duì)列為空。圖3-7表示隊(duì)列出、入隊(duì)操作示

30、例。 下面給出順序隊(duì)列中實(shí)現(xiàn)進(jìn)隊(duì)與出隊(duì)運(yùn)算算法描述。 1進(jìn)隊(duì) 在順序隊(duì)列中，進(jìn)隊(duì)時，數(shù)據(jù)元素是從隊(duì)尾進(jìn)入的，應(yīng)該先改變隊(duì)尾指針，使隊(duì)尾指針指向新元素應(yīng)插入的位置，即隊(duì)尾位置，然后將數(shù)據(jù)插入。由于順序隊(duì)列有上界，因此會發(fā)生隊(duì)滿的情況。在插入時，若發(fā)生隊(duì)滿，應(yīng)返回隊(duì)滿信息。 #define MAX 10int qMAX=1，2，3，4，5;int front=-1，rear=-1;int inqueue（int x）/*插入元素為x*/ if （rear=MAX-1） /*如果隊(duì)滿*/printf(“overflown”);/*打印溢出*/ return(rear); else /*如果隊(duì)不滿*/

31、 q+rear=x； /*隊(duì)尾指針加1*/ return（rear）;/*插入成功返回隊(duì)尾指針*/ main（） /*主程序*/ int i，h=6; /*將h入隊(duì)*/ rear=4; rear=inqueue（h）; for（i=front+1;i=rear;i+） printf（%d，qi）; /*顯示整個隊(duì)的內(nèi)容*/ 例如已知隊(duì)列為1，2，3，4，5，將元素“6”入隊(duì)，調(diào)用入隊(duì)函數(shù)后顯示結(jié)果為1，2，3，4，5，6。 2出隊(duì) 出隊(duì)時將隊(duì)首指針?biāo)冈厝〕觯陉?duì)列結(jié)構(gòu)定義時，隊(duì)首指針指向隊(duì)首元素的前一個位置，因此，應(yīng)先使隊(duì)首指針加1，然后取出隊(duì)首指針?biāo)冈亍．?dāng)隊(duì)列空時，函數(shù)返回隊(duì)空信息

32、0。#define MAX 10int qMAX=1，2，3，4，5;int front=-1，rear=-1;int delqueue（int *y） /*出隊(duì)，出隊(duì)的值放在y中*/if（front=rear） /*如果隊(duì)空*/ printf(“queue empty”)return（front）; else /*如果隊(duì)不空*/ *y=q+front; /*頭指針加1，隊(duì)首結(jié)點(diǎn)送入指針y所指向的變量中*/ return（front）; main（） /*主程序*/ int i，x; rear=4;front=delqueue（&x）; for（i=front+1;i=rear;i+）

33、 printf（%d，qi）; /*顯示整個隊(duì)列*/ 例如已知隊(duì)列為1，2，3，4，5，則調(diào)用出隊(duì)函數(shù)后顯示的結(jié)果為2，3，4，5。 若存儲隊(duì)列的一維數(shù)組中所有位置上都有元素，即尾指針指向一維數(shù)組最后，而頭指針指向一維數(shù)組開頭，則隊(duì)滿。不能再向隊(duì)列中插入元素。 但可能會出現(xiàn)這樣情況，尾指針指向一維數(shù)組最后，但前面有元素已經(jīng)出隊(duì)，這時要插入元素，仍然發(fā)生溢出，而實(shí)際上隊(duì)列并未滿。這種溢出稱為“假溢出”，如圖3-7（C）。克服“假溢出”的方法有兩種：一種是將隊(duì)列中的所有元素均向最前端位置移動，顯然這種方法是很浪費(fèi)時間的；另一種方法是采用循環(huán)隊(duì)列。 循環(huán)隊(duì)列是將存儲隊(duì)列的存儲區(qū)看成是一個首尾相連的環(huán)

34、，即將表示隊(duì)列的數(shù)組元素q0與qMAX-1連接起來，形成一個環(huán)形表。如圖3-8所示。 在循環(huán)隊(duì)列中，容量設(shè)為MAX，隊(duì)首指針為front，隊(duì)尾指針為rear。初始狀態(tài)為front=rear=0。循環(huán)隊(duì)列空標(biāo)志為rear=front，循環(huán)隊(duì)列滿的標(biāo)志為（rear+1）%MAX=front，在循環(huán)隊(duì)列滿時，隊(duì)列中實(shí)際上還有一個空閑單元，以防止空隊(duì)與滿隊(duì)的標(biāo)志發(fā)生沖突。當(dāng)然為，也可以另設(shè)標(biāo)志來區(qū)分隊(duì)滿和隊(duì)空，但運(yùn)算時就要多花費(fèi)一些時間。圖3-9給出了循環(huán)隊(duì)列的進(jìn)隊(duì)、出隊(duì)與指針的關(guān)系。圖3-9 循環(huán)隊(duì)列的進(jìn)隊(duì)、出隊(duì)示意圖 下面給出循環(huán)隊(duì)列中實(shí)現(xiàn)進(jìn)隊(duì)與出隊(duì)運(yùn)算算法的描述。 循環(huán)隊(duì)列存儲在數(shù)組cqMAX中

35、，隊(duì)尾指針為rear，隊(duì)首指針為front。 1進(jìn)隊(duì) 將一個新元素x進(jìn)隊(duì)，從隊(duì)尾插入，首先要判斷是否隊(duì)滿，若隊(duì)滿，則返回隊(duì)滿信息。若隊(duì)不滿，則插入新元素，返回插入成功信息。#define MAX 10 int qMAX=0,1，2，3，4，5; int front=0,rear=0;int incq（int x） if（rear+1）%MAX=front） /*如果隊(duì)滿*/ return（0）; else /*如果隊(duì)不滿*/ rear=（rear+1）%MAX; /*隊(duì)尾指針加1*/ qrear=x; /*將新元素x插入到隊(duì)尾*/ return(1); main（） /*主程序*/ int i

36、，x=23; rear=5; if(incq（x）) for（i=front+1;i=rear;i+） printf（%3d，qi）;/*顯示整個隊(duì)的內(nèi)容*/ 2出隊(duì) 出隊(duì)時要判斷是否隊(duì)空，若隊(duì)為空，則返回隊(duì)空信息0。若隊(duì)不為空，則將隊(duì)首元素存入x中，返回出隊(duì)成功信息1。#define MAX 10 int qMAX=0,1，2，3，4，5; int front=0,rear=0; void delcq（） if（rear=front）/*如果隊(duì)空*/ printf(“empty”); else /*如果隊(duì)不空*/ front=（front+1）%MAX; /*隊(duì)首指針加1*/main（） /

37、*主程序*/ int rear=5; for(i=front+1;i=rear;i+) printf(“%5d”,qi); 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯捌浠静僮鞯膶?shí)現(xiàn) 順序分配的循環(huán)隊(duì)列雖然設(shè)計(jì)的很巧妙，但若有多個隊(duì)列共享內(nèi)存時，比多個棧共享內(nèi)存空間更為復(fù)雜。而鏈?zhǔn)椒峙涞年?duì)列可以很容易地實(shí)現(xiàn)多個隊(duì)列的共享內(nèi)存空間。 當(dāng)隊(duì)列采用鏈表作為存儲結(jié)構(gòu)時，被稱作鏈隊(duì)。其邏輯狀態(tài)如圖3-10所示。 圖3-10 帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列 鏈隊(duì)列結(jié)點(diǎn)類型用C語言描述如下： typedef struct node int data; /*以整型為例*/ struct node*next;NODE; 在鏈隊(duì)列中，有一

38、個頭指針front和一個尾指針rear。與單鏈表類似，另外給鏈隊(duì)列增加一個附加表頭結(jié)點(diǎn)。隊(duì)列頭指針指向隊(duì)列表頭結(jié)點(diǎn)，隊(duì)列尾指針指向隊(duì)列的尾結(jié)點(diǎn)。隊(duì)列空的條件是front=rear，即頭尾指針都指向表頭結(jié)點(diǎn)。鏈隊(duì)列的入隊(duì)運(yùn)算在隊(duì)尾進(jìn)行，鏈隊(duì)列的出隊(duì)運(yùn)算在隊(duì)首進(jìn)行。 1入隊(duì) 將x加入到鏈隊(duì)列的尾部，并返回rear。算法描述如下：#include#include typedef struct node int data; struct node*next;NODE; NODE *front,*rear;NODE *crea_linkq() NODE *s； int x,tag; printf(“en

39、ter flag”); scanf(“%d”,&tag); front=(NODE *)malloc(sizeof(NODE); front-data=tag; rear=front; printf(“enter data x:”); scanf(“%d”,&x);while(x!=tag) s=(NODE *) malloc (sizeof (NODE) s-data=x; rear-next=s; rear=s; scanf(“%d”,&x); rear-next=NULL; return(front);NODE*pushq（int x） NODE *p; p=（N

40、ODE*）malloc（sizeof（node）; /*向系統(tǒng)申請一存儲單元p*/ p-data=x; /*將要插入的元素x放入p數(shù)據(jù)域*/ p-next=NULL; /*將p結(jié)點(diǎn)的指針域置為NULL*/ rear-next=p; .*原尾結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)p*. rear=p; /*新元素入隊(duì)后的尾結(jié)點(diǎn)*/ return（rear）;/*返回尾結(jié)點(diǎn)*/main（） /*主程序*/ NODE *p; int x=34; /*x為要入隊(duì)的元素*/ front=crea_linkq（）; /*調(diào)用建立鏈隊(duì)的函數(shù)，并將front指向隊(duì)首，rear指向隊(duì)尾*/ rear=pushq（x）; /*調(diào)用

41、入隊(duì)函數(shù)*/ p=front-next; /*顯示整個隊(duì)列*/ while (p!=NULL) printf(“%d”,p-data); p=p-next; 2出隊(duì) 從帶表頭結(jié)點(diǎn)的鏈隊(duì)列中刪除隊(duì)首元素，并存入*p中，并將存儲單元釋放，若隊(duì)列為空返回空值，返回front。#include#include typedef struct node int data; struct node*next;NODE; NODE *front,*rear; NODE*popq（NODE*front，NODE*rear） int y ; NODE*p; if（front=rear） /*判斷隊(duì)空*/ retu

42、rn（front）; else /*隊(duì)不空*/ p=front-next; /*將頭元素next指針放在p中*/ front-next=p-next; if（p-next=NULL） /*在只有一個元素的情況下*/ rear=front;/*出隊(duì)后，隊(duì)空*/ y=p-data ; free（p）; return（front）; /*返回front*/ main（） /*主程序*/ NODE *p; front=crea_linkq（）; /*調(diào)用建立鏈隊(duì)的函數(shù)，見前述*/ front=popq（front，rear）; p=front-next; /*顯示整個隊(duì)列*/ while (p!=NU

43、LL) printf(“%d”,p-data) ; p=p-next ; 3.2.4 隊(duì)列的應(yīng)用舉例 隊(duì)列在日常生活中和計(jì)算機(jī)程序設(shè)計(jì)中應(yīng)用非常廣泛。下面舉兩個計(jì)算機(jī)應(yīng)用方面的例子。 例例3.3 打印數(shù)據(jù)緩沖區(qū)問題。 在打印機(jī)打印的時候，數(shù)據(jù)是由主機(jī)傳送給打印機(jī)的。主機(jī)輸出數(shù)據(jù)的速度比打印機(jī)打印的速度要快得多。若直接把輸出的數(shù)據(jù)送給打印機(jī)，由于速度不匹配，主機(jī)就要等待打印機(jī)的打印工作，而不能進(jìn)行其他工作。這樣就大大影響了主機(jī)的工作效率。 為了解決這個問題，通常是在內(nèi)存中設(shè)置一個打印數(shù)據(jù)緩沖區(qū)。緩沖區(qū)是一塊連續(xù)的存儲空間，把它設(shè)計(jì)成循環(huán)隊(duì)列結(jié)構(gòu)，主機(jī)把要打印的數(shù)據(jù)依次寫入到這個緩沖區(qū)中，寫滿后就

44、暫停輸出，主機(jī)此時可以進(jìn)行其他工作。打印機(jī)就從緩沖區(qū)按照先進(jìn)先出的原則依次取出數(shù)據(jù)并打印。打印完這批數(shù)據(jù)后，再向主機(jī)發(fā)出請求，主機(jī)接到請求后，再向緩沖區(qū)寫入打印數(shù)據(jù)。 利用緩沖區(qū)，解決了計(jì)算機(jī)數(shù)據(jù)處理與打印機(jī)之間速度不匹配的問題，從而提高了計(jì)算機(jī)的工作效率。 例例3.4 鍵盤輸入循環(huán)緩沖區(qū)問題。 鍵盤輸入是另一個循環(huán)隊(duì)列在計(jì)算機(jī)操作系統(tǒng)中應(yīng)用的實(shí)例。例如，當(dāng)程序正在執(zhí)行某一任務(wù)時，用戶仍然可以從鍵盤輸入其他內(nèi)容。用戶輸入的內(nèi)容暫時未能在屏幕上顯示出來，當(dāng)程序的當(dāng)前任務(wù)結(jié)束時，用戶輸入的內(nèi)容才顯示出來。 在這個過程當(dāng)中，系統(tǒng)是將檢測到的鍵盤輸入的字符先存儲到一個緩沖區(qū)中，當(dāng)系統(tǒng)當(dāng)前任務(wù)結(jié)束后，就

45、從鍵盤緩沖區(qū)依次取出已輸入的字符，并按要求進(jìn)行處理。這是系統(tǒng)設(shè)置的一個鍵盤緩沖區(qū)，也采用了循環(huán)隊(duì)列方式。利用循環(huán)隊(duì)列的工作方式，對字符按次序處理。循環(huán)結(jié)構(gòu)又可以有效地限制了緩沖區(qū)的大小，有效地利用了存儲空間。 習(xí) 題 3一、 選擇題1. 對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序2. 在作進(jìn)棧運(yùn)算時,應(yīng)先判別棧是否( ),在作退棧運(yùn)算時應(yīng)先判別棧是否( )。當(dāng)棧中元素為n個,作進(jìn)棧運(yùn)算時發(fā)生上溢,則說明該棧的最大容量為( )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應(yīng)將兩棧的 ( )分別設(shè)在這片內(nèi)存空間的兩

46、端,這樣,當(dāng)( )時，才產(chǎn)生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D. 棧底 : A. 兩個棧的棧頂同時到達(dá)棧空間的中心點(diǎn). B. 其中一個棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn). C. 兩個棧的棧頂在棧空間的某一位置相遇. D. 兩個棧均不空,且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底.3.3 本章小結(jié) 1棧是一種運(yùn)算受到限制的特殊線性表，它僅允許在線性表同一端進(jìn)行插入和刪除操作，棧是一種后進(jìn)先出的線性表，簡稱為LIFO表。 2棧在日常生活和計(jì)算機(jī)程序設(shè)計(jì)中有著廣泛的應(yīng)用，如算術(shù)表達(dá)式求值、函數(shù)的

47、嵌套和遞歸調(diào)用等。 3隊(duì)列也是一種運(yùn)算受到限制的特殊線性表，它僅允許在線性表一端進(jìn)行插入，在另一端進(jìn)行刪除，隊(duì)列是一種先進(jìn)先出的特殊線性表，簡稱為FIFO表。 4隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)與單鏈表類似，但刪除結(jié)點(diǎn)只能在表頭，插入元素只能在表尾。3. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=ifront-num); else printf(第%d號車停在停車場第%d車位上n,x.num,s1-top); /* Arrive */ void Delive (SqStack *s1,SqStack *s2, LQueue *q,ELEMTP x) /*車輛x離開停車場*/ in

48、t n,f=False; ELEMTP y; QNode *p; while (s1-top0) & (f!=True) /*在棧s1中尋找車輛x */ y=Pop_Sq(s1); if (y.num!=x.num) n=Push_Sq(s2,y); else f=True; if (y.num=x.num) /*尋找到車輛x*/ printf(第%d號車應(yīng)收費(fèi)%d元n,y.num,(x.arrtime-y.arrtime)*M); while (s2-top0) /*將棧s2中的車輛倒回到棧s1中*/ y=Pop_Sq(s2); f=Push_Sq(s1,y); n=DelQueue

49、_L(q); if (n!=NULL) /*便道q上的第一輛車入棧s1*/ y.num=n; y.arrtime=x.arrtime; f=Push_Sq(s1,y); printf(第%d號車停在停車場第%d號車位上n,y.num,s1-top); else /*棧s1中未找到車輛x*/ while (s2-top0) /*將棧s2中的車輛倒回到棧s1中*/ y=Pop_Sq(s2); f=Push_Sq(s1,y); p=q-front; /*在便道q上找到車輛x*/ f=False; while (f=False & p-next!=NULL) if (p-next-num!=x

50、.num) p=p-next; else p-next=p-next-next; q-front-num-; if (p-next=NULL) q-rear=q-front; printf(第%d號車離開便道n,x.num); f=True; if (f=False) printf(輸入數(shù)據(jù)錯誤，停車場和便道上均無%d號車n,x.num); /* Delive */ void Display(SqStack *s1, LQueue *q) /*顯示停車場的狀況*/ int k; QNode *p; printf(停車場狀況:n); if(s1-top!=0) printf(車道 車號n); for(k=0;ktop;k+) printf(%d %dn,k+1,s1-elemk.num); else printf(停車場沒有車輛n); printf(便道狀況:n); if(q-front-num) pr