1、數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 本章主要介紹以下內(nèi)容：本章主要介紹以下內(nèi)容：l 棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作l 隊(duì)列的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作隊(duì)列的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作l 棧與隊(duì)列的應(yīng)用舉例棧與隊(duì)列的應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)3.1 棧棧3.2 隊(duì)列隊(duì)列數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.1.1 3.1.1 棧的定義棧的定義 棧是一種特殊的線性表。其特殊性在于限定插入棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所示：下所示： 進(jìn)行插入和刪除的一端是浮動(dòng)端，通

2、常被稱為進(jìn)行插入和刪除的一端是浮動(dòng)端，通常被稱為棧棧頂頂，并用一個(gè)，并用一個(gè)“棧頂指針棧頂指針”指示；而另一端是固定端，指示；而另一端是固定端，通常被稱為通常被稱為棧底棧底。我們經(jīng)常將棧用下圖。我們經(jīng)常將棧用下圖3-1的形式描述：的形式描述：a1, a2, a3, ., an 插入和刪除端插入和刪除端數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)an.a2a1棧頂 top圖圖 3-1數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 結(jié)論：結(jié)論：后進(jìn)先出后進(jìn)先出（Last In First Out），簡(jiǎn)稱為），簡(jiǎn)稱為L(zhǎng)IFO線性表。線性表。 舉例舉例1：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)地落在

3、一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定地落在一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只最先拿走最上面的那只碗，而最后拿出最下面的那只碗。碗。 舉例舉例2：在建筑工地上，使用的磚塊從底往上一層：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時(shí)，將從最上面一層一層地拿取。一層地碼放，在使用時(shí)，將從最上面一層一層地拿取。 下面我們先給出棧結(jié)構(gòu)的基本操作：下面我們先給出棧結(jié)構(gòu)的基本操作： （1）初始化棧）初始化棧 InitStack(S) （2）入棧）入棧 Push(S,item) （3）出棧）出棧 Pop(S,item) （4）獲取棧頂元素內(nèi)容）

4、獲取棧頂元素內(nèi)容 GetTop(S,item) （5）判斷棧是否為空）判斷棧是否為空 StackEmpty(S) 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.1.2 3.1.2 棧的順序存儲(chǔ)棧的順序存儲(chǔ) 棧的順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元依次棧的順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元依次存放棧中的每個(gè)數(shù)據(jù)元素，并用起始端作為棧底。存放棧中的每個(gè)數(shù)據(jù)元素，并用起始端作為棧底。 類型定義如下所示：類型定義如下所示： #define MAX_STACK 10 /棧的最大數(shù)據(jù)元素?cái)?shù)目棧的最大數(shù)據(jù)元素?cái)?shù)目 typedef struct stack StackEntry itemMAX_STACK; /存放棧中數(shù)據(jù)

5、元素的存儲(chǔ)單元存放棧中數(shù)據(jù)元素的存儲(chǔ)單元 int top; /棧頂指針棧頂指針 STACK;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)基本操作算法：基本操作算法：1. 初始化棧初始化棧S void InItStack(STACK *S) s-top=-1; 2. 入棧入棧 void Push(STACK *S,StackEntry item) if (S-top=MAX_STACK-1) exit(“Stack is full”); else S-item+S-top=item;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)圖圖 3-2MAX_STACK-1.10top= -1數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)3. 出棧出棧 vo

6、id Pop(STACK *S,StackEntry *item)if (StackEmpty(*S) exit(“Stack is empty”); else *item=S-itemS-top-;4. 獲取棧頂元素內(nèi)容獲取棧頂元素內(nèi)容 void GetTop(STACK S,StackEntry *item)if (StackEmpty(S) exit(“Stack is empty”); else *item=S.itemS.top;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 5. 判斷棧判斷棧S是否為空是否為空 int StackEmpty(STACK S) if (S.top=-1) return

7、 TRUE; else FALSE; 結(jié)論：由于棧的插入和刪除操作具有它的特殊性，結(jié)論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時(shí)需要移動(dòng)的問(wèn)題，但棧容量難以擴(kuò)充的弱點(diǎn)仍元素時(shí)需要移動(dòng)的問(wèn)題，但棧容量難以擴(kuò)充的弱點(diǎn)仍就沒(méi)有擺脫。就沒(méi)有擺脫。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.1.3 3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)棧的鏈?zhǔn)酱鎯?chǔ) 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。人們將用鏈的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯?chǔ)

