本章主要內(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é)時，上機(jī) 2學(xué)時重點、難點： 棧的存儲結(jié)構(gòu)及其基本操作、隊列存儲結(jié)構(gòu)及其基本操作§3.1 棧3.1.1 棧的定義 棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所 示：結(jié)論： 后進(jìn)先出( Last In First Out )，簡稱為 LIFO 線性表。例 3 1：家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，一定最 先拿走最上面的那只碗，而最后拿出最下面的那只碗。例 3

2、 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 struc

3、t /* 棧類定義 */int elementsMAXSIZE;int 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+;else printf( " 棧上溢！ n" )

4、;(3) 出棧int Pop( Stack *S ) /* 將棧 S 中的棧頂元素出棧 */if( !IsEmpty( *S ) ) /* 如果棧非空，則返回棧頂元素，并使棧頂指針減 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(

5、 " ?？眨?n" ); return ERROR;(5) 判斷棧 S 是否為空 bool IsEmpty( Stack S) /* 判斷棧是否為空。如果棧空，返回 true ，否則返回 false */if( S.top = 0 ) return true; else return false;結(jié)論： 由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元 素時需要移動的問題，但棧容量難以擴(kuò)充的弱點仍就沒有擺脫。人們將用3.1.3 棧的鏈?zhǔn)酱鎯捌浠具\算的實現(xiàn) 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目， 就應(yīng)該考慮使用鏈?zhǔn)酱鎯Y(jié)

6、構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)表示的棧稱作 "鏈棧 " 。鏈棧通常用一個無頭結(jié)點的單鏈表表示。如圖示：bottom結(jié)點類型定義：t ypedef struct node /* 棧類定義 */int data;struct node *next; LinkStack;(1) 初始化void InitLinkStack( LinkStack *top ) /* 初始化棧，將棧置空 */ *top = NULL;2) 判斷是否為空bool IsEmpty( LinkStack *top) /* 判斷棧是否為空。如果棧空，返回true ，否則返回 false */if( top = NULL )

7、 return true;else return false;3) 進(jìn)棧void Push(LinkStack *top, int x) /* 將元素 x 壓入到棧 S 中，先申請結(jié)點再將其入棧 */LinkStack *S;S = (LinkStack *)malloc( sizeof(LinkStack) );S->data = x;S->next = *top;*top = S;4) 出棧int Pop( LinkStack *top ) /* 將棧 S 中的棧頂元素出棧 */LinkStack *S;int data;if( !IsEmpty( *top ) ) /* 如果

8、棧非空，則返回棧頂元素，并使棧頂指針減1 */S = *top;*top = (*top)->next;data = S->data;free( S );return data;elseprintf( " 棧下溢！ n" );return ERROR;(5) 取棧頂元素int GetTop( LinkStack *top ) /* 獲取棧頂元素，但不改變棧頂指針 */if( !IsEmpty( top ) )return top->data;elseprintf( " ?？眨?n" );return ERROR;(6) 清空void E

