棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)教程PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)教程棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)教程第1頁/共22頁是浮動(dòng)端，通常被稱為棧頂，并用一個(gè)“棧頂指針”指示；而另一端是固定端，通常被稱為棧底。我們經(jīng)常將棧用下圖3-1的形式描述：a1, a2, a3, ., an 插入和刪除端插入和刪除端第2頁/共22頁an.a2a1棧頂 top圖圖 3-1第3頁/共22頁輸入項(xiàng)目A,B,C,若輸入的順序是A,B,C，試給出全部的可能的輸出序列。下面我們先給出棧結(jié)構(gòu)的基本操作：（1）初始化棧Init_Stack(S) （2）入棧 Push_Stack(S,x) （3）出棧 Pop_Stack(S) （4）獲取棧頂元素內(nèi)容Top_Stack(S) （5）

2、判斷棧是否為空Empty_Stack (S)第4頁/共22頁dataMAXSIZE; int top; SeqStack定義一個(gè)指向順序棧的指針： SeqStack *s;第5頁/共22頁 int Empty_SeqStack(SeqStack *s) if (s-top= = -1) return 1; else return 0;第6頁/共22頁MAX_STACK-1.10top= -1第7頁/共22頁int Pop_SeqStack(SeqStack *s, datatype *x) if (Empty_SeqStack ( s ) ) return 0; /*?？詹荒艹鰲?*/ els

3、e *x=s-datas-top; s-top-; return 1; /*棧頂元素存入*x，返回*/ 第8頁/共22頁滿時(shí)，不能入棧; 否則出現(xiàn)空間溢出，引起錯(cuò)誤，這種現(xiàn)象稱為上溢。 2. 出棧和讀棧頂元素操作，先判斷棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常?？諘r(shí)常作為一種控制轉(zhuǎn)移的條件。第9頁/共22頁由于棧的插入刪除操作只能在一端進(jìn)行，而對于單鏈表來說，在首端插入刪除結(jié)點(diǎn)要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。第10頁/共22頁top如圖如圖3-3第11頁/共22頁第12頁/共22頁 else return 0; 第13頁/共22頁 s-next=top; top=s; return top; 第14頁/共22頁 free (p); return top; 第15頁/共22頁 6 0 6 高所以：（3467）10 =（6613）8第16頁/共22頁第17