8、結(jié)構(gòu)表示的棧稱作式存儲(chǔ)結(jié)構(gòu)表示的棧稱作“鏈棧鏈?！?。鏈棧通常用一個(gè)。鏈棧通常用一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表表示。如圖無(wú)頭結(jié)點(diǎn)的單鏈表表示。如圖3-3所示。所示。 由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來(lái)說(shuō)，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)地容單鏈表來(lái)說(shuō)，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)地容易一些，所以，我們將單鏈表的首端作為棧頂端，即易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。將單鏈表的頭指針作為棧頂指針。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) top圖 3-3數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在C語(yǔ)言中

9、可用下列類型定義實(shí)現(xiàn)：語(yǔ)言中可用下列類型定義實(shí)現(xiàn)：type struct node /鏈棧的結(jié)點(diǎn)結(jié)構(gòu)鏈棧的結(jié)點(diǎn)結(jié)構(gòu) StackEntry item; /棧的數(shù)據(jù)元素類型棧的數(shù)據(jù)元素類型 struct node *next; /指向后繼結(jié)點(diǎn)的指針指向后繼結(jié)點(diǎn)的指針NODE; typedef struct stack NODE *top;STACK; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)下面我們將給出鏈棧各項(xiàng)基本操作的算法。下面我們將給出鏈棧各項(xiàng)基本操作的算法。1. 初始化棧初始化棧S void InitStack(STACK *S) S-top=NULL;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)2. 入棧入棧 vo

10、id Push(STACK *S,StackEntry item) p=(NODE*)malloc(sizeof(NODE); if (!p) exit(OVERFLOW); else p-item=item; p-next=S-top; S-top=p; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)3. 出棧出棧void Pop(STACK*S, StackEntry *item)if (StackEmpty(*S) exit(“Stack is empty”);else *item=S-top-item; p=S-top; S-top=p-next; free(p); 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)4. 獲

11、取棧頂元素內(nèi)容獲取棧頂元素內(nèi)容 void GetTop(STACK S,StackEntry *item) if (StackEmpty(S) exit(“Stack is empty”); else *item=S.top-item;5. 判斷棧判斷棧S是否空是否空 int StackEmpty(STACK S) if (S.top=NULL) return TRUE; else FALSE;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.1.4 3.1.4 棧的應(yīng)用舉例棧的應(yīng)用舉例 【舉例舉例1 1】將從鍵盤(pán)輸入的字符序列逆置輸出將從鍵盤(pán)輸入的字符序列逆置輸出 比如，從鍵盤(pán)上輸入：比如，從鍵盤(pán)上輸入：t

12、set a si sihT；算法將輸出：；算法將輸出：This is a test 下面我們給出解決這個(gè)問(wèn)題的完整算法。下面我們給出解決這個(gè)問(wèn)題的完整算法。 typedef char StackEntry; void ReverseRead( ) STACK S; /定義一個(gè)棧結(jié)構(gòu)定義一個(gè)棧結(jié)構(gòu)S char ch; InitStack(&S); /初始化棧初始化棧數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)while (ch=getchar()!=n) /從鍵盤(pán)輸入字符，直到輸入換行符為止從鍵盤(pán)輸入字符，直到輸入換行符為止 Push(&S ,ch); /將輸入的每個(gè)字符入棧將輸入的每個(gè)字符入棧

