數(shù)據(jù)結(jié)構(gòu)第3章堆 棧和 隊(duì)列.ppt

《數(shù)據(jù)結(jié)構(gòu)第3章堆 棧和 隊(duì)列.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、引言堆棧和隊(duì)列也是最常見的數(shù)據(jù)結(jié)構(gòu)，在算法設(shè)計(jì)中經(jīng)常使用。堆棧和隊(duì)列在邏輯上同線性表一樣，都是線性結(jié)構(gòu)，差別在于：線性表可以在表的任意位置插入和刪除元素，而堆棧和隊(duì)列只能在表的端點(diǎn)插入和刪除元素。第3章堆棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE內(nèi)容提要1.定義堆棧與隊(duì)列抽象數(shù)據(jù)類型2.討論堆棧與隊(duì)列的順序表示方法3.討論堆棧與隊(duì)列的鏈接表示方法4.以表達(dá)式計(jì)算為例討論堆棧的應(yīng)用3.1堆棧a0a1…ai…an-1入棧出棧bottomtop圖3-1棧的示意圖棧的示意圖S=(a0,a1,…,an-1)課堂提要第3章堆棧和隊(duì)列3.1堆棧3.2隊(duì)列3.3表達(dá)式的計(jì)算3.1.1

2、堆棧抽象數(shù)據(jù)類型堆棧（簡(jiǎn)稱棧）是限定插入和刪除操作都在表的一端進(jìn)行的線性表。若棧中無元素，則為空棧。允許插入和刪除元素的一端稱為棧頂，另一端稱為棧底。S=(a0,a1,…,an-1)1.堆棧的定義課堂提要第3章堆棧和隊(duì)列3.1堆棧3.1.1棧抽象數(shù)據(jù)類型3.1.2棧的順序表示3.1.3棧的鏈接表示3.2隊(duì)列3.3表達(dá)式的計(jì)算若給定棧S=(a0,a1,…,an-1)，則稱a0是棧底元素，an-1是棧頂元素。若元素a0,…,an-1依次進(jìn)棧時(shí)，則出棧的順序與進(jìn)棧相反，即元素an-1必定最先出棧，然后an-2才能出棧。因此，棧是后進(jìn)先出(LastInFirstOut——LI

3、FO)的線性數(shù)據(jù)結(jié)構(gòu)。a0a1…ai…an-1入棧出棧bottomtop圖3-1棧的示意圖2.棧抽象數(shù)據(jù)類型ADTStack{Data:零個(gè)或多個(gè)元素的線性序列（a0,a1,...,an-1),其最大允許長度為ＭaxStackSize。對(duì)于它插入和刪除運(yùn)算都限制在同一端進(jìn)行，并遵循LIFO原則。Operations:Create()：建立一個(gè)空棧。Destroy()：撤消一個(gè)棧。IsEmpty()：若?？眨瑒t返回true;否則返回false。IsFull()：若棧滿，則返回true;否則返回false。Top(x)：返回棧頂元素。若操作成功，則返回true;否則返回f

4、alse。Push(x)：在棧頂插入元素x。Pop()：從棧中刪除棧頂元素。Clear():清除堆棧中全部元素。};3.棧的C++模板抽象類程序3-1棧的C++類templateclassStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1.2棧的順序表示1.棧的順序表示法an-1a1

5、a0topn-110棧s圖3-2順序棧maxTop………課堂提要第3章堆棧和隊(duì)列3.1堆棧3.1.1棧抽象數(shù)據(jù)類型3.1.2棧的順序表示3.1.3棧的鏈接表示3.2隊(duì)列3.3表達(dá)式的計(jì)算2.順序棧類templateclassSeqStack:publicStack{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;b

6、oolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//總是指向棧頂元素intmaxTop;T*s;}an-1a1a0topn-110棧s圖3-2順序棧maxTop………3.動(dòng)態(tài)一維數(shù)組描述順序棧類templateclassSeqStack:publicStack{public:……private:intmaxTop;inttop;T*s;}an-1a1a0topn-110棧s圖3-2順序棧maxTop………構(gòu)造函數(shù)templateSeqStack::SeqSta

7、ck(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析構(gòu)函數(shù)SeqStack::~SeqStack(intMaxSize){delete[]s;}an-1a1a0topn-110棧s圖3-2順序棧maxTop………4.在順序存儲(chǔ)表示下實(shí)現(xiàn)棧上定義的操作（1）取棧頂元素templateboolSeqStack::Top(T&x)const{if(IsEmpty()){cout<<"Empty"<