第4章 棧和隊列

1、第四章 棧與隊列本章主要內(nèi)容n 棧的概念、存儲結(jié)構(gòu)及其基本操作n 棧的應(yīng)用n隊列的概念、存儲結(jié)構(gòu)及其基本操作n隊列的應(yīng)用n遞歸4.1 4.1 棧棧n棧的定義n棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。n進(jìn)行插入和刪除的稱為棧頂，并用一個“棧頂指針”指示；而另一端是固定端，稱為棧底。a1, a2, a3, ., an 插入和刪除端插入和刪除端棧的特點棧的特點n后進(jìn)先出（后進(jìn)先出（Last In First Out），簡稱為），簡稱為LIFO線性表。線性表。 n舉例1：家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，一定最先

2、拿走最上面的那只碗，而最后拿出最下面的那只碗。 n舉例2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地拿取。 n順序棧 用順序存儲實現(xiàn)的棧稱為順序棧。分配一塊連續(xù)的存儲空間存放棧中的元素，棧底位置固定設(shè)置在數(shù)組的任何一端（一般在下標(biāo)為0的一端），棧頂是隨著插入和刪除變化的，用一個變量指明棧頂?shù)奈恢茫▽嶋H上是棧頂元素的下一個位置），存儲結(jié)構(gòu)如圖所示。棧的C+實現(xiàn)typedef int DataType; /這里以整型為棧的數(shù)據(jù)類型class SeqStackprivate: DataType *base;/棧底指針 DataType *top;/棧頂指針始終指向

3、棧頂元素的后一個位置 int size;/棧的大小public: SeqStack(int stacksize=100) base=new DataType stacksize; top=base; /指向棧頂元素的后一位置 size=stacksize; ; /構(gòu)造了一個空棧,默認(rèn)大小為100個單元 SeqStack() delete base; top=NULL;base=NULL; ; /銷毀一個已存在的棧 int Empty_Stack(); /判斷棧是否為空 int Push_Stack(DataType e); /將元素e插入棧頂 int Pop_Stack(DataType &a

4、mp;e);/從棧頂刪除一個元素到e中返回 int GetTop_Stack(DataType &e); /從棧頂取一個元素到e中返回;/順序棧類順序棧的成員函數(shù)的實現(xiàn) （1）判斷棧是否為空 算法思想：判斷top是否小于等于base，小于等于則為空棧，返回1，否則返回0。 int SeqStack:Empty_Stack() /判斷順序棧是否為空 return(top=base);（2）入棧操作 算法思想：首先判斷棧是否已滿，若滿則失敗，返回0；否則，由于棧的top指向棧頂元素的后一個位置，將入棧元素賦到top的位置，再將top+1指向新的位置，成功返回1。 int SeqStack:

5、Push_Stack(DataType e) if(top-basebase) /判斷棧是否為空 top-; e=*top; return 1; else return 0;（4）取棧頂元素操作 算法思想：首先判斷棧是否為空，若空則失敗，返回0；否則，由于棧的top指向棧頂元素的后一位置，返回top-1所指單元的值，棧不發(fā)生變化。 int SeqStack:GetTop_Stack(DataType &e) if(topbase) /判斷棧是否為空 e=*(top-1); return 1; else return 0;鏈棧的成員函數(shù)的實現(xiàn) 棧也可以用鏈?zhǔn)酱鎯Ψ绞綄崿F(xiàn)。一般鏈棧用單鏈表

6、表示，其結(jié)點結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同，即結(jié)點為：typedef int DataType; /這里以整型為棧的數(shù)據(jù)類型 class StackNode /定義鏈棧的結(jié)點public: DataType data; StackNode *next; StackNode() next=NULL; ; ; 鏈棧的存儲示意圖鏈棧的類定義class LinkStackprivate: StackNode *top;public: LinkStack() top=NULL; ; /構(gòu)造一個新的空棧 LinkStack() /銷毀一個已存在的棧 StackNode *p; while(top) /銷毀棧中所有

