第三章棧和隊(duì)列

1、 通常稱，棧和隊(duì)列是限定插入和刪除插入和刪除 只能只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。 線性表線性表 棧棧 隊(duì)列隊(duì)列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 棧和隊(duì)列是兩種常用的數(shù)據(jù)類型棧和隊(duì)列是兩種常用的數(shù)據(jù)類型 3.1 棧棧 一棧的定義及基本操作 1、棧的定義 棧（stack）是一種只允許在一端進(jìn)行插入和刪除的線性表 ，它是一種操作受限的線性表。 在表中只允許進(jìn)行插入和刪除的一端稱為棧頂（top），另 一端稱為棧底(bottom)

2、。當(dāng)棧中無(wú)數(shù)據(jù)元素時(shí)，稱為空棧。 設(shè)棧s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是棧底元素， an是棧頂元素。 棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放的位置。 棧底（bottom):不允許插入和刪除的一端。 2、棧的特點(diǎn)：后進(jìn)先出后進(jìn)先出 a1 a2 . an 進(jìn)棧進(jìn)棧出棧出棧 棧頂棧頂 棧底棧底 例、已知入棧序列為123 則求所有的出棧序列： 123 132 213 231 321 例：入棧序列為123456則能否得到 435612和135426的出棧序列。（s表 示進(jìn)棧，x表示出棧) 435612： 不能得到 135426 :

3、sxssxssxxxsx 可以得到 若進(jìn)棧序列為若進(jìn)棧序列為3，5，7，9，進(jìn)棧過(guò)程中，進(jìn)棧過(guò)程中 可以出棧，則不可能的一個(gè)出棧次序是可以出棧，則不可能的一個(gè)出棧次序是 （ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3 3棧的基本操作棧的基本操作 （1）InitStack(/棧底指針 SElemType *top;/棧頂指針 int stacksize;/棧當(dāng)前可使用的最大容量 )SqStack; a1 a2 a3 S 2 3 1 0 top base s.top=s.top- 1 e=*s.top s.top- s.base=s.s

