【正文】 （ stack） ?順序棧進、出棧圖示 top=1 1 2 3 4 5 0 ?？? 棧頂指針 top,指向實際棧頂 后的空位置，初值為 1 top 1 2 3 4 5 0 進棧 A top 出棧 棧滿 B C D E F 設數(shù)組維數(shù)為 M top=1,?？?，此時出棧，則 下溢 （ underflow) top=M1,棧滿，此時入棧，則 上溢 （ overflow) top top top top top 1 2 3 4 5 0 A B C D E F top top top top top top ?？? 106 Status Push(SqStack *S,datatype e){ If(Stop = MAXSIZE1) /*上溢 */ return ERROR。 Stop ++。 Selements[Stop] = e。 return OK。 } 棧 （ stack） ? 進棧算法 107 棧 （ stack） ? 出棧算法 Status Pops (SqStack *S,datatype *e){ If (Stop == 1) /*下溢 */ return ERROR。 Stop 。 *e = Selements[Stop+1]。 return OK。 } 108 二、鏈棧 （單鏈表） 棧 （ stack） typedef struct node { int data。 struct node *link。 }LinkList。 ?結點定義 ^ …... top data link 棧底 棧頂 109 棧 （ stack） ?鏈棧的特點 ?鏈表的存儲結構與鏈接存儲的棧完全相同，只是鏈頭指針就是棧頂指針。 初始時為NULL ? 鏈式棧無棧滿問題，空間可擴充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈式棧的棧頂在鏈頭 ? 適合于多棧操作 110 棧 （ stack） ?鏈棧的進棧算法 進棧等同于不帶頭結點單鏈表的頭插法 Status Push(LinkList * S,datatype e ){ p = (LinkList )malloc(sizeof(Linklist))。 pdata = e。 pnext = Stop。 Stop = p。 return OK。} 111 棧 （ stack） ?鏈棧的出棧算法 出棧等同于刪除第一個結點 Status Pop(LinkList * S,datatype *e ){ If(Stop) return ERROR。/*下溢 */ p = Stop。 Stop = pnext。 *e = pdata。 free(p)。 return OK。 } 112 棧 （ stack） 棧的應用 (1)“ 回溯 ” 問題求解 (2) 過程的嵌套和遞歸調用 113 1．嵌套調用 棧 （ stack） 棧的應用 114 r 主程序 s r 子過程1 r s t 子過程2 r s t 子過程3 s r r 棧 （ stack） ?嵌套調用過程圖示 115 遞歸：函數(shù)直接或間接的調用自身的過程 169。一個對象部分地包含它自己 ， 或是用它自己給自己定義 169。一個過程直接地或間接地調用自己 169。利用前面運算來求得答案的過程 ?實現(xiàn)： 建立遞歸工作棧 ?優(yōu)點： 遞歸函數(shù)結構清晰 ， 程序易讀 ， 正確性易證明 ?缺點： 速度慢 ， 空間大效率低 棧 （ stack） 2．遞歸調用 116 棧 （ stack） void p (參數(shù)表 ) { if （遞歸結束條件） 可直接求解步驟； 基本項 else p（較小的參數(shù)）； 歸納項 } ?遞歸算法的一般形式 117 棧 （ stack） 例：求 n! = 1， n=0 n*(n1)！ n0 int Factorial(int n){ if (n==0) return 1。 return n*Factorial(n1)。 } 118 例 ：遞歸的執(zhí)行情況分析 棧 （ stack） 119 void print(Int w) { int i。 if ( w!=0) { print(w1)。 for(i=1。i=w。++i) printf(“ %3d,” ,w)。 printf(“ /n” )。 } } 棧 （ stack） 運行結果： 1， 2， 2， 3， 3， 3， ? 例 遞歸的執(zhí)行情況分析 120 棧 （ stack） 主程序 (1) print(w) w=3。 3 print(2)。 （ 1） w=3 top (2) 輸出： 3, 3, 3 w 2 print(1)。 （ 2） w=2 （ 1） w=3 top (3) 輸出： 2, 2 w 1 print(0)。 （ 3） w=1 （ 2） w=2 （ 1） w=3 top (4)輸出： 1 w 0 （ 4） w=0 （ 3） w=1 （ 2） w=2 （ 1） w=3 top w (2) 2 (1) 3 輸出：(3) 1 (2) 2 (1) 3 3 (1 ) 3 返回 (3) 1 (2) 2 (1) 3 top (4) 0 結束 ?上例圖示分析 121 括號的匹配檢驗 棧 （ stack） ?假設表達式中有多種擴號，可以用棧來進行擴號匹配檢驗，具體做法為： 非括號字符跳過不理；碰上左擴號，入棧；碰上右擴號，出棧，并且檢查出棧元素是否與當前右擴號相匹配，若匹配繼續(xù)檢查，否則匹配失敗。 請同學們下去自己編程序試試。 122 隊列（ QUEUE） 一、隊列定義 ?隊列是限定只能在表的一端進插入，在表的另一端進行刪除的線性表 ?隊尾 (rear)——允許插入的一端 ?隊頭 (front)——允許刪除的一端 ?隊列特點： 先進先出 (FIFO) 123 隊列（ QUEUE） ?隊列定義 假設隊列 S=(a1， a2， a3， … an)， 則 a1稱為 隊首元素 ， an為 隊尾元素 。 隊中元素按 a1， a2， a3， … an的次序入隊，出隊按先進先出的原則進行的 ,因此 a1，a2， a3， … an的次序出隊 front 和 rear的初始值地隊列初始化時均應置為 1。 124 入隊 時將 rear+1, 新元素插入 elements[front]位置 . 出隊 時，將加 front+1, 刪去元素 隊列（ QUEUE） a1 a2 a3…………………… .an 入隊 出隊 front rear 隊列 Q=(a1,a2,……,an) ?隊列定義 125 a1 a2 a3…………………… .an 端 1 端 2 入隊 出隊 入隊 出隊 隊列（ QUEUE） ?雙端隊列 126 隊列（ QUEUE） ?隊列的主要操作 （ 1）建立一個空隊列 InitQueue(amp。Q) （ 2）進隊 EnQueue(amp。Q,e) （ 3） 出隊 DeQueue(amp。Q,amp。e) （ 4） 判斷一個隊列是否為空 QueueEmpty(Q) （ 5）獲得隊頭元素值 GetHead(Q,amp。e ) 127 隊列（ QUEUE） 二、鏈隊列 ?結點定義 typedef struct node { int data。 struct node *next。 }Qnode,*QueuePtr。 128 front rear x入隊 ^ x front rear y入隊 x ^ y front rear 空隊 ^ 隊列（ QUEUE） ?鏈隊列圖示 129 入隊不用考慮隊滿 ,但出隊要考慮隊空 隊空條件為 front == NULL front rear y出隊 ^ front rear x出隊 x ^ y 隊列（ QUEUE） ?鏈隊列圖示 130 隊列（ QUEUE） ?鏈隊列入隊算法 p = (QueuePtr)malloc(sizeof(Qnode))。 pdata = x。 pnext = NULL。 Qrearnext = p。 Qrear = p。 131 隊列（ QUEUE） ?鏈隊列出隊算法 if(Empty(Q)) return ERROR。 else{ s = Qfrontnext。/*指向被刪結點 */ if(snext == NULL){ QfrontNext = Null。 Qrear = Qfront。} Else Qfrontnext = snext。 *e = sdata。 free(s)。 return OK。} 132 隊列（ QUEUE） front=1 rear=1 1 2 3 4 5 0 隊空 1 2 3 4 5 0 front J1,J1,J3入隊 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入隊 J4 J5 J6 front 設兩個指針 front,rear,約定： rear指示隊尾元素； front指示隊頭元素前一位置 初值 front=rear=1 空隊列條件： front==rear 入隊列： sq[++rear]=x。 出隊列： x=sq[++front]。 rear rear front rear 1 2 3 4 5 0 J1,J2,J3出隊 J1 J2 J3 front front front ? 三、循環(huán)隊列 隊列的順序表示和實現(xiàn) 133 隊列（ QUEUE） ?存在問題 設數(shù)組維數(shù)為 M，則： ?當 front=1,rear=M1時 ， 再有元素入隊發(fā)生溢出 —真溢出 ?當 front 1,rear=M1時 ， 再有元素入隊發(fā)生溢出 —假溢出 解決方案 : ?隊首固定 ， 每次出隊剩余元素向下移動 ——浪費時間 ?循環(huán)隊列 134 ?循環(huán)隊列 基本思想 ： 存儲隊列的數(shù)組被當作首尾相接的表處理 ； 讓 sq[0]接在 sq[M1]之后，若 rear+1==M,則令 rear=0。 隊列（ QUEUE） 187。實現(xiàn)：利用“?！边\算 187。入隊： rear=(rear+1)%M。 sq[rear]=x。 187。出隊： front=(front+1)%M。 x=sq[front]。 187。隊滿、隊空判定條件 0 M1 1 front rear 135 …… rear front maxSize1 入隊 : rear=(rear+1) % MaxSize。 elements[rear]=item 出隊： front=(front+1)%MaxSize。 隊空： rear = front。