本章主要內(nèi)容1、棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作及其應(yīng)用;2、

1、本章主要內(nèi)容：1、棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作及其應(yīng)用；2、隊(duì)列的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作及其應(yīng)用課時(shí)分配：1、2各占2學(xué)時(shí)，上機(jī)2學(xué)時(shí)重點(diǎn)、難點(diǎn)：棧的存儲(chǔ)結(jié)構(gòu)及其基本操作、隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本操作3.1 棧3.1.1 棧的定義棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所示：結(jié)論：后進(jìn)先出（Last In First Out），簡稱為LIFO線性表。例31：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)地落在一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。例32：在建筑工地上，使用的磚塊從底往上一層一層地碼放，

2、在使用時(shí)，將從最上面一層一層地拿取。下面我們先給出棧結(jié)構(gòu)的基本操作：（1）初始化棧 InitStack(S) （2）入棧 Push(S,elem) （3）出棧 Pop(S,elem) （4）獲取棧頂元素內(nèi)容 GetTop(S,elem) （5）判斷棧是否為空 StackEmpty(S) 3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元依次存放棧中的每個(gè)數(shù)據(jù)元素，并用起始端作為棧底。類型定義如下所示：#define MAXSIZE 100#define ERROR -1typedef struct /* 棧類定義 */int elementsMAXSIZE;i

3、nt top; Stack;基本操作算法：（1）初始化棧void InitStack( Stack *S ) /* 初始化棧，將棧置空 */S-top = 0;（2）入棧 void Push(Stack *S, int x) /* 將元素x壓入到棧S中 */if( !IsFull(*S) ) /* 如果尚未達(dá)到棧滿，則將x壓入棧S中，并使棧頂指針增1 */S-elementsS-top = x;S-top+;elseprintf( 棧上溢！n );（3）出棧 int Pop( Stack *S ) /* 將棧S中的棧頂元素出棧 */if( !IsEmpty( *S ) ) /* 如果棧非空，則

4、返回棧頂元素，并使棧頂指針減1 */S-top-;return S-elementsS-top;elseprintf( 棧下溢！n );return ERROR;（4）獲取棧頂元素內(nèi)容 int GetTop( Stack S ) /* 獲取棧頂元素，但不改變棧頂指針 */if( !IsEmpty( S ) )return S.elementsS.top-1;elseprintf( ?？?！n );return ERROR;（5）判斷棧S是否為空bool IsEmpty( Stack S) /* 判斷棧是否為空。如果?？?，返回true，否則返回false */if( S.top = 0 ) ret

5、urn true;else return false;結(jié)論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時(shí)需要移動(dòng)的問題，但棧容量難以擴(kuò)充的弱點(diǎn)仍就沒有擺脫。3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)及其基本運(yùn)算的實(shí)現(xiàn) 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱作鏈棧。鏈棧通常用一個(gè)無頭結(jié)點(diǎn)的單鏈表表示。如圖示：11966nulltopbottom結(jié)點(diǎn)類型定義：typedef struct node /* 棧類定義 */int data;struct node *next; LinkStack;（1）

6、初始化void InitLinkStack( LinkStack *top ) /* 初始化棧，將棧置空 */*top = NULL;（2）判斷是否為空bool IsEmpty( LinkStack *top) /* 判斷棧是否為空。如果?？?，返回true，否則返回false */if( top = NULL ) return true;else return false;（3）進(jìn)棧void Push(LinkStack *top, int x) /* 將元素x壓入到棧S中，先申請(qǐng)結(jié)點(diǎn)再將其入棧 */LinkStack *S;S = (LinkStack *)malloc( sizeof(Li

7、nkStack) );S-data = x;S-next = *top;*top = S;（4）出棧int Pop( LinkStack *top ) /* 將棧S中的棧頂元素出棧 */LinkStack *S;int data;if( !IsEmpty( *top ) ) /* 如果棧非空，則返回棧頂元素，并使棧頂指針減1 */S = *top;*top = (*top)-next;data = S-data;free( S );return data;elseprintf( 棧下溢！n );return ERROR;（5）取棧頂元素int GetTop( LinkStack *top )

8、/* 獲取棧頂元素，但不改變棧頂指針 */if( !IsEmpty( top ) )return top-data;elseprintf( 棧空！n );return ERROR;（6）清空void EmptyLinkStack( LinkStack *top ) /* 清空堆棧S，使其棧頂指針為0 */LinkStack *S;while( *top != NULL )S = (*top)-next;free( *top );*top = S;3.1.4 棧的應(yīng)用舉例例3-3: 將從鍵盤輸入的字符序列逆置輸出比如，從鍵盤上輸入：tset a si sihT；算法將輸出：This is a t