9、mptyLinkStack( 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 test 下面我們給出解決這個問題的完整算法。typedef char Elemtype;void ReverseRead( )Stack S; / 定義一個棧結(jié)構(gòu) Schar ch

10、;InitStack(&S); /初始化棧while (ch=getchar()!='n') / 從鍵盤輸入字符，直到輸入換行符為止Push(&S ,ch); / 將輸入的每個字符入棧while (!StackEmpty(S) / 依次退棧并輸出退出的字符Pop(&S,&ch);putchar(ch);putchar('n');例 3 4： 十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制使用展轉(zhuǎn)相除法將一個十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)； 重復(fù)此操作， 直到該十進(jìn)制數(shù)值為 0 為止。 最后將所有的余數(shù)反向輸出就是所對應(yīng)的

11、二進(jìn)制數(shù)值。 比如： (692)10 = (1010110100)2 ，其展轉(zhuǎn)相除的過程如圖所示：下面給出解決這個問題的完整算法。void Decimal _ Binary ( )STACK S; / 定義棧結(jié)構(gòu) SInitStack(&S); / 初始化棧 S scanf("%d",data); / 輸入十進(jìn)制正整數(shù) while (data) Push(&S,data%2); / 余數(shù)入棧data/=2; / 被除數(shù) data 整除以 2 ，得到新的被除數(shù)while (!StackEmpty(S) /依次從棧中彈出每一個余數(shù)，并輸出之Pop(&S,

12、&data); printf("%d",data); 例 3 5： 檢驗表達(dá)式中的括號匹配情況假設(shè)在一個算術(shù)表達(dá)式中，可以包含三種括號：圓括號" ("和" )" ，方括號 "" 和"" 和花括號 "" 和"" ，并且這三種括號可以按任意的次序嵌套使用。 比如，.(.).?，F(xiàn)在需要設(shè)計一個算法，用來檢驗在輸入的算術(shù)表達(dá)式中所使用括號的合法性。算術(shù)表達(dá)式中各種括號的使用規(guī)則為：出現(xiàn)左括號，必有相應(yīng)的右括號與之匹配，并且每對括號之間可以 嵌套，但不能出現(xiàn)

13、交叉情況。我們可以利用一個棧結(jié)構(gòu)保存每個出現(xiàn)的左括號，當(dāng)遇到右括號時，從棧中 彈出左括號，檢驗匹配情況。在檢驗過程中，若遇到以下幾種情況之一，就可以得出括號不匹配的結(jié)論。(1) 當(dāng)遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號；(2) 從棧中彈出的左括號與當(dāng)前檢驗的右括號類型不同，說明出現(xiàn)了括號交叉情況；(3) 算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。 下面是解決這個問題的完整算法。typedef char Elemtype;int Check( )STACK S; / 定義棧結(jié)構(gòu) Schar ch;InitStack(&S); /初始化棧

14、Swhile (ch=getchar()!='n') /以字符序列的形式輸入表達(dá)式switch (ch) case (ch='('|ch= ''|ch= ''): Push(&S,ch);break; /遇左括號入棧/ 在遇到右括號時，分別檢測匹配情況case (ch= ')'): if (StackEmpty(S) retrun FALSE;else Pop(&S,&ch);if (ch!= '(') return FALSE; break;case (ch= '&

15、#39;): 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:break;if (StackEmpty(S) return TRUE;else return FALSE;§3.2 隊列3.

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

17、統(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：當(dāng)隊列空時，對頭和隊尾指針都為1，隊列將變成下圖所示

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

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

20、ront,rear; /隊頭指針、隊尾指針假設(shè)當(dāng)數(shù)組只剩下一個單元時認(rèn)為隊滿存放隊列中數(shù)據(jù)元素的存儲單元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

21、; (3) 出隊void DeQueue(QUEUE*Q,Elemtype *elem) if (QueueEmpty(*Q) exit("Queue is empty."); 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)

22、%MAX_QUEUE; (5) 判斷隊列 Q是否為空int QueueEmpty(Queue Q)if (Q.front=Q.rear) return TRUE;else return FALSE;3.2.3 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)在用鏈?zhǔn)浇Y(jié)構(gòu)存儲隊列時，需要設(shè)置隊頭指針和隊尾指針，以便指示隊頭結(jié)點和隊尾結(jié)點鏈?zhǔn)酱鎯Φ年犃械囊话阈问?結(jié)點結(jié)構(gòu)定義如下： typedef struct node /* 隊列結(jié)點類型定義 */int data; struct node *next; LinkQueue;typedef struct /* 隊列頭結(jié)點類型定義 */LinkQueue *f

23、ront; /*隊列的隊首指針 */LinkQueue *rear; /*隊列的隊尾指針 */ Queue;基本運算：(1 ) 初始化void InitQueue( Queue *Q ) /* 初始化隊列，生成一個帶哨兵的空隊列 */Q->front = (LinkQueue *)malloc( sizeof(LinkQueue) );Q->front->next = NULL;Q->rear = Q->front;(2 ) 判空bool IsEmpty( Queue Q) /* 判斷隊列是否為空。如果隊列為空，返回 true ，否則返回 false */if(

24、Q.front = Q.rear ) return true;else return false;(3 ) 進(jìn)隊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;/* 當(dāng)將隊列中的一個元