第三章棧和隊(duì)列

1、1第三章 棧和隊(duì)列23.1 棧的類型定義棧的類型定義3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 棧類型的實(shí)現(xiàn)棧類型的實(shí)現(xiàn)3.4 隊(duì)列的類型定義隊(duì)列的類型定義3.5 隊(duì)列類型的實(shí)現(xiàn)隊(duì)列類型的實(shí)現(xiàn)3通常稱，棧和隊(duì)列是限定插入和刪除插入和刪除只能只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。 線性表線性表 棧棧 隊(duì)列隊(duì)列ListInsert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1ListDelete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類型棧和隊(duì)列是兩種常用的數(shù)據(jù)類型43.1 棧的類型定義棧的類

2、型定義 ADT Stack 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT Stack5InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()6 InitStack(&

3、amp;S) 操作結(jié)果：構(gòu)造一個(gè)空棧 S。 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。7 StackEmpty(S)初始條件：棧 S 已存在。操作結(jié)果：若棧 S 為空棧，則返回 TRUE，否則 FALE。8 StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回 S 的元素個(gè)數(shù)，即棧的長度。9 GetTop(S, &e)初始條件：棧 S 已存在且非空。操作結(jié)果：用e返回 S 的棧頂元素。a1a2an 10 ClearStack(&S)初始條件：棧 S 已存在。操作結(jié)果：將 S 清為空棧。11 Push(&

4、;S, e)初始條件：棧 S 已存在。操作結(jié)果：插入元素 e 為新的棧頂元素。a1a2ane 12 Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。a1a2anan-1 133.2 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)例三、例三、 行編輯程序問題行編輯程序問題例四、例四、 表達(dá)式求值表達(dá)式求值例五、例五、 實(shí)現(xiàn)遞歸實(shí)現(xiàn)遞歸14 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 15例如：例如：（1348)10

5、= (2504)8 ，其運(yùn)算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序計(jì)算順序輸出順序輸出順序16void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion17例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)則 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。假設(shè)在表達(dá)式中 （）或（

6、）等為正確的格式。例如：考慮下列括號(hào)序列：例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 818分析可能出現(xiàn)的不匹配不匹配的情況:v到來的右括弧非是所“期待”的;v到來的是“不速之客”;v直到結(jié)束，也沒有到來所“期待”的括弧;（ ）或 ( ) 或 （ ）均為不正確的格式。19算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧；2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若?？諚？?，則表明該“右括弧右括弧”多余多余 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出棧” 否則表明不匹配不匹配3）表達(dá)式表達(dá)式檢驗(yàn)結(jié)束時(shí)結(jié)束時(shí)， 若?？諚？眨瑒t表明表達(dá)

7、式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余20Status matching(string& exp) int state = 1; while (i= S.stacksize) /棧滿 return OVERFLOW; *S.top+ = e; return OK;47Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用 e 返回其值，并返回OK； / 否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;48棧

8、頂指針鏈棧鏈棧a1an注意注意: 鏈棧中鏈棧中指針的方向指針的方向an-1棧底元素棧底元素49 習(xí)習(xí) 題題設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下有問題：（1）若入棧出棧次序?yàn)閜ush(1)，pop( )，push(2)，push(3)，pop( )，pop( )，push(4)，pop( )，則出棧的數(shù)字序列為什么？（2）請(qǐng)分析1、2、3、4的24種排列中，哪些序列可以通過相應(yīng)的入出棧得到。50 ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1

9、, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭隊(duì)列頭， an 端為隊(duì)列尾隊(duì)列尾基本操作：基本操作：3.4 隊(duì)列的類型定義隊(duì)列的類型定義 ADT Queue51隊(duì)列的基本操作：隊(duì)列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)52InitQueue(&Q) 操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q

10、) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：隊(duì)列Q被銷毀， 不再存在。53QueueEmpty(Q) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊(duì)列，則 返回TRUE，否則 返回FALSE。54 QueueLength(Q) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。55 GetHead(Q, &e) 初始條件：初始條件：Q為非空隊(duì)列。 操作結(jié)果：操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an 56 DeQueue(&Q, &e) 初始條件：初始條件：Q為非空隊(duì)列。 操作結(jié)果：操作結(jié)果：刪

11、除Q的隊(duì)頭元素，并用e返回其值。a1a2an 57 EnQueue(&Q, e) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。a1a2ane 58 ClearQueue(&Q) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊(duì)列。593.5 隊(duì)列類型的實(shí)現(xiàn)隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列鏈隊(duì)列鏈?zhǔn)接诚笱h(huán)隊(duì)列循環(huán)隊(duì)列順序映象60 typedef struct QNode / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊(duì)列鏈隊(duì)列鏈?zhǔn)接诚?1type

12、def struct / 鏈隊(duì)列類型鏈隊(duì)列類型 QueuePtr front; / 隊(duì)頭指針隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針隊(duì)尾指針 LinkQueue;a1anQ.frontQ.frontQ.rear空隊(duì)列空隊(duì)列Q.rear隊(duì)頭元素隊(duì)頭元素62 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /存儲(chǔ)分配失敗 Q.front-next = NULL; return OK;63 Status EnQueue (

13、LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;Q.frontQ.rearepa1an64 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rea

14、r) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; delete (p); return OK;if (Q.rear = p) Q.rear = Q.front;65Q.frontQ.reara1注意：出隊(duì)列操作的特殊情況注意：出隊(duì)列操作的特殊情況if (Q.rear = p) Q.rear = Q.front;66#define MAXQSIZE 100 /最大隊(duì)列長度typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， /

15、指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 int queuesize; SqQueue;循環(huán)隊(duì)列循環(huán)隊(duì)列順序映象67注意：順序隊(duì)列的幾種情況：注意：順序隊(duì)列的幾種情況：abcQ.frontQ.rear1、一般情況：、一般情況：100Q.frontQ.rear02、初始化：、初始化：68abcQ.frontQ.rearabQ.front注意：順序隊(duì)列的幾種情況：注意：順序隊(duì)列的幾種情況：3、特殊情況：、特殊情況：cQ.reardQ.rearQ.frontdQ.rearQ.rear69Q.front=Q.rear 隊(duì)滿還是隊(duì)空隊(duì)滿還是隊(duì)空?約定

16、約定: 少用一個(gè)元素空間，以“隊(duì)列頭指針在隊(duì)列尾指針的下一位置上”作為隊(duì)列呈“滿”狀態(tài)的表示。70Q.front=Q.rear 隊(duì)滿還是隊(duì)空隊(duì)滿還是隊(duì)空?Q.frontQ.rearv隊(duì)列空：隊(duì)列空：Q.front=Q.rearQ.frontQ.rearabcd efgv隊(duì)列滿：隊(duì)列滿：（Q.rear +1）% maxsize = Q.front71(a) 空隊(duì) (b)非空隊(duì) (c)滿隊(duì) 循環(huán)隊(duì)列示意圖72 Status InitQueue (SqQueue &Q, int maxsize) / 構(gòu)造一個(gè)最大存儲(chǔ)空間為 maxsize 的 / 空循環(huán)隊(duì)列 Q Q.base = new E

17、lemTypemaxsize; if (!Q.base) exit (OVERFLOW); Q.queuesize = maxsize; Q.front = Q.rear = 0; return OK; 73Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e為Q的新的隊(duì)尾元素 if (Q.rear+1) % Q.queuesize = Q.front) return ERROR; /隊(duì)列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % Q.queuesize; return OK;74 Status DeQueue (SqQueue &Q, ElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % Q.queuesize