第2章之棧與隊(duì)列(已修改)
2025-10-09 16:23 本頁(yè)面
【正文】 下一頁(yè) 上一頁(yè) 停止放映 第 2章之 棧與隊(duì)列 西安交通大學(xué)計(jì)教中心 下一頁(yè) 上一頁(yè) 停止放映 [第 2頁(yè) /68頁(yè) ] 要點(diǎn) ? 棧和隊(duì)列結(jié)構(gòu)的特點(diǎn) ? 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的特點(diǎn) ? 操作的特點(diǎn) 下一頁(yè) 上一頁(yè) 停止放映 [第 3頁(yè) /68頁(yè) ] 棧的定義 堆棧 (Stack) ? 棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。 ? 允許進(jìn)行插入和刪除操作的一端稱為 棧頂 (top)，另一端為 棧底 (bottom)；棧底固定，而棧頂浮動(dòng)； ? 棧中元素個(gè)數(shù)為零時(shí)稱為空棧。 ? 棧結(jié)構(gòu)也稱為 后進(jìn)先出 表（ LIFO）。 棧示意圖 a1 a3 a2 進(jìn)棧 出棧 top 下一頁(yè) 上一頁(yè) 停止放映 [第 4頁(yè) /68頁(yè) ] 棧有關(guān)概念 棧上溢 ?？臻g是有限的，若棧已滿，在進(jìn)行入棧操作時(shí)，就要產(chǎn)生上溢。 棧下溢 若?？?，再要執(zhí)行出棧操作，則會(huì)發(fā)生下溢。 棧頂指針 在棧操作過(guò)程中，有一個(gè)專(zhuān)門(mén)的棧指針（習(xí)慣上稱它為 TOP），指出棧頂元素所在的位置。 下一頁(yè) 上一頁(yè) 停止放映 [第 5頁(yè) /68頁(yè) ] 棧的順序存儲(chǔ)結(jié)構(gòu) 同順序表一樣 ， 可利用一維數(shù)組來(lái)實(shí)現(xiàn) 。 C++語(yǔ)言定義如下： struct SqStack{ ElemType *data。 //存儲(chǔ)元素的數(shù)組 int top。 //棧頂指針 ， 存儲(chǔ)棧頂元素下標(biāo) int stacksize。 //最大可用空間數(shù)量 }。 SeqStack s。 //定義一個(gè)堆棧 s Top = 1 表示空棧； top = stacksize1 表示棧滿 。 下一頁(yè) 上一頁(yè) 停止放映 [第 6頁(yè) /68頁(yè) ] 棧操作舉例 a1 a2 …… a n 棧底 棧頂 MAXSIZE TOP 1. top=0 A B C 2. (空棧 ) top=3 (A、 B、 C進(jìn)棧 ） A B 3. top=2 (C出棧） 4. A B C D E F top=MAXSIZE (棧滿） 下一頁(yè) 上一頁(yè) 停止放映 [第 7頁(yè) /68頁(yè) ] 例 有三個(gè)元素的進(jìn)棧序列是 1， 2， 3。寫(xiě)出可能的出棧序列 。 出棧序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x 下一頁(yè) 上一頁(yè) 停止放映 [第 8頁(yè) /68頁(yè) ] 棧的基本運(yùn)算 InitStack（ Stack） 置棧為空； Empty（ Stack） 判定棧是否為空； Push（ Stack， x） 進(jìn)棧操作，在棧頂插入元素； Pop（ Stack） 出棧操作，刪除棧頂元素； Gettop（ Stack） 取棧頂元素 下一頁(yè) 上一頁(yè) 停止放映 [第 9頁(yè) /68頁(yè) ] （ 1） 順序棧初始化 棧的初始化主要是為存儲(chǔ)元素的數(shù)組申請(qǐng)空間（ 長(zhǎng)度為 size） 。 void InitStack(SqStack *s, int size) { if( size 0 ) { sstacksize = size。 stop = 1。 sdata = new ElemType[size]。 // 申請(qǐng)空間 } else cout堆棧初始化長(zhǎng)度錯(cuò)誤 。 } 下一頁(yè) 上一頁(yè) 停止放映 [第 10頁(yè) /68頁(yè) ] （ 2） 進(jìn)棧操作 若棧不滿 ， 則在棧頂插入元素 x作為新的棧頂 。 算法步驟 : – step1 判別棧滿否，若滿，則顯示棧溢出信息，停止執(zhí)行；否則，執(zhí)行 step 2； – Step2 棧頂指針 top上移 (加 1)； – Step3 在 top所指的位置插入元素 x。 下一頁(yè) 上一頁(yè) 停止放映 [第 11頁(yè) /68頁(yè) ] 進(jìn)棧程序算法 void Push(SqStack *s, ElemType x) { if(stop sstacksize1) //是否為空 { stop++。 //Top加 1 sdata[top]=x。 //x進(jìn)棧 } else cout“棧滿 ” 。 } 示例 下一頁(yè) 上一頁(yè) 停止放映 [第 12頁(yè) /68頁(yè) ] （ 3） 出棧操作 若棧不空 ， 則刪除 s的棧頂元素 ， 用 e返回其值 。 算法步驟 : – step1 判別棧是否為空；若空，則輸出 棧下溢信息，并停止執(zhí)行；否則， 執(zhí)行 step2； – step2 彈出（刪除）棧頂元素； – step3 棧頂指針 top下移 (減 1)。 下一頁(yè) 上一頁(yè) 停止放映 [第 13頁(yè) /68頁(yè) ] 出棧算法程序 void Pop (SqStack *s, ElemType amp。e) { if(stop 1) { e= sdata[stop]。 stop。 } else cout“?？?? 。 } 示例 下一頁(yè) 上一頁(yè) 停止放映 [第 14頁(yè) /68頁(yè) ] （ 4） 取棧頂元素 若棧不空 ， 則用 e返回 s的棧頂元素 。 void GetTop(SqStack *s, ElemType amp。e) { if(stop 1) //若棧非空 e= sdata[stop]。 //取棧頂元素 else cout“?？?”
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1