13、while (!StackEmpty(S) /依次退棧并輸出退出的字符依次退棧并輸出退出的字符 Pop(&S,&ch); putchar(ch);putchar(n);數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)【舉例舉例2 2】十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制 使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)；重復(fù)，并保留其余數(shù)；重復(fù)此操作，直到該十進(jìn)制數(shù)值為此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余為止。最后將所有的余數(shù)反向輸出就是所對(duì)應(yīng)的二進(jìn)制數(shù)值。數(shù)反向輸出就是所對(duì)

14、應(yīng)的二進(jìn)制數(shù)值。 比如：比如：(692)10 = (1010110100)2，其展轉(zhuǎn)相除的過(guò)程，其展轉(zhuǎn)相除的過(guò)程如圖如圖3-4所示：所示：數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)圖圖 3-4除數(shù) 被除數(shù)余數(shù)2 6922 346 02 173 02 86 12 43 02 21 12 10 12 5 02 2 12 1 00 1數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)下面給出解決這個(gè)問(wèn)題的完整算法。下面給出解決這個(gè)問(wèn)題的完整算法。void Decimal _ Binary ( )STACK S; /定義棧結(jié)構(gòu)定義棧結(jié)構(gòu)SInitStack(&S); /初始化棧初始化棧Sscanf(“%d”,data); /輸入

15、十進(jìn)制正整數(shù)輸入十進(jìn)制正整數(shù)數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)while (data) Push(&S,data%2); /余數(shù)入棧余數(shù)入棧 data/=2; /被除數(shù)被除數(shù)data整除以整除以2，得到新的被除數(shù)，得到新的被除數(shù)while (!StackEmpty(S) /依次從棧中彈出每一個(gè)余數(shù)，并輸出之依次從棧中彈出每一個(gè)余數(shù)，并輸出之 Pop(&S,&data); printf(“%d”,data);數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)【舉例舉例3 3】檢驗(yàn)表達(dá)式中的括號(hào)匹配情況檢驗(yàn)表達(dá)式中的括號(hào)匹配情況 假設(shè)在一個(gè)算術(shù)表達(dá)式中，可以包含三種括號(hào)：假設(shè)在一個(gè)算術(shù)表達(dá)式中，可以包

16、含三種括號(hào)：圓括號(hào)圓括號(hào)“（”和和“）”，方括號(hào)，方括號(hào)“”和和“”和花括號(hào)和花括號(hào)“”和和“”，并且這三種括號(hào)可以按任意的次序嵌套，并且這三種括號(hào)可以按任意的次序嵌套使用。比如，使用。比如，.(.).?，F(xiàn)在需要設(shè)?，F(xiàn)在需要設(shè)計(jì)一個(gè)算法，用來(lái)檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用計(jì)一個(gè)算法，用來(lái)檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用括號(hào)的合法性。括號(hào)的合法性。 算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間可以嵌套，但不能出現(xiàn)交叉情況。我們可以利用一個(gè)可以嵌套，但不能出現(xiàn)交叉情況。

17、我們可以利用一個(gè)棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)時(shí)，從棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)時(shí)，從棧中彈出左括號(hào)，檢驗(yàn)匹配情況。在檢驗(yàn)過(guò)程中，若棧中彈出左括號(hào)，檢驗(yàn)匹配情況。在檢驗(yàn)過(guò)程中，若遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)論。論。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) （1）當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說(shuō)明到目）當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說(shuō)明到目前為止，右括號(hào)多于左括號(hào)；前為止，右括號(hào)多于左括號(hào)； （2）從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類）從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類型不同，說(shuō)明出現(xiàn)了括號(hào)交叉情況；型不同，說(shuō)明出現(xiàn)

