1、第三章 棧和隊列3.1 棧3.2 棧的應用舉例3.3 隊列1 3.1.1 棧的定義 棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom).當表中沒有元素時稱為空棧。 假設棧S=(a1，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為后進先出表（LIFO）。3.1 棧棧：限定只能在表的一端進行插入和刪除的特殊的線性表. 設棧s=（a1，a2，. . . ,ai，. . . ，an），

2、其中a1是棧底元素， an是棧頂元素。棧頂（top)：允許插入和刪除的一端； 棧頂的當前位置由棧頂指針的位置指示器指示。棧底（bottom):不允許插入和刪除的一端。進棧或入棧：棧的插入操作。出棧或退棧：棧的刪除操作。 a1 a2 . an進棧出棧棧頂棧底3.1.1 棧的定義空棧：沒有元素的棧棧的特性：先進后出（LIFO），即只能在末端（棧頂）進行插、刪的操作3.1.1 棧的定義例：一疊書或一疊盤子。 棧頂 棧底3.1.1 棧的定義棧中的幾種基本操作： 1.插入一個新的棧頂元素（進棧）:push(S,x); 2.刪除棧頂元素（出棧）: pop(S); 3.讀取棧頂元素:getTop(S); 4

3、.判空棧:stackEmpty(S); 3.1.1 棧的定義棧的存儲結構順序棧利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，一般用一維數組表示必須附設一個位置指針top（棧頂指針）來動態地指示棧頂元素在順序棧中的位置鏈棧采用鏈表作為存儲結構實現的必須設置一個棧頂指針永遠指向棧頂3.1.2 棧的表示和實現一、順序棧 由于棧是運算受限的線性表，因此線性表的存儲結構對棧也適應。 棧的順序存儲結構簡稱為順序棧，它是運算受限的線性表。因此，可用數組來實現順序棧。因為棧底位置是固定不變的,所以可以將棧底位置設置在數組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的。3.1.2 棧的表

4、示和實現 需用一個整型變量top來指示當前棧頂的位置，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。一、順序棧順序棧的結構int stack105;stack0 = a1;stack1 = a2;top = 2stacktop+ = a3; 一、順序棧a2a1top-一、順序棧對應的出棧操作為：top- 進棧操作為：top+ 得到棧頂元素為：atop判斷棧為空的操作為：if(top = 0)進棧算法int Push(int stack, int x) if(top maxsize ) return 0; stacktop+ = x; retur

5、n 1; a2 a3 a4987654321 a10top一、順序棧棧的判空操作int stackempty() if ( top = 0) return 1; else return 0;出棧算法： a2 a3 a4987654321 a10top一、順序棧int pop (int stack) top - ; return stacktop;二、鏈棧 棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表，插入和刪除操作僅限制在表頭位置上進行.由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。 3.1.2 棧的表示和實現 antop棧底 用指針來實現的棧叫

6、鏈棧。棧的容量事先不能估計時采用這種存儲結構。鏈棧的類型說明如下：typedef struct Lnode int data； struct Lnode next； node;node LinkStack；top頭指針永遠指向頭結點二、鏈棧進棧算法二、鏈棧void push(node LinkStack,int x) node *temp; temp = (node*)malloc(sizeof(node); temp-data = x; temp-next = LinkStack-next; LinkStack-next = temp出棧算法二、鏈棧void pop(node LinkSta

7、ck,int &x) node *temp; temp = LinkStack-next; LinkStack-next = LinkStack-next-next; x = temp-data; free(temp); 1 數制的轉換 sdut 21312 括號匹配的檢驗 sdut 21343 表達式求值 sdut 2132 2133hdu 1022水題大戰的題目。（模擬棧的過程）3.2 棧的應用 隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統中的作

8、業排隊。 先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表，簡稱FIFO表。當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,an ，也就是說隊列的修改是依先進先出的原則進行的。3.3.1 隊列的定義下圖是隊列的示意圖：出隊入隊隊頭隊尾 a1a2an3.3.1 隊列的定義隊尾：在隊列中，允許插入的一端隊頭：在隊列中，允許刪除的一端隊列的主要運算設置一個空隊列；插入一個新的隊尾元素，稱為進隊；刪除隊頭元素，稱為出隊；讀取隊頭元素；等3.3.1 隊列的

9、定義隊列的存儲結構（1）順序存儲結構(a) 線性隊列 (b) 循環隊列（2）鏈式存儲結構3.3.2 隊列的表示和實現隊列的類型定義：#define MAXSIZE 50typedef struct int elem MAXSIZE; int front;int rear;SeqQueue;e1,e2出隊，e4入隊隊滿 e1 e2 e3 (b)rearfronte1,e2,e3入隊 隊空時， 令rear=front=0，當有新元素入隊時，尾指針加1，當有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素的位置，而尾指針始終指向隊尾元素后一個位置rear=front=0(隊空)fron

10、t 3 2 1 0 (a)rearrear=4 (c) e3 e4front隊列的順序存儲 和棧類似，隊列中亦有上溢和下溢現象。此外，順序隊列中還存在“假上溢”（假溢出）現象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際的元素個數遠遠小于向量空間的規模，但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現象稱為假上溢。隊列的順序存儲 為充分利用向量空間。克服上述假上溢現象的方法是將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量，存儲在其中的隊列稱為循環隊列（Circular Queue)。在循環隊列中進行出隊、入隊