7、元素 p=top; top=top-next; delete p; top=NULL; /棧頂指針賦空表示為空棧 ; int Empty_Stack();/判斷棧是否為空 int Push_Stack(DataType e);/將元素e插入棧頂 int Pop_Stack(DataType &e);/從棧頂刪除一個元素到e中返回 int GetTop_Stack(DataType &e); /從棧頂取出一個元素到e中返回; /鏈棧類鏈棧的成員函數(shù)的實現(xiàn) （1）判斷棧是否為空int LinkStack:Empty_Stack() /判斷鏈棧是否為空 return(!top);（2

8、）入棧操作 算法思想：首先為鏈棧分配空間，若成功，將入棧元素賦值到申請的鏈棧結(jié)點，并插入棧頂，使其成為棧頂元素，成功返回1；否則失敗，返回0。int LinkStack:Push_Stack(DataType e) StackNode *p=new StackNode; /申請結(jié)點 if(p) /申請結(jié)點成功 p-data=e; p-next=top; top=p; /修改棧頂指針 return 1; else return 0;（3）出棧操作 算法思想：首先判斷棧是否為空，若非空，則取出棧頂元素，以引用參數(shù)e返回，并刪除這個結(jié)點，成功返回1；否則，失敗返回0。 int LinkStack:P

9、op_Stack(DataType &e) StackNode *p;if(top) p=top; e=p-data; top=top-next; /修改棧頂指針 delete p; /刪除結(jié)點 return 1; else return 0;（4）取棧頂元素操作 算法思想：首先判斷棧是否為空，若非空，則取出棧頂元素，以引用參數(shù)e返回，成功返回1；否則，失敗返回0。 int LinkStack:GetTop_Stack(DataType &e) if(top) e=top-data; return 1; else return 0;返回棧的應(yīng)用 1.數(shù)制轉(zhuǎn)換 將十進(jìn)制數(shù)N轉(zhuǎn)換為

10、r進(jìn)制的數(shù)，其轉(zhuǎn)換方法為輾轉(zhuǎn)相除法。以N=1 234，r=8為例，轉(zhuǎn)換方法如下。算法思想如下。（1）初始化一個字符類型的棧，初始化N為要轉(zhuǎn)換的數(shù)，r為進(jìn)制數(shù)；（2）判斷N的值，為0時轉(zhuǎn)（4），否則N % r所表示的數(shù)碼壓入棧s中；（3）用N / r代替N，轉(zhuǎn)（2）；（4）出棧，出棧序列即為結(jié)果。int DecConversion(int N,int r,char NumR) /十進(jìn)制N轉(zhuǎn)換成r進(jìn)制,這里r為不大于10的數(shù) SeqStack S; /定義一個順序棧 DataType x; int i=0; if(r10) /限定為十進(jìn)制以下 return(0); while(N) S.Push_

11、Stack(CodeTableN%r); /余數(shù)表示的數(shù)碼入棧 N=N/r; /商作為被除數(shù)繼續(xù) while(!S.Empty_Stack() /直到?？胀顺鲅h(huán) S.Pop_Stack(x);/彈棧頂元素 NumRi+=x;/輸出棧頂元素 NumRi=0; return(1);返回隊 列 隊列也是一種特殊的線性表，是限制在表的一端進(jìn)行插入和在另一端進(jìn)行刪除的線性表。表中允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭（front）。 e1 e2 e3 e4 e5 入隊 出隊 隊列又稱為先進(jìn)先出線性表（First In First Out），簡稱FIFO表。其特點是先進(jìn)先出或者后進(jìn)后

12、出 順序隊列 分配一塊連續(xù)的存儲空間來存放隊列中的元素，并且由于隊列的隊頭和隊尾都是活動的，因此有隊頭、隊尾兩個指針。這里約定，隊頭指針指向?qū)嶋H隊頭元素所在的位置的前一位置，隊尾指針指向?qū)嶋H隊尾元素所在的位置 n隊列假溢問題解決辦法循環(huán)隊列下的運算實現(xiàn)typedef int DataType; /這里以整型為隊列的數(shù)據(jù)類型 class SeqQueueprivate: DataType *base; int front; int rear; int size;public: SeqQueue(int Queuesize=100) /構(gòu)造一個空隊列，空間大小為100 base=new DataT