18、了括號(hào)交叉情況； （3）算術(shù)表達(dá)式輸入完畢，但棧中還有沒(méi)有匹配）算術(shù)表達(dá)式輸入完畢，但棧中還有沒(méi)有匹配的左括號(hào)，說(shuō)明左括號(hào)多于右括號(hào)。的左括號(hào)，說(shuō)明左括號(hào)多于右括號(hào)。 下面是解決這個(gè)問(wèn)題的完整算法。下面是解決這個(gè)問(wèn)題的完整算法。 typedef char StackEntry; int Check( ) STACK S; /定義棧結(jié)構(gòu)定義棧結(jié)構(gòu)S char ch;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)InitStack(&S); /初始化棧初始化棧Swhile (ch=getchar()!=n) /以字符序列的形式輸入表達(dá)式以字符序列的形式輸入表達(dá)式 switch (ch) c a s e (

19、c h = = ( | | c h = = | | c h = = ) : Push(&S,ch);break; /遇左括號(hào)入棧遇左括號(hào)入棧 /在遇到右括號(hào)時(shí)，分別檢測(cè)匹配情況在遇到右括號(hào)時(shí)，分別檢測(cè)匹配情況case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch); if (ch!= () return FALSE; break;case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch);數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)if (c

20、h!= ) return FALSE; break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(&S,&ch); if (ch!= ) return FALSE; break; default:break; if (StackEmpty(S) return TRUE; else return FALSE;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.2.1 3.2.1 隊(duì)列的定義隊(duì)列的定義 隊(duì)列特殊性在于限定插入在線性表的一端進(jìn)行，隊(duì)列特殊性在于限定插入在線性表的一端進(jìn)行，刪除在線性表的另外一端進(jìn)行。如圖刪除在線性表的另外一

21、端進(jìn)行。如圖3-5所示：所示：a1a2a3.ai.an -1an插 入 端刪 除 端圖圖 3-5數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 插入端和刪除端都是浮動(dòng)的。通常我們將插入端插入端和刪除端都是浮動(dòng)的。通常我們將插入端稱為稱為隊(duì)尾隊(duì)尾，用一個(gè)，用一個(gè)“隊(duì)尾指針隊(duì)尾指針”指示；而刪除端被稱指示；而刪除端被稱為為隊(duì)頭隊(duì)頭，用一個(gè)，用一個(gè)“隊(duì)頭指針隊(duì)頭指針”指示。指示。 結(jié)論：結(jié)論：先進(jìn)先出先進(jìn)先出（First In First Out），簡(jiǎn)稱為），簡(jiǎn)稱為FIFO線性表。線性表。 舉例舉例1：到醫(yī)院看病，首先需要到掛號(hào)處掛號(hào)，然：到醫(yī)院看病，首先需要到掛號(hào)處掛號(hào)，然后，按號(hào)碼順序救診。后，按號(hào)碼順序救診。

22、舉例舉例2：乘坐公共汽車(chē)，應(yīng)該在車(chē)站排隊(duì)，車(chē)來(lái)后，：乘坐公共汽車(chē)，應(yīng)該在車(chē)站排隊(duì)，車(chē)來(lái)后，按順序上車(chē)。按順序上車(chē)。 舉例舉例3：在：在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個(gè)應(yīng)用程序響應(yīng)一系列的每個(gè)應(yīng)用程序響應(yīng)一系列的“消息消息”，像用戶點(diǎn)擊鼠，像用戶點(diǎn)擊鼠標(biāo)；拖動(dòng)窗口這些操作都會(huì)導(dǎo)致向應(yīng)用程序發(fā)送消息。標(biāo)；拖動(dòng)窗口這些操作都會(huì)導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個(gè)應(yīng)用程序創(chuàng)建一個(gè)隊(duì)列，用來(lái)存為此，系統(tǒng)將為每個(gè)應(yīng)用程序創(chuàng)建一個(gè)隊(duì)列，用來(lái)存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過(guò)放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過(guò)程就是不斷地從隊(duì)列中讀取消息

23、，并依次給予響應(yīng)。程就是不斷地從隊(duì)列中讀取消息，并依次給予響應(yīng)。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)下面我們給出隊(duì)列結(jié)構(gòu)的基本操作：下面我們給出隊(duì)列結(jié)構(gòu)的基本操作：（1）初始化隊(duì)列）初始化隊(duì)列 InitQueue(Q) （2）入隊(duì)）入隊(duì) EnQueue(Q,item) （3）出隊(duì)）出隊(duì) DeQueue(Q,item) （4）獲取隊(duì)頭元素內(nèi)容）獲取隊(duì)頭元素內(nèi)容 GetFront(Q,item) （5）判斷隊(duì)列是否為空）判斷隊(duì)列是否為空 QueueEmpty(Q) 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)3.2.2 3.2.2 隊(duì)列的順序存儲(chǔ)隊(duì)列的順序存儲(chǔ) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖3-6所示：