11、操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結果是指向向量的下界0。這種循環意義下的加1操作可以描述為： if(i+1=QueueSize) i=0; else i+;利用模運算可簡化為： i=(i+1)%QueueSize隊列的順序存儲 顯然，因為循環隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應用外，真正實用的順序隊列是循環隊列。 如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊列“

12、空”還是“滿”。 解決此問題的方法至少有三種： 其一是另設一個布爾變量以區別隊列的空和滿；其二是少用一個元素的空間，約定入隊前，測試尾指針在循環意義下加1后是否等于頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空）；隊列的順序存儲 其三是使用一個計數器記錄隊列中元素的總數（實際上是隊列長度）。下面我們用第三種方法實現循環隊列上的六種基本操作，為此先給出循環隊列的類型定義。 #define QueueSize 100 typedef struct Queuedatatype dataqueuesize int front， rear; int len; sqqueue;隊列的順序存儲（

13、1）置空隊 void initqueue(sqqueue *q) qfront=qrear=-1; qlen=0; （2）判斷隊空 int queueempty(sqqueue *q) return qlen=0; （3）判斷隊滿 int queuefull(sqqueue *q) return qlen=queuesize; 隊列的順序存儲（4）入隊 void inqueue(sqqueue *q,datatype x) if(queuefull(q) printf(“queue overflow”); return; qlen+; qdataqrear=x; qrear=(qrear+1)

14、%queuesize; 隊列的順序存儲（5）出隊 queuedatatype dequeue(sqqueue *q) datatype temp; if(queueempty(q) printf(“queue underflow”); return; temp=qdataqfront; qlen-; qfront=(qfront+1)%queuesize; return temp; 隊列的順序存儲（6）取頭元素 queuedatatype queuefront(sqqueue *q) if(queueempty(q) printf(“queue is empty.”); return(0);

15、return qdataqfront; 隊列的順序存儲區分隊列空與滿另一種方法 少用一個元素的空間，約定入隊前，測試尾指針在循環意義下加1后是否等于頭指針,若相等則認為隊滿（注意：rear所指的單元始終為空）；隊列的順序存儲循環隊列 rear front 0 1 2 3(3) 隊空隊滿條件：(Q.rear+1)%MAX=Q.front注：實際上為了避免與隊空標志沖突，還留有一個空間。將頭尾連接成一個環，形成循環隊列。(1)一般情況 rear front 0 1 2 3e4e3 (2) 隊滿 front e3 e4 0 1 2 3 reare5隊列的順序存儲#define MAXSIZE 50t

16、ypedef structQueueElementType elementMAXSIZE; int front;int rear;SeqQueue;注意事項：1、出隊時，頭指針的變化為front=(front+1) mod MAXSIZE2、入隊時，尾指針的變化為rear=(rear+1) mod MAXSIZE3、凡是遇到指針要發生變化，頭和尾指針的有效范圍為0,MAXSIZE-1，所以用取模運算來保證頭尾指針的取值循環隊列的類型定義循環隊列中加入一個元素的算法： int EnQueue(SeqQueue *Q,int x) Q為已有的循環隊列將插入的值循環隊列循環隊列中加入一個元素的算法：

17、 int EnQueue(SeqQueue *Q,int x) if(Q-rear+1)%MAXSIZE= =Q-front) return(0); else Q-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3rearX循環隊列循環隊列中刪除一個元素的算法：int DeQueue(SeqQueue *Q，int *py) 已有的循環隊列返回刪除的值的地址循環隊列循環隊列中刪除一個元素的算法：int DeQueue(SeqQueue *Q，int *py) if(Q-rear= =Q-front) retu

18、rn(0); else*py=QQ-front; Q-front=(Q-front+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3front循環隊列鏈式存儲結構 an a2 a1Q.frontQ.rear隊頭隊尾typedef struct NodeQueueElementType data; struct Node *next;LinkQueueNode;/*結點的定義*/typedef structLinkQueueNode *front; LinkQueueNode *rear;LinkQueue;/*隊列的定義*/注意：隊頭永遠指向頭結點，隊尾永遠指向最后一個