9、est下面我們給出解決這個(gè)問題的完整算法。typedef char Elemtype;void ReverseRead( ) Stack S; /定義一個(gè)棧結(jié)構(gòu)Schar ch; InitStack(&S); /初始化棧while (ch=getchar()!=n) /從鍵盤輸入字符，直到輸入換行符為止Push(&S ,ch); /將輸入的每個(gè)字符入棧while (!StackEmpty(S) /依次退棧并輸出退出的字符Pop(&S,&ch);putchar(ch);putchar(n);例34： 十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制 使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，

10、并保留其余數(shù)；重復(fù)此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是所對(duì)應(yīng)的二進(jìn)制數(shù)值。比如：(692)10 = (1010110100)2，其展轉(zhuǎn)相除的過程如圖所示：下面給出解決這個(gè)問題的完整算法。void Decimal _ Binary ( )STACK S; /定義棧結(jié)構(gòu)S InitStack(&S); /初始化棧Sscanf(%d,data); /輸入十進(jìn)制正整數(shù)while (data) Push(&S,data%2); /余數(shù)入棧data/=2; /被除數(shù)data整除以2，得到新的被除數(shù)while (!StackEmpty(S) /依次從棧中彈出每一個(gè)余數(shù)，并輸出之Po

11、p(&S,&data); printf(%d,data);例35： 檢驗(yàn)表達(dá)式中的括號(hào)匹配情況 假設(shè)在一個(gè)算術(shù)表達(dá)式中，可以包含三種括號(hào)：圓括號(hào)（和），方括號(hào)和和花括號(hào)和，并且這三種括號(hào)可以按任意的次序嵌套使用。比如，.(.).。現(xiàn)在需要設(shè)計(jì)一個(gè)算法，用來檢驗(yàn)在輸入的算術(shù)表達(dá)式中所使用括號(hào)的合法性。算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間可以嵌套，但不能出現(xiàn)交叉情況。我們可以利用一個(gè)棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)時(shí)，從棧中彈出左括號(hào)，檢驗(yàn)匹配情況。在檢驗(yàn)過程中，若遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)論。（1）當(dāng)遇到某一個(gè)右括號(hào)

12、時(shí)，棧已空，說明到目前為止，右括號(hào)多于左括號(hào)；（2）從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類型不同，說明出現(xiàn)了括號(hào)交叉情況；（3）算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號(hào)，說明左括號(hào)多于右括號(hào)。下面是解決這個(gè)問題的完整算法。typedef char Elemtype;int Check( )STACK S; /定義棧結(jié)構(gòu)Schar ch; InitStack(&S); /初始化棧Swhile (ch=getchar()!=n) /以字符序列的形式輸入表達(dá)式switch (ch) case (ch=(|ch= |ch= ): Push(&S,ch);break; /遇左括號(hào)入棧/在遇到右括號(hào)

13、時(shí)，分別檢測匹配情況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);if (ch!= ) return FALSE; break;case (ch= ): if (StackEmpty(S) retrun FALSE;else Pop(&S,&ch);if (ch!= ) return FALSE; break;default:brea

14、k;if (StackEmpty(S) return TRUE;else return FALSE;3.2 隊(duì)列3.2.1 隊(duì)列的定義插入端和刪除端都是浮動(dòng)的。通常我們將插入端稱為隊(duì)尾，用一個(gè)隊(duì)尾指針指示；而刪除端被稱為隊(duì)頭，用一個(gè)隊(duì)頭指針指示。結(jié)論：先進(jìn)先出（First In First Out），簡稱為FIFO線性表。例3-6：到醫(yī)院看病，首先需要到掛號(hào)處掛號(hào)，然后，按號(hào)碼順序救診。例3-7：乘坐公共汽車，應(yīng)該在車站排隊(duì)，車來后，按順序上車。例3-8：在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個(gè)應(yīng)用程序響應(yīng)一系列的消息，像用戶點(diǎn)擊鼠標(biāo)； 拖動(dòng)窗口這些操作都會(huì)導(dǎo)致向應(yīng)用程序發(fā)送消息。為此

15、，系統(tǒng)將為每個(gè)應(yīng)用程序創(chuàng)建一個(gè)隊(duì)列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊(duì)列中讀取消息，并依次給予響應(yīng)。下面我們給出隊(duì)列結(jié)構(gòu)的基本操作：（1）初始化隊(duì)列 InitQueue(Q) （2）入隊(duì) EnQueue(Q,elem) （3）出隊(duì) DeQueue(Q,elem) （4）獲取隊(duì)頭元素內(nèi)容 GetFront(Q,elem) （5）判斷隊(duì)列是否為空 QueueEmpty(Q)3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：012n-2n-1a1a2a3an-1an問題1：當(dāng)隊(duì)列空時(shí)，對(duì)頭和隊(duì)尾指針都為1，隊(duì)列將變成下圖所示狀態(tài)：012n

16、-2n-1問題2：假溢出，即，在添加數(shù)據(jù)時(shí)，可能出現(xiàn)沒有剩余空間而實(shí)際隊(duì)列又不滿的狀況。如：01234567a5a6a7a8rearfront解決辦法：將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接形成一個(gè)環(huán)狀，即循環(huán)隊(duì)列，如下圖：rearfront32107654a8a7a6a5假設(shè)為隊(duì)列開辟的數(shù)組單元數(shù)目為MAX_QUEUE，在C語言中，它的下標(biāo)在0MAX_QUEUE-1之間，若增加隊(duì)頭或隊(duì)尾指針，可以利用取模運(yùn)算（一個(gè)整數(shù)數(shù)值整除以另一個(gè)整數(shù)數(shù)值的余數(shù)）實(shí)現(xiàn)。如下所示：front=(front+1)%MAX_QUEUE； rear=(rear+1)%MAX_QUEUE；當(dāng)front或rear為MAXQ

17、UEUE-1時(shí)，上述兩個(gè)公式計(jì)算的結(jié)果就為0。這樣，就使得指針自動(dòng)由后面轉(zhuǎn)到前面，形成循環(huán)的效果。隊(duì)空和隊(duì)滿的標(biāo)志問題：隊(duì)列變?yōu)榭眨?duì)頭和隊(duì)尾指針相等。解決方法：一是為隊(duì)列另設(shè)一個(gè)標(biāo)志，用來區(qū)分隊(duì)列是空還是滿；二是當(dāng)數(shù)組只剩下一個(gè)單元時(shí)就認(rèn)為隊(duì)滿，此時(shí)，隊(duì)尾指針只差一步追上隊(duì)頭指針，即：(rear+1)%MAX_QUEUE=front。類型定義：#define MAX_QUEUE 10 /隊(duì)列的最大數(shù)據(jù)元素?cái)?shù)目typedef struct queue /假設(shè)當(dāng)數(shù)組只剩下一個(gè)單元時(shí)認(rèn)為隊(duì)滿Elemtype elemMAX_QUEUE; /存放隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)單元int front,rear;