24、所示：012n-2n-1a1a2a3.an-1an frontrear圖圖 3-6數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 問(wèn)題問(wèn)題1：當(dāng)隊(duì)空時(shí)，隊(duì)頭和隊(duì)尾指針都為：當(dāng)隊(duì)空時(shí)，隊(duì)頭和隊(duì)尾指針都為-1，隊(duì)列，隊(duì)列將處于下圖將處于下圖3-7所示的狀態(tài)：所示的狀態(tài)：012.n-2n-1front=-1rear=-1圖圖 3-7數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 此時(shí)若進(jìn)行入隊(duì)操作，就需要讓隊(duì)頭和隊(duì)尾指針此時(shí)若進(jìn)行入隊(duì)操作，就需要讓隊(duì)頭和隊(duì)尾指針都增都增1，再將新數(shù)據(jù)元素放入該位置。也就是說(shuō)，這樣，再將新數(shù)據(jù)元素放入該位置。也就是說(shuō)，這樣設(shè)置隊(duì)頭、隊(duì)尾指針位置，在進(jìn)行入隊(duì)操作時(shí)，空隊(duì)設(shè)置隊(duì)頭、隊(duì)尾指針位置，在進(jìn)行入隊(duì)操

25、作時(shí)，空隊(duì)與非空隊(duì)狀態(tài)所需要執(zhí)行的操作不完全一樣。與非空隊(duì)狀態(tài)所需要執(zhí)行的操作不完全一樣。 解決方法：在算法中，需要對(duì)這兩種情況加以區(qū)分，解決方法：在算法中，需要對(duì)這兩種情況加以區(qū)分，這勢(shì)必增加了算法的復(fù)雜性。因此，人們?cè)O(shè)想了一種這勢(shì)必增加了算法的復(fù)雜性。因此，人們?cè)O(shè)想了一種解決方法，即讓隊(duì)頭指針指向隊(duì)列真正隊(duì)頭元素的前解決方法，即讓隊(duì)頭指針指向隊(duì)列真正隊(duì)頭元素的前一個(gè)位置，如下圖一個(gè)位置，如下圖3-8所示。所示。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)012n-2n-1a1a2a3.an-1anfrontrear圖圖 3-8數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 問(wèn)題問(wèn)題2：由于順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間屬于靜態(tài)分：

26、由于順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間屬于靜態(tài)分配，所以，在添加數(shù)據(jù)元素時(shí)，可能會(huì)出現(xiàn)沒(méi)有剩余配，所以，在添加數(shù)據(jù)元素時(shí)，可能會(huì)出現(xiàn)沒(méi)有剩余單元的情況。對(duì)于隊(duì)列來(lái)說(shuō)，這一點(diǎn)又有它的特殊性。單元的情況。對(duì)于隊(duì)列來(lái)說(shuō)，這一點(diǎn)又有它的特殊性。下面我們討論一下下圖下面我們討論一下下圖3-10所示的隊(duì)列。所示的隊(duì)列。01234567a5a6a7a8frontrear圖圖 3-10數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) “假溢出假溢出”現(xiàn)象?，F(xiàn)象。 解決方法：將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接，解決方法：將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接，形成一個(gè)環(huán)狀。如圖形成一個(gè)環(huán)狀。如圖3-11所示。我們將這種形式表示所示。我們將這種形式表示