4、tacksize 棧滿棧滿 a1 a2 a3 a4 S 2 3 1 0 top base S 2 3 1 0 S.top=s.base 空棧空棧 top A1 S 2 3 1 0base *s.top=e S.top=S.top+1 top base 2）順序棧的基本運(yùn)算算法）順序棧的基本運(yùn)算算法 （1）初始化棧 Status InitStack(SqStack If(!s.base)exit(OVERFLOW); s.top=s.base; s.stacksize=STACK-INIT-SIZE； return OK; （2）入棧操作 status Push(SqStack return O

5、K; if(s.top-s.base=s.stacksize) s . b a s e = ( S E l e m T y p e * ) r e a l l o c ( s . b a s e , (s.stacksize+STACKINCREMENT)*sizeof(SElemType); if (!s.base)exit(OVERFLOW): s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; （3）出棧操作 status Pop(SqStack /?？?e=*-s.top; return OK; （4）取棧頂元素操作 statu

6、s Pop(SqStack s,SElemType /?？?e=*(s.top-1); return OK; 取棧頂元素與出棧不同之處在于出棧操作改變 棧頂指針top的位置，而取棧頂元素操作不改變 棧的棧頂指針。 （5）判?？詹僮?int Empty(sqstack s) /棧s為空時(shí)，返回為T(mén)RUE；非空時(shí)，返回 為FALSE if(s.base=s.top) return TRUE; return FALSE; 2、 鏈棧鏈棧 用指針來(lái)實(shí)現(xiàn)的棧叫鏈棧。當(dāng)棧的容量事先用指針來(lái)實(shí)現(xiàn)的棧叫鏈棧。當(dāng)棧的容量事先 不能估計(jì)時(shí)采用這種存儲(chǔ)結(jié)構(gòu)。不能估計(jì)時(shí)采用這種存儲(chǔ)結(jié)構(gòu)。 鏈棧的類型定義如下：鏈棧的類

7、型定義如下： Typedef struct lnode SElemType data； struct lnode next； lnode， Lstack； s 棧頂 棧底 an a1 進(jìn)棧算法進(jìn)棧算法 V o i d p u s h ( L s t a c k p-data=e; p-next=s; s=p; bas e S 棧棧 s 進(jìn)棧元素進(jìn)棧元素e 進(jìn)棧算法進(jìn)棧算法 Void push(Lstack p-data=e; p-next=s; s=p; P bas e S 進(jìn)棧算法進(jìn)棧算法 Void push(Lstack p-data=e; p-next=s; s=p; e P bas e

8、 S 進(jìn)棧算法進(jìn)棧算法 Void push(Lstack p-data=e; p-next=s; s=p; e P bas e S 進(jìn)棧算法進(jìn)棧算法 Void push(Lstack p-data=e; p-next=s; s=p; return (1); e P bas e S 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ， 其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計(jì)算順序計(jì)算順序 輸出順序輸出順序 void

9、conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion 例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 假設(shè)在表達(dá)式中 （）或（ ） 等為正確的格式 則 檢驗(yàn)括號(hào)是否匹配的方法可用 “期待的急迫程度”這個(gè)概念來(lái)描述。 例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8 分析可能出現(xiàn)的不匹配不匹配的情況: 到來(lái)的右括弧不是所“期待”的; 到來(lái)的是“不速之客”; 直到

10、結(jié)束，也沒(méi)有等到所“期待” 的括弧; （ ）或 ( ) 或（ ） 均為不正確的格式。 算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想： 1）凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧； 2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若?？諚？眨瑒t表明該“右括弧右括弧”多余多余 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出棧” 否則表明不匹配不匹配 3）表達(dá)式表達(dá)式檢驗(yàn)結(jié)束時(shí)結(jié)束時(shí)， 若棧空棧空，則表明表達(dá)式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余 Status matching(string while (inext = NULL; return OK; Status EnQueue (

11、LinkQueue if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; a1anQ.front Q.rear e p Status DeQueue (LinkQueue p = Q.front-next; e = p-data; Q.front-next = p-next; free (p); return OK; if (Q.rear = p) Q.rear = Q.front; QueuePtr q q-next=q(隊(duì)空） a1 a2 an

12、q 如果使用帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列 ， 并且只設(shè)一個(gè)指針指向?qū)ξ苍亟Y(jié)點(diǎn)（注意不 設(shè)頭指針），該如何編寫(xiě)相應(yīng)的隊(duì)列初始化， 入隊(duì)列和出隊(duì)列的算法？ 思考？ 3 2 1 0 (a) a1 a2 a3 3 2 1 0 (b) a3 3 2 1 0 (c) q. rear q.front a1、a2出隊(duì)列出隊(duì)列 q.rear=q.front (隊(duì)空）隊(duì)空） q.rear a1、 a2 、a3 入隊(duì)列入隊(duì)列 a3 3 2 1 0 (d) a4 q. rear q.front q.front q.rear q.front 1循環(huán)隊(duì)列的表示循環(huán)隊(duì)列的表示 假溢出假溢出 循環(huán)隊(duì)列循環(huán)隊(duì)列順序映象 2循環(huán)

13、隊(duì)列的隊(duì)空與隊(duì)滿條件循環(huán)隊(duì)列的隊(duì)空與隊(duì)滿條件 為了區(qū)分隊(duì)空與隊(duì)滿的條件： 2)設(shè)計(jì)標(biāo)志位 tag加入到隊(duì)列中 隊(duì)空：q.tag=0 隊(duì)滿：q.tag=1 1）犧牲一個(gè)存儲(chǔ)單元 隊(duì)空：q.front=q.rear 隊(duì)滿(q.rear+1)%MAXQSIZE =q.front #define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 int queuesize; SqQueue; 3、循環(huán)隊(duì)列的主要運(yùn)算算法、循環(huán)隊(duì)列的主要運(yùn)算算法 （1）初始化隊(duì)列 Status IniQueue(SqQueue If (!q.base) exit (OVERFLOW); q.front= q.rear=0; return OK; （2）入隊(duì)列操作 Status EnQuenu(SqQueue /隊(duì)列滿 q.baseq.rear=e; q.rear=(q.rear+1)%MAX