棧的定義及順序存儲

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

2、6一一一一. .棧的定義棧的定義棧棧是一種限制僅在一端進行插入和刪除的線性表棧頂棧頂進行插入、刪除棧頂top棧底bottoma2a1an出棧 進棧n-1107一一一一. .棧的定義棧的定義先進后出先進后出(FILO)(FILO)后進先出后進先出(LIFO)(LIFO)1. 若進棧序列為1,2,3,4,進棧過程中可以出棧，則不可能是一個出棧序列（ ）。A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4特點特點【隨堂練習隨堂練習】C8一一二二. .棧的存儲棧的存儲 思考：思考：線性表的存儲方式？ 棧的存儲：棧的存儲：鏈棧順序棧9(1)(1)順序棧類定義（順序棧類

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

4、思想一一二二. .棧的存儲棧的存儲0M-1Top0Top1可能浪費鏈式存儲FlashFlash演示演示12一一三三. .棧的應用棧的應用【解決任務解決任務】(14)10=( ？ )2進制轉(zhuǎn)換進制轉(zhuǎn)換算法思想：算法思想：當N0時，重復（1），（2）(1) (1) 若若Num0Num0，則將，則將Num%RNum%R壓入棧壓入棧s s中，執(zhí)行中，執(zhí)行(2)(2)； 若若Num=0Num=0，將棧，將棧s s的內(nèi)容依次出棧，算法結束。的內(nèi)容依次出棧，算法結束。(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“進制是:”;Multibaseoutput(num,R);Coutendl;14一一【作業(yè)布置作業(yè)布置】數(shù)制轉(zhuǎn)換括號匹配的檢驗行編輯程序1.請用C/C+寫出進制轉(zhuǎn)換算法，并運行十進制數(shù)1348的八進制，截屏保存?！菊n外擴充課外擴充】棧的應用棧的應用迷宮問題表達式求值遞歸