18、 /隊(duì)頭指針、隊(duì)尾指針QUEUE;各項(xiàng)基本操作算法。（1）初始化隊(duì)列Q void InitQueue(QUEUE *Q)Q-front=-1;Q-rear=-1;（2）入隊(duì) void EnQueue(QUEUE *Q,Elemtype elem)if (Q-rear+1)%MAX_QUEUE=Q-front) exit(OVERFLOW);else Q-rear=(Q-reasr+1)%MAX_QUEUE;Q-elemQ-rear=elem; （3）出隊(duì) void DeQueue(QUEUE*Q,Elemtype *elem)if (QueueEmpty(*Q) exit(Queue is e

19、mpty.);else Q-front=(Q-front+1)%MAX_QUEUE;*elem=Q-elemQ-front;（4）獲取隊(duì)頭元素內(nèi)容 void GetFront(QUEUE Q,Elemtype *elem) if (QueueEmpty(Q) exit(Queue is empty.);else *elem=Q.elem(Q.front+1)%MAX_QUEUE;（5）判斷隊(duì)列Q是否為空 int QueueEmpty(Queue Q)if (Q.front=Q.rear) return TRUE;else return FALSE; 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的

20、實(shí)現(xiàn)在用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)隊(duì)列時(shí)，需要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。a0a1a2an-1 鏈?zhǔn)酱鎯?chǔ)的隊(duì)列的一般形式q.frontq.rear結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct node /* 隊(duì)列結(jié)點(diǎn)類型定義 */int data;struct node *next; LinkQueue;typedef struct /* 隊(duì)列頭結(jié)點(diǎn)類型定義 */LinkQueue *front; /* 隊(duì)列的隊(duì)首指針 */LinkQueue *rear; /* 隊(duì)列的隊(duì)尾指針 */ Queue;基本運(yùn)算：（1） 初始化void InitQueue( Queue *Q ) /* 初

21、始化隊(duì)列，生成一個(gè)帶哨兵的空隊(duì)列 */Q-front = (LinkQueue *)malloc( sizeof(LinkQueue) );Q-front-next = NULL;Q-rear = Q-front;（2） 判空bool IsEmpty( Queue Q) /* 判斷隊(duì)列是否為空。如果隊(duì)列為空，返回true，否則返回false */if( Q.front = Q.rear ) return true;else return false;（3） 進(jìn)隊(duì)void EnQueue( Queue *Q, int x) /* 將元素x壓入到隊(duì)列Q中，先申請(qǐng)結(jié)點(diǎn)再將其入隊(duì) */Q-rear-next = (LinkQueue *)malloc( sizeof(LinkQueue) );Q-rear = Q-rear-next;Q-rear-data = x;Q-rear-next = NULL;（4） 出隊(duì)int DeQueue( Queue *Q ) /* 將隊(duì)列Q中的隊(duì)首元素出隊(duì) */LinkQueue *p;int data;if( !IsEmpty( *Q ) ) /* 如果隊(duì)列非空，則返回隊(duì)首元素 */p = Q-front-next;Q-front-next = p-next;/* 當(dāng)將隊(duì)列中的一個(gè)元素刪除后，指針rear就懸浮起來了，需要將其調(diào)整到正確