數(shù)據(jù)結(jié)構(gòu)與算法分析lecture4(棧)(已修改)
2024-10-31 19:46 本頁面
【正文】 2021825 Lecture notes 1 Stacks(棧 ) ?棧是只允許在同一端進(jìn)行插入和刪除運(yùn)算的線性表。允許插入和刪除的那一端稱為棧頂，另一端為棧底。若有棧 ? S = (s0,s1,……s n1) ?則 s0為棧底結(jié)點(diǎn)， sn1為棧頂結(jié)點(diǎn)。 ?棧的結(jié)點(diǎn)插入為進(jìn)棧 ?棧的結(jié)點(diǎn)刪除為出棧 ?棧具有后進(jìn)先出 (LIFO)的特性 S0 S1 …. Sn1 進(jìn)棧 出棧 棧頂 棧底 2021825 Lecture notes 2 0 1 MAXN1 top 0 1 MAXN1 top (a) 棧結(jié)構(gòu)示意圖 (b) ?？? (c) 棧滿 2021825 Lecture notes 3 ArrayBased Stacks(順序棧 ) ? 可以用順序存儲線性表來表示棧，為了指明當(dāng)前執(zhí)行插入和刪除運(yùn)算的棧頂位置，需要一個(gè)游標(biāo)變量top(習(xí)慣稱為棧頂指針 )， top指出棧頂表元在數(shù)組中的下標(biāo)。 始終指向待插入元素的位置。 ? top是下一次進(jìn)棧時(shí)，進(jìn)棧表元要存入的數(shù)組元素下標(biāo)。當(dāng)棧為空時(shí)， top=0；棧滿時(shí)， top=MAXN（數(shù)組元素個(gè)數(shù)）， 如圖 中的 (b)和(c)。 a2 a1 top 2021825 Lecture notes 4 ?進(jìn)棧 : ?首先把進(jìn)棧表元存入以 top為下標(biāo)的數(shù)組元素中，然后 top加 1，使 top變?yōu)橄乱淮芜M(jìn)棧表元在數(shù)組中的下標(biāo)。 ?出棧 : ?首先執(zhí)行 top減 1，然后把以 top為下標(biāo)的棧頂表元送到接受出棧表元的變量中。同樣限制在?？諘r(shí)，不能再出棧；在棧滿時(shí)，不能再入棧。 2021825 Lecture notes 5 Arraybased stack class implementation(順序棧類的實(shí)現(xiàn) ) ? //Arraybased stack class implementation ? Template class Elem class AStack:public StackElem ? { ? private: ? int size。//Maximum size of stack ? int top。//Index for top element ? //Array holding stack elements ? Elem *listArray。 表示棧中的第一個(gè)空閑位置 2021825 Lecture notes 6 ? public: ? AStack(int sz=DefaultListSize) ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1