27、的隊(duì)列稱之為的隊(duì)列稱之為循環(huán)隊(duì)列循環(huán)隊(duì)列。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)a8a7a6a576543210rearfront圖圖 3-11數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 假設(shè)為隊(duì)列開(kāi)辟的數(shù)組單元數(shù)目為假設(shè)為隊(duì)列開(kāi)辟的數(shù)組單元數(shù)目為MAX_QUEUE，在在C語(yǔ)言中，它的下標(biāo)在語(yǔ)言中，它的下標(biāo)在0MAX_QUEUE-1之間，若之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算（一個(gè)整數(shù)增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算（一個(gè)整數(shù)數(shù)值整除以另一個(gè)整數(shù)數(shù)值的余數(shù)）實(shí)現(xiàn)。如下所示：數(shù)值整除以另一個(gè)整數(shù)數(shù)值的余數(shù)）實(shí)現(xiàn)。如下所示： front=(front+1)%MAX_QUEUE； rear=(rear+1)%M

28、AX_QUEUE； 當(dāng)當(dāng)front或或rear為為MAXQUEUE-1時(shí)，上述兩個(gè)公式時(shí)，上述兩個(gè)公式計(jì)算的結(jié)果就為計(jì)算的結(jié)果就為0。這樣，就使得指針自動(dòng)由后面轉(zhuǎn)到。這樣，就使得指針自動(dòng)由后面轉(zhuǎn)到前面，形成循環(huán)的效果。前面，形成循環(huán)的效果。 隊(duì)空和隊(duì)滿的標(biāo)志問(wèn)題：隊(duì)空和隊(duì)滿的標(biāo)志問(wèn)題： 隊(duì)列變?yōu)榭眨?duì)頭和隊(duì)尾指針相等。隊(duì)列變?yōu)榭眨?duì)頭和隊(duì)尾指針相等。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)a7 a876543210rearfront76543210rearfront(a)(b)圖圖 3-12隊(duì)列變?yōu)闈M，隊(duì)頭和隊(duì)尾指針也相等。隊(duì)列變?yōu)闈M，隊(duì)頭和隊(duì)尾指針也相等。數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)rearfronta

29、6a5a4a3a1a276543210a6a5a4a3a1a2a8a776543210rearfront(a)(b)圖圖 3-13數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 解決方法：一是為隊(duì)列另設(shè)一個(gè)標(biāo)志，用來(lái)區(qū)分解決方法：一是為隊(duì)列另設(shè)一個(gè)標(biāo)志，用來(lái)區(qū)分隊(duì)列是隊(duì)列是“空空”還是還是“滿滿”；二是當(dāng)數(shù)組只剩下一個(gè)單；二是當(dāng)數(shù)組只剩下一個(gè)單元時(shí)就認(rèn)為隊(duì)滿，此時(shí)，隊(duì)尾指針只差一步追上隊(duì)頭元時(shí)就認(rèn)為隊(duì)滿，此時(shí)，隊(duì)尾指針只差一步追上隊(duì)頭指針，即：指針，即：(rear+1)%MAX_QUEUE=front。 類型定義：類型定義： #define MAX_QUEUE 10 /隊(duì)列的最大數(shù)據(jù)元素?cái)?shù)目隊(duì)列的最大數(shù)據(jù)元素?cái)?shù)

30、目 typedef struct queue /假設(shè)當(dāng)數(shù)組只剩下一個(gè)單元時(shí)認(rèn)為隊(duì)滿假設(shè)當(dāng)數(shù)組只剩下一個(gè)單元時(shí)認(rèn)為隊(duì)滿 QueueEntry itemMAX_QUEUE; /存放隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)單元存放隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)單元 int front,rear; /隊(duì)頭指針、隊(duì)尾指針隊(duì)頭指針、隊(duì)尾指針 QUEUE;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)各項(xiàng)基本操作算法。各項(xiàng)基本操作算法。（1）初始化隊(duì)列）初始化隊(duì)列Q void InitQueue(QUEUE *Q) Q-front=-1; Q-rear=-1;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（2）入隊(duì)）入隊(duì) void EnQueue(QUEUE *Q,Que

31、ueEntry item) if (Q-rear+1)%MAX_QUEUE=Q-front) exit(OVERFLOW); else Q-rear=(Q-rear+1)%MAX_QUEUE; Q-itemQ-rear=item; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（3）出隊(duì)）出隊(duì) void DeQueue(QUEUE*Q,QueueEntry *item) if (QueueEmpty(*Q) exit(“Queue is empty.”); else Q-front=(Q-front+1)%MAX_QUEUE; *item=Q-itemQ-front; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（4）獲取隊(duì)頭

32、元素內(nèi)容）獲取隊(duì)頭元素內(nèi)容 void GetFront(QUEUE Q,QueueEntry *item) if (QueueEmpty(Q) exit(“Queue is empty.”); else *item=Q.item(Q.front+1)%MAX_QUEUE;（5）判斷隊(duì)列）判斷隊(duì)列Q是否為空是否為空 int QueueEmpty(Queue Q) if (Q.front=Q.rear) return TRUE; else return FALSE;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 3.2.3 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)隊(duì)列的鏈?zhǔn)酱鎯?chǔ) 在用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示隊(duì)列時(shí)，需要設(shè)置隊(duì)頭指在用鏈?zhǔn)?/p>

