【正文】 eturn 1。x) { if (==1) //棧空 return 0。 } } 19 (4)取棧頂元素運(yùn)算算法 其主要操作是：將棧中 top處的元素取出賦給變量 x。 。x) //x為引用型參數(shù) { if (==1) return 0。 int Pop(SqStack amp。 return 1。 else { ++。 int Push(SqStack amp。st) //st為引用型參數(shù) { =1。 //順序棧的初始分配空間 typedef struct sqst { ElemType data[StackSize]； //保存棧中元素 int top； //棧指針 } SqStack； 16 順序棧的基本運(yùn)算算法如下 : (1)初始化棧運(yùn)算算法 此算法主要用于創(chuàng)建一個空棧 ,并將棧頂下標(biāo)top初始化為 1。 top=1表示?？?； top=StackSize1表示棧滿。Data為一個一維數(shù)組，用于存儲棧中元素， ElemType為棧元素的數(shù)據(jù)類型，可以根據(jù)需要而指定為某種具體的類型。如果作出棧運(yùn)算，則會 “ 下溢 ” 。 圖 (a)表示順序棧為棧空，這也是初始化運(yùn)算得到的結(jié)果。習(xí)慣上將棧底放在數(shù)組下標(biāo)小的那端。 //輸出 n } } 13 棧的順序存儲結(jié)構(gòu) 棧的順序存儲結(jié)構(gòu)稱為順序棧。 //n進(jìn)棧 } cout “輸出序列： ” ； while (!StackEmpty(st)) //棧不空時循環(huán) { Pop(st,n)。 if (n==0) break。 cout “輸入一串整數(shù)（以 0標(biāo)識結(jié)束） ” ； InitStack(st)。 解：使用一個棧實(shí)現(xiàn)本例要求，先將輸入的整數(shù)進(jìn)棧，然后出棧并輸出。 12 例 利用棧的基本運(yùn)算，編寫一個算法輸入若干整數(shù)，以 0標(biāo)識輸入結(jié)束。 (4)取棧頂元素 GetTop(st,x):若 st不空，由 x返回當(dāng)前的棧頂元素 ,當(dāng)棧 st為空時，結(jié)果為一特殊標(biāo)志 (。 (2)進(jìn)棧 Push(st,x):將元素 x插入到棧 st中作為棧頂元素。 所以本題答案為 C。 (A) 一定是 2 (B) 一定是 1 (C) 不可能是 1 (D) 以上都不對 答 :當(dāng) p1=3時 ,說明 1,2,3先進(jìn)棧 ,立即出棧 3,然后可能出棧 ,即為 2,也可能 4或后面的元素進(jìn)棧 ,再出棧 。 (A) i (B) ni (C) ni+1 (D) 不確定 答 :當(dāng) p1=n時 ,輸出序列必是 n,n1,… ,3,2,1,則有 : p2=n1, p3=n2, … , pn=1 推斷出 pi=ni+1,所以本題答案為 C。所以本題答案為 D。 答 :所有可能的出棧次序如下 : abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 8 例 2 設(shè)一個棧的輸入序列為 A,B,C,D,則借助一個棧所得到的輸出序列不可能是 。因此棧又稱為后進(jìn)先出線性表。插入、刪除運(yùn)算都在棧頂進(jìn)行，相當(dāng)于進(jìn)出都經(jīng)過胡同口。 這里 ， 人進(jìn)出胡同的原則是后進(jìn)去的先出來 。 此時若編號為 ④ 的人要退出胡同 ，必須等 ⑤ 退出后才可以 。 舉一個例子說明棧結(jié)構(gòu)的特征 ， 假設(shè)有一個很窄的死胡同 ， 胡同里能容納若干人 ， 但每次只能容許一個人進(jìn)出 。 棧的插入操作通常稱為 進(jìn)棧 或 入棧 ,棧的刪除操作通常稱為 退棧 或 出棧 。 處于棧頂位置的數(shù)據(jù)元素稱為 棧頂元素 。1 第 3章 棧和隊列 隊列 棧 本章小結(jié) 2 棧的基本概念 棧的順序存儲結(jié)構(gòu) 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 棧 3 棧是一種特殊的線性表，這種線性表上的插入和刪除運(yùn)算限定在表的某一端進(jìn)行。表中允許進(jìn)行插入、刪除操作的一端稱為 棧頂 ；另一端稱為棧底 。不含任何數(shù)據(jù)元素的棧稱為 空棧 。 棧的基本概念 4 棧的特點(diǎn)是后進(jìn)先出 。 現(xiàn)有五個人 ，分別編號為 ① ~⑤ ， 按編號的順序依次進(jìn)入此胡同 ，如圖 。 若 ① 要退出 ， 則必須等到⑤ 、 ④ 、 ③ 、 ② 依次都退出后才行 。 ⑤ ④ ③ ② ① 圖 5 ?？梢员茸鬟@里的死胡同，棧頂相當(dāng)于胡同口，棧底相當(dāng)于胡同的另一端，進(jìn)、出胡同可看作棧的插入、刪除運(yùn)算。這表明棧修改的原則是 先進(jìn)后出 （或 后進(jìn)先出 ）。 6 棧頂 棧底 出棧 進(jìn)棧 棧示意圖 7 例 1 設(shè)有 4個元素 a、 b、 c、 d進(jìn)棧 ,給出它們所有可能的出棧次序 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 答 :可以簡單地推算 ,得容易得出 D,A,B,C是不可能的 ,因?yàn)?D先出來 ,說明 A,B,C均在棧中 ,按照入棧順序 ,在棧中順序應(yīng)為 D,C,B,A,出棧的順序只能是 D,C,B,A。 9 例 3 已知一個棧的進(jìn)棧序列是 1,2,3,… ,n,其輸出序列是 p1,p2,… ,pn,若 p1=n,則 pi的值 。 10 例 4 設(shè) n個元素進(jìn)棧序列是 1,2,3,… ,n,其輸出序列是 p1,p2,… ,pn,若 p1=3,則 p2的值 。因此 ,p2可能是 2,也可能是 4,… ,n,但一定不能是 1。 11 棧的基本運(yùn)算至少應(yīng)包括以下 5種 : (1)初始化棧 InitStack(st):構(gòu)造一個空棧 st。 (3)出棧 Pop(st,x):其作用是當(dāng)棧 st不空時，將棧頂元素賦給 x,并從棧中 刪除當(dāng)前棧頂 。 (5)判斷棧是否為空 StackEmpty(st):若棧 st為空 ,則返回 1；否則返回 0。然后按與輸入相反次序輸出這些整數(shù)。對應(yīng)的算法如下： void Invert() { int n。 //初始化棧 st while (1) { cin n。 //輸入值 n為 0時退出循環(huán) Push(st,n)。 //出棧 n cout n “ ”。順序棧通常由一個 一維數(shù)組 和 一個記錄棧頂元素位置的變量 組成。假設(shè)用一維數(shù)組sq[5]表示一個棧，則需使用一個變量 top記錄當(dāng)前棧頂下標(biāo)值。此時棧頂下標(biāo)值 top=1。 14 順序棧進(jìn)棧和出棧示意圖 top 1 top top top 15 順序棧類型定義如下： 順序棧被定義為一個結(jié)構(gòu)體類型，它有兩個域： data和 top。top為 int型，它的實(shí)際取值范圍為 0 ~ StackSize1。 const int StackSize=100。 void InitStack(SqStack amp。 } 17 (2)進(jìn)棧運(yùn)算算法 其主要操作是：棧頂下標(biāo)加 1,將進(jìn)棧元素放進(jìn)棧頂下標(biāo)所指的位置上 。st, ElemType x) { if