13、ype Queuesize; front=0; rear=0; size=Queuesize; ; SeqQueue() /銷毀一個已存在的隊列 delete base; ; int Empty_Queue(); /判斷隊列是否為空 int En_Queue(DataType e); /入隊將元素e插入隊尾 int De_Queue(DataType &e); /出隊從隊頭刪除一個元素到e中返回 int Front_Queue(DataType &e); /取隊頭元素，從隊頭取出一個元素到e中返回; （1）判斷循環(huán)隊列是否為空 int SeqQueue:Empty_Queue(

14、)/判斷循環(huán)隊列是否為空 return(front=rear);（2）進(jìn)隊操作 算法思想：首先判斷隊是否已滿，若滿則退出，否則，由于隊的rear指向隊尾元素，先修改rear到新的隊尾位置，再將入隊元素賦到rear的位置即可。 int SeqQueue:En_Queue(DataType e) if(rear+1)%size)!=front)/判斷隊列是否滿 rear=(rear+1)%size; baserear=e; return 1; else return 0;（3）出隊操作 算法思想：首先判斷隊列是否為空，若空則退出，否則，由于隊列的front指向隊頭元素的前一位置，因此要先修改fro

15、nt，再將其front所指向的元素以引用參數(shù)e返回即可。int SeqQueue:De_Queue(DataType &e) if(rear!=front) /判斷隊列是否空 front=(front+1)%size; e=basefront; return 1; else return 0;（4）取隊頭元素操作 算法思想：首先判斷隊是否為空，若空則退出，否則，由于隊列的front指向隊頭元素的前一位置，因此要返回的隊頭元素是front的后一位置。 int SeqQueue:Front_Queue(DataType &e) if(rear!=front) /判斷隊列是否空 e=

16、base(front+1)%size; return 1; else return 0; 返回4.隊列的應(yīng)用 求迷宮的最短路徑：現(xiàn)要求設(shè)計一個算法找一條從迷宮入口到出口的最短路徑 算法基本思想：從迷宮入口點（1，1）出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點；然后依次再從這些點出發(fā)，再記下所有一步能到達(dá)的坐標(biāo)點；依此類推，直到到達(dá)迷宮的出口點（m，n）為止，然后從出口點沿搜索路徑回溯直至入口。這樣就找到了一條迷宮的最短路徑，否則迷宮無路徑 使用隊列保存搜索過程5.遞歸 遞歸的定義：若一個對象部分地包括它自己，或用它自己給自己定義，則稱這個對象是遞歸的；或定義為在一個過程中直接或間接地調(diào)用自己

17、，則這個過程是遞歸的。 以n的階乘為例，n!的定義為：n的階乘等于n乘以n-1的階乘，公式標(biāo)示：1 0!(1)! 0nnnnn當(dāng)時當(dāng)時int fact(int n) if(n=0) return 1; else return(n* fact(n-1);遞歸算法書寫要點如下。（1）問題具有類同自身的子問題的性質(zhì)，被定義項在定義中的應(yīng)用具有更小的尺度。（2）被定義項在最小尺度上有直接解。設(shè)計遞歸算法的方法是：（1）尋找方法，將問題化為原問題的子問題求解（例如n!=n*(n-1)!）。（2）設(shè)計遞歸出口，確定遞歸終止條件（例如求解n!時，當(dāng)n=1時，n!=1）。遞歸過程的調(diào)用和返回 遞歸函數(shù)的遞歸過

18、程：在遞歸進(jìn)層（ii+1層）時系統(tǒng)需要做3件事。（1）保留本層參數(shù)與返回地址（將所有的實際參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存）；（2）給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲區(qū)）；（3）將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，遞歸退層（ii+1層）系統(tǒng)也應(yīng)完成3項工作。（1）保存被調(diào)函數(shù)的計算結(jié)果；（2）恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）；（3）依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。n具體實例：n！的遞歸調(diào)用過程求迷宮中的一條路徑的遞歸算法 算法思想：在搜索路徑的過程中，每個點朝4個方向的搜索方法是一樣的，故可設(shè)計成遞歸算法 int mazepath(int *maze,int x,int y,int m,int n) struct int dx; int dy; move4; /定義移動的4個方向 mo