33、存儲(chǔ)結(jié)構(gòu)表示隊(duì)列時(shí)，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。frontrear圖圖 3-14數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)入隊(duì)需要執(zhí)行下面三條語(yǔ)句：入隊(duì)需要執(zhí)行下面三條語(yǔ)句：s-next=NULL; rear-next=s;rear=s;下面是在下面是在C語(yǔ)言中，實(shí)現(xiàn)隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義：語(yǔ)言中，實(shí)現(xiàn)隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的類型定義：type struct node /鏈?zhǔn)疥?duì)列的結(jié)點(diǎn)結(jié)構(gòu)鏈?zhǔn)疥?duì)列的結(jié)點(diǎn)結(jié)構(gòu) QueueEntry Entry; /隊(duì)列的數(shù)據(jù)元素類型隊(duì)列的數(shù)據(jù)元素類型 struct node *next; /指向后繼結(jié)點(diǎn)的指針

34、指向后繼結(jié)點(diǎn)的指針NODE;typedef struct queue /鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列 NODE *front; /隊(duì)頭指針隊(duì)頭指針 NODE *rear; /隊(duì)尾指針隊(duì)尾指針QUEUE; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)下面我們給出鏈?zhǔn)疥?duì)列的基本操作算法。下面我們給出鏈?zhǔn)疥?duì)列的基本操作算法。（1）初始化隊(duì)列）初始化隊(duì)列Q void InitQueue(QUEUE *Q) Q-front=(NODE*)malloc(sizeof(NODE); if (Q-front=NULL) exit(ERROR); Q-rear= Q-front;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（2）入隊(duì)）入隊(duì) void En

35、Queue(QUEUE *Q,QueueEntry item) s=(NODE*)malloc(sizeof(NODE); if (!s) exit(ERROR); s-item=item; s-next=NULL; Q-rear-next=s; Q-rear=s; 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（3）出隊(duì)）出隊(duì) void DeQueue(QUEUE *Q,QueueEntry *item) if (QueueEmpty(*Q) exit(ERROR); else *item=Q-front-next-item; s=Q-front-next; Q-front-next=s-next; free

36、(s); 數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列)（4）獲取隊(duì)頭元素內(nèi)容）獲取隊(duì)頭元素內(nèi)容 void GetFront(QUEUE Q,QueueEntry *item) if (QueueEmpty(Q) exit(ERROR); else *item=Q-front-next-item;（5）判斷隊(duì)列）判斷隊(duì)列Q是否為空是否為空 int QueueEmpty(QUEUE Q) if (Q-front=Q-rear) return TRUE； else return FALSE;數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版(棧和隊(duì)列) 4 4隊(duì)列的應(yīng)用舉例隊(duì)列的應(yīng)用舉例【舉例舉例1 1】汽車(chē)加油站。汽車(chē)加油站。 隨著城市里汽車(chē)數(shù)量的急速增長(zhǎng)，汽車(chē)加油站也隨著城市里汽車(chē)數(shù)量的