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

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

2、在使用時，將從最上面一層一層地拿取。下面我們先給出棧結(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 棧的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)棧的順序存儲結(jié)構(gòu)是用一組連續(xù)的存儲單元依次存放棧中的每個數(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) ) /* 如果尚未達到棧滿，則將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) /* 判斷棧是否為空。如果?？眨祷豻rue，否則返回false */if( S.top = 0 ) ret

5、urn true;else return false;結(jié)論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時需要移動的問題，但棧容量難以擴充的弱點仍就沒有擺脫。3.1.3 棧的鏈式存儲及其基本運算的實現(xiàn) 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。人們將用鏈式存儲結(jié)構(gòu)表示的棧稱作鏈棧。鏈棧通常用一個無頭結(jié)點的單鏈表表示。如圖示：11966nulltopbottom結(jié)點類型定義：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）進棧void Push(LinkStack *top, int x) /* 將元素x壓入到棧S中，先申請結(jié)點再將其入棧 */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下面我們給出解決這個問題的完整算法。typedef char Elemtype;void ReverseRead( ) Stack S; /定義一個棧結(jié)構(gòu)Schar ch; InitStack(&S); /初始化棧while (ch=getchar()!=n) /從鍵盤輸入字符，直到輸入換行符為止Push(&S ,ch); /將輸入的每個字符入棧while (!StackEmpty(S) /依次退棧并輸出退出的字符Pop(&S,&ch);putchar(ch);putchar(n);例34： 十進制數(shù)值轉(zhuǎn)換成二進制 使用展轉(zhuǎn)相除法將一個十進制數(shù)值轉(zhuǎn)換成二進制數(shù)值。即用該十進制數(shù)值除以2，

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

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

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

13、時，分別檢測匹配情況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 隊列3.2.1 隊列的定義插入端和刪除端都是浮動的。通常我們將插入端稱為隊尾，用一個隊尾指針指示；而刪除端被稱為隊頭，用一個隊頭指針指示。結(jié)論：先進先出（First In First Out），簡稱為FIFO線性表。例3-6：到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。例3-7：乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順序上車。例3-8：在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個應(yīng)用程序響應(yīng)一系列的消息，像用戶點擊鼠標； 拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此

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

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

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

18、 /隊頭指針、隊尾指針QUEUE;各項基本操作算法。（1）初始化隊列Q void InitQueue(QUEUE *Q)Q-front=-1;Q-rear=-1;（2）入隊 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）出隊 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）獲取隊頭元素內(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）判斷隊列Q是否為空 int QueueEmpty(Queue Q)if (Q.front=Q.rear) return TRUE;else return FALSE; 3.2.3 隊列的鏈式存儲結(jié)構(gòu)及其基本運算的

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

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