棧的定義及順序存儲(chǔ)

1、棧的定義、順序存儲(chǔ)棧的定義、順序存儲(chǔ)第七節(jié)段第七節(jié)段數(shù)據(jù)結(jié)構(gòu)1一一【創(chuàng)設(shè)情境創(chuàng)設(shè)情境】 壓入子彈，射出子彈的特點(diǎn)？ 羽毛球筒取放羽毛球特點(diǎn)？2一一【引入新課引入新課】操作受限：只可在一端進(jìn)行；最后放進(jìn)去的子彈最先射出來(lái)。棧棧3進(jìn)制轉(zhuǎn)化問(wèn)題進(jìn)制轉(zhuǎn)化問(wèn)題(14)10=( ？ )21110一一【任務(wù)驅(qū)動(dòng)、學(xué)習(xí)知識(shí)任務(wù)驅(qū)動(dòng)、學(xué)習(xí)知識(shí)】思考思考：1.轉(zhuǎn)化方法？2.數(shù)據(jù)存儲(chǔ)、輸出實(shí)現(xiàn)？41 12 23 3棧的棧的定義定義棧的棧的存儲(chǔ)存儲(chǔ)棧的應(yīng)用棧的應(yīng)用目目 錄錄5一一一一. .棧的定義棧的定義思考思考：1.進(jìn)棧、出棧相當(dāng)于順序表？2.時(shí)間復(fù)雜度？(1)回答：回答：順序表表尾操作FlashFlash演示演示

2、6一一一一. .棧的定義棧的定義棧棧是一種限制僅在一端進(jìn)行插入和刪除的線性表?xiàng)ｍ敆ｍ斶M(jìn)行插入、刪除棧頂top棧底bottoma2a1an出棧 進(jìn)棧n-1107一一一一. .棧的定義棧的定義先進(jìn)后出先進(jìn)后出(FILO)(FILO)后進(jìn)先出后進(jìn)先出(LIFO)(LIFO)1. 若進(jìn)棧序列為1,2,3,4,進(jìn)棧過(guò)程中可以出棧，則不可能是一個(gè)出棧序列（ ）。A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4特點(diǎn)特點(diǎn)【隨堂練習(xí)隨堂練習(xí)】C8一一二二. .棧的存儲(chǔ)棧的存儲(chǔ) 思考：思考：線性表的存儲(chǔ)方式？ 棧的存儲(chǔ)：棧的存儲(chǔ)：鏈棧順序棧9(1)(1)順序棧類(lèi)定義（順序棧類(lèi)

3、定義（p41p41）：）： privateprivate： int stacklistMaxStackSize;int stacklistMaxStackSize; int top; int top; public public： 各種運(yùn)算的成員函數(shù)各種運(yùn)算的成員函數(shù)；討論討論1 1：1.哪些運(yùn)算？一一二二. .棧的存儲(chǔ)棧的存儲(chǔ)10?？諘r(shí)棧滿時(shí)棧頂元素?？諘r(shí)，執(zhí)行pop棧滿時(shí)，執(zhí)行push一一二二. .棧的存儲(chǔ)棧的存儲(chǔ)【順序棧順序棧】討論討論2 2：top=-1top=MaxStackSize-1Stop產(chǎn)生“下溢”產(chǎn)生“上溢”如何解決？如何解決？11定義足夠大空間的順序?！肮蚕砉蚕?xiàng)！彼枷?/p>

4、思想一一二二. .棧的存儲(chǔ)棧的存儲(chǔ)0M-1Top0Top1可能浪費(fèi)鏈?zhǔn)酱鎯?chǔ)FlashFlash演示演示12一一三三. .棧的應(yīng)用棧的應(yīng)用【解決任務(wù)解決任務(wù)】(14)10=( ？ )2進(jìn)制轉(zhuǎn)換進(jìn)制轉(zhuǎn)換算法思想：算法思想：當(dāng)N0時(shí)，重復(fù)（1），（2）(1) (1) 若若Num0Num0，則將，則將Num%RNum%R壓入棧壓入棧s s中，執(zhí)行中，執(zhí)行(2)(2)； 若若Num=0Num=0，將棧，將棧s s的內(nèi)容依次出棧，算法結(jié)束。的內(nèi)容依次出棧，算法結(jié)束。(2) (2) 用用Num/RNum/R代替代替NumNum。 13#include “seqstack.h”Void Multibaseou

5、tput(long num,int R) Seqstack s; do s.push(num%R); num/=R; while(num!=0); while(!s. StackEmpty() couts.Pop(); /主函數(shù)主函數(shù)Void main() long num; int R;coutnumR;coutnum“的”R“進(jìn)制是:”;Multibaseoutput(num,R);Coutendl;14一一【作業(yè)布置作業(yè)布置】數(shù)制轉(zhuǎn)換括號(hào)匹配的檢驗(yàn)行編輯程序1.請(qǐng)用C/C+寫(xiě)出進(jìn)制轉(zhuǎn)換算法，并運(yùn)行十進(jìn)制數(shù)1348的八進(jìn)制，截屏保存?！菊n外擴(kuò)充課外擴(kuò)充】棧的應(yīng)用棧的應(yīng)用迷宮問(wèn)題表達(dá)式求值遞歸