本章主要內(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 棧棧的定義棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。如下所示：結(jié)論： 后進(jìn)先出（ Last In First Out），簡(jiǎn)稱為L(zhǎng)IFO 線性表。例 3 1：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)地落在一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。例 3 2：在建筑工地上，

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)棧的順序存儲(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 elements

3、MAXSIZE;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+;elseprintf( "棧上溢！ n" );（3）出棧int Pop( Stack *S ) /*將棧 S 中的棧頂元素

4、出棧*/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( "?？眨?n" );return ERROR;（5）判斷棧 S 是否為空bool I

5、sEmpty( Stack S) /*判斷棧是否為空。如果?？眨祷豻rue，否則返回false */if( S.top = 0 ) return true;else return false;結(jié)論： 由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時(shí)需要移動(dòng)的問題，但棧容量難以擴(kuò)充的弱點(diǎn)仍就沒有擺脫。棧的鏈?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)的單鏈表表示。如圖示：topbottom11966nul

6、l結(jié)點(diǎn)類型定義：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 ) return true;else return false;（3）進(jìn)棧void Push(LinkStack *top, int

7、 x)/* 將元素 x 壓入到棧 S 中，先申請(qǐng)結(jié)點(diǎn)再將其入棧*/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 ) )/* 如果棧非空，則返回棧頂元素，并使棧頂指針減1 */S = *top;*top = (*top)->next;data = S->da

8、ta;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 EmptyLinkStack( LinkStack *top ) /* 清空堆棧 S，使其棧頂指針為 0 */ LinkStack *S;whi

9、le( *top != NULL )S = (*top)->next;free( *top );*top = S;棧的應(yīng)用舉例例 3-3:將從鍵盤輸入的字符序列逆置輸出比如，從鍵盤上輸入：tset a si sihT；算法將輸出：This is a test下面我們給出解決這個(gè)問題的完整算法。typedef char Elemtype;void ReverseRead( )Stack S; /定義一個(gè)棧結(jié)構(gòu)Schar ch;InitStack(&S); /初始化棧while (ch=getchar()!='n') /從鍵盤輸入字符，直到輸入換行符為止Push(&a

10、mp;S ,ch); /將輸入的每個(gè)字符入棧while (!StackEmpty(S) /依次退棧并輸出退出的字符Pop(&S,&ch);putchar(ch);putchar('n');例 3 4： 十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制使用展轉(zhuǎn)相除法將一個(gè)十進(jìn)制數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)； 重復(fù)此操作， 直到該十進(jìn)制數(shù)值為0 為止。最后將所有的余數(shù)反向輸出就是所對(duì)應(yīng)的二進(jìn)制數(shù)值。比如： (692)10 = (1010110100)2，其展轉(zhuǎn)相除的過程如圖所示：下面給出解決這個(gè)問題的完整算法。void Decimal _ Binary ( )S

11、TACK S; /定義棧結(jié)構(gòu)SInitStack(&S); /初始化棧 Sscanf("%d",data); /輸入十進(jìn)制正整數(shù)while (data) Push(&S,data%2); /data/=2; /被除數(shù)余數(shù)入棧data 整除以2，得到新的被除數(shù)while (!StackEmpty(S) / 依次從棧中彈出每一個(gè)余數(shù)，并輸出之 Pop(&S,&data);printf("%d",data);例 3 5： 檢驗(yàn)表達(dá)式中的括號(hào)匹配情況假設(shè)在一個(gè)算術(shù)表達(dá)式中，可以包含三種括號(hào)：圓括號(hào)" （"和&q

12、uot; ）"，方括號(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)時(shí)，棧已空，說明到目前為止，

13、右括號(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= ''): P

14、ush(&S,ch);break; /遇左括號(hào)入棧/ 在遇到右括號(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);if (ch!= '') return FALSE; break;case (ch= &

15、#39;'): 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 隊(duì)列隊(duì)列的定義插入端和刪除端都是浮動(dòng)的。通常我們將插入端稱為隊(duì)尾，用一個(gè) " 隊(duì)尾指針 " 指示；而刪除端被稱為隊(duì)頭，用一個(gè) " 隊(duì)頭指針 " 指示。結(jié)論： 先進(jìn)先出（ First In Firs

16、t Out），簡(jiǎn)稱為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ā)送消息。為此，系統(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

17、,elem)（ 3）出隊(duì) DeQueue(Q,elem)（ 4）獲取隊(duì)頭元素內(nèi)容 GetFront(Q,elem)（ 5）判斷隊(duì)列是否為空 QueueEmpty(Q)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：012n-2n-1a 1a 2a 3an-1a n問題 1 ：當(dāng)隊(duì)列空時(shí)，對(duì)頭和隊(duì)尾指針都為1，隊(duì)列將變成下圖所示狀態(tài)：012n-2n-1問題 2 ：假溢出，即，在添加數(shù)據(jù)時(shí)，可能出現(xiàn)沒有剩余空間而實(shí)際隊(duì)列又不滿的狀況。如：01234567a5a 6a 7a 8frontrear解決辦法：將存儲(chǔ)隊(duì)列元素的一維數(shù)組首尾相接形成一個(gè)環(huán)狀，即循環(huán)隊(duì)列，如下圖：76rear

18、a7a805a6a51423front假設(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 為 MAXQUEUE-時(shí)1，上述兩個(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ì)列是&quo

19、t; 空 " 還是 " 滿" ；二是當(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; /QUEUE;隊(duì)頭指針、隊(duì)尾指針各項(xiàng)基本操作算法。（1）初始化隊(duì)列Qvoid InitQueue(QUEUE *Q)Q->front=-1;

20、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 empty.");else Q->front=(Q->fr

21、ont+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;隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)在用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)隊(duì)列時(shí)，需

22、要設(shè)置隊(duì)頭指針和隊(duì)尾指針，以便指示隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)。q.frontq.reara0a1a2an-1 鏈?zhǔn)酱鎯?chǔ)的隊(duì)列的一般形式結(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; /*LinkQueue *rear; /* Queue;*/隊(duì)列的隊(duì)首指針隊(duì)列的隊(duì)尾指針*/*/基本運(yùn)算：（ 1） 初始化void InitQueue( Queue *Q ) /*初始化隊(duì)列，生成一個(gè)帶哨兵的空隊(duì)列 */ Q-&

23、gt;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->r

24、ear->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;