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