嚴蔚敏數據結構課件第三章棧和隊列

1、第3章 棧和隊列 孫甲霞孫甲霞n教學目標：掌握棧和隊列的結構特性，熟練掌握棧和教學目標：掌握棧和隊列的結構特性，熟練掌握棧和隊列的基本操作在兩種存儲結構上的實現方法。隊列的基本操作在兩種存儲結構上的實現方法。n教學重點：棧和隊列的基本操作教學重點：棧和隊列的基本操作n教學難點：遞歸教學難點：遞歸n教學時數：教學時數：4n棧和隊列是特殊的線性表，是操作受限的線性表。和棧和隊列是特殊的線性表，是操作受限的線性表。和線性表的運算規(guī)則不同。線性表的運算規(guī)則不同。3.1 棧的定義和特點3.1.1 棧的定義和特點棧的定義和特點棧是棧是限定在表尾進行插入刪除操作的線性表限定在表尾進行插入刪除操作的線性表。表

2、尾端稱。表尾端稱為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。棧棧s=( a1，a2，an)n插入元素到插入元素到棧頂棧頂（即表尾）的操作，稱為（即表尾）的操作，稱為入棧入棧。n從從棧頂棧頂（即表尾）刪除最后一個元素的操作，稱為（即表尾）刪除最后一個元素的操作，稱為出棧出棧。n棧的特點：棧的特點：后進先出（后進先出（LIFO）棧底元素棧底元素棧頂元素棧頂元素3.3 棧的表示和實現3.3.2、順序棧、順序棧即即采用一組地址連續(xù)的存儲單元采用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂依次存放自棧底到棧頂的數據元素。的數據元素。basetopa1ba

3、setop空棧空棧含有含有1個元素的棧個元素的棧含有含有n個元素的棧個元素的棧top=basetop指向棧頂元素的下一個位置指向棧頂元素的下一個位置basetopa1a2a3ann順序棧的表示與實現順序棧的表示與實現棧的順序存儲表示：棧的順序存儲表示：#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef struct SElemType *base; /棧底指針，始終指向棧底元素，構棧底指針，始終指向棧底元素，構造之前和銷毀之后，造之前和銷毀之后，base的值為的值為NULLSElemType*top; /棧頂指針棧頂指針,始終指向

4、棧頂元素的始終指向棧頂元素的下一個位置下一個位置intstacksize; /當前分配的存儲容量，以元素為當前分配的存儲容量，以元素為單位單位SqStack;基本操作1、初始化操作、初始化操作status InitStack(SqStack &S) /構造一個空棧構造一個空棧SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /若分配失敗，異常退出若分配失敗，異常退出/否則，初始化棧頂指針否則，初始化棧頂指針top和和stacksizeS.top=S.base

5、;S.stacksize=STACK_INIT_SIZE;return OK; /InitStackS.baseS.top2、取棧頂元素、取棧頂元素status GetTop(SqStack S, SElemType &e)/若棧不空，則用若棧不空，則用e返回棧頂元素，并返回返回棧頂元素，并返回OK，否則返回，否則返回/ERRORif(S.top =S.base) return ERROR;e=*(S.top-1);return OK; /GetTopS.baseS.topa1a2a3anean(S.top-1)3、進棧、進棧status Push(SqStack &S, SE

6、lemType e)/插入元素插入元素e為新的棧頂元素為新的棧頂元素if(S.top-S.base=S.stacksize) /棧滿的標志，棧滿的標志，S.top-S.base為棧的長度為棧的長度S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e; return OK; /元素元素e進棧進棧 /PushS.

7、baseS.topa1a2a3ane4、出棧、出棧status Pop(SqStack &S, SElemType &e)/若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e返回其值，并返回返回其值，并返回/OK，否則返回，否則返回ERRORif(S.top=S.base) return ERROR; /若棧若棧S為空，返為空，返回回ERROR，S.top=S.base為?？盏臉酥緸闂？盏臉酥緀=*-S.top; /若棧不空，用若棧不空，用e返回其值，并刪除該元素返回其值，并刪除該元素rerurn OK; /PopS.topS.basea1a2a3anean注意n

8、棧的長度：棧的長度： S.top-S.basen空棧：空棧：S.top=S.basen棧滿：棧滿：S.top-S.base=S.stacksizenS.top在元素進出棧時改變在元素進出棧時改變nS.base只在追加存儲空間時改變只在追加存儲空間時改變n3.3.3、鏈棧、鏈棧鏈表插入刪除在表首進行比較方便，而棧的操作經常是鏈表插入刪除在表首進行比較方便，而棧的操作經常是在棧頂進行，因此以單鏈表的表首表示棧頂，即鏈棧在棧頂進行，因此以單鏈表的表首表示棧頂，即鏈棧為限定在鏈表首部進行插入、刪除操作的不帶頭結點為限定在鏈表首部進行插入、刪除操作的不帶頭結點的單鏈表。的單鏈表。類型定義：類型定義：ty

9、pedef struct StackNodeElemType data;struct StackNode *next;StackNode,*LinkStack;n1、初始化、初始化status InitStack(LinkStack &s)/初始化一個空棧初始化一個空棧ss=NULL;return OK;n2、入棧、入棧status Push(LinkStack &s, EelmType e)p=(LinkStack)malloc(sizeof(StackNode);p-data=e;p-next=s;/插入表首插入表首s=p;return OK;n3、出棧、出棧status

10、Pop(LinkStack &s, EelmType &e)if(s=NULL) return ERROR;e=s-data;p=s;s=s-next;free(p);return OK;n4、取棧頂元素、取棧頂元素status GetTop(LinkStack s,ElemType &e)/用用e返回棧頂元素的值返回棧頂元素的值if(s=NULL) return ERROR;e=s-data;return OK;練習例例1、一個棧的輸入序列是、一個棧的輸入序列是123456，若在入棧的過程中，若在入棧的過程中允許出棧，則棧的輸出序列允許出棧，則棧的輸出序列435612

11、可能實現嗎？可能實現嗎？ 135426的輸出呢？的輸出呢？例例2、一個棧的輸入序列為、一個棧的輸入序列為123，若在入棧的過程中允許，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？出棧，則可能得到的出棧序列是什么？判斷的原則：判斷的原則：若進棧的順序為若進棧的順序為ijk，則出棧的順序不可能是，則出棧的順序不可能是kij。討論：1、為什么要設計堆棧？它有什么獨特用途？、為什么要設計堆棧？它有什么獨特用途？n調用函數或子程序非它莫屬；調用函數或子程序非它莫屬；n遞歸運算的有力工具；遞歸運算的有力工具；n用于保護現場和恢復現場；用于保護現場和恢復現場；n簡化了程序設計的問題。簡化了程序設計

12、的問題。n2、棧和線性表的異同？棧和線性表的異同？邏輯結構邏輯結構存儲結構存儲結構運算規(guī)則運算規(guī)則線性表線性表一對一一對一順序表、鏈表順序表、鏈表隨機存取隨機存取棧棧一對一一對一順序棧、鏈棧順序棧、鏈棧后進先出后進先出3.4 棧和遞歸n3.4.1 遞歸思想遞歸思想將大問題劃分為若干個小問題，且小問題的解決方法與將大問題劃分為若干個小問題，且小問題的解決方法與原問題相同或類似，只是規(guī)模變小了，直到問題的規(guī)原問題相同或類似，只是規(guī)模變小了，直到問題的規(guī)模小到可以直接解決為止。模小到可以直接解決為止。遞歸程序的結構：遞歸程序的結構：l遞歸調用遞歸調用l遞歸結束條件（劃分到最小規(guī)模時的條件）遞歸結束條

13、件（劃分到最小規(guī)模時的條件）l遞歸出口（直接求解的方法）遞歸出口（直接求解的方法）函數類型函數類型 p（參數列表）（參數列表）if(遞歸結束條件遞歸結束條件) 直接求解；直接求解；else p(較小的參數較小的參數) ；n例、輸出鏈表中各個元素。例、輸出鏈表中各個元素。void Print(LinkList L)if(L=NULL) return;printf(L-data);Print(L-next);n棧與遞歸棧與遞歸函數調用過程：函數調用過程：1、在棧里為被調用函數分配一條記錄，保存所有的、在棧里為被調用函數分配一條記錄，保存所有的實參、局部變量和上一層的返回地址。實參、局部變量和上一層

14、的返回地址。2、被調用函數執(zhí)行結束后，將刪除棧頂記錄，并轉、被調用函數執(zhí)行結束后，將刪除棧頂記錄，并轉到返回地址處繼續(xù)執(zhí)行。到返回地址處繼續(xù)執(zhí)行。3、當前正在執(zhí)行的函數的記錄即為棧頂記錄。后調、當前正在執(zhí)行的函數的記錄即為棧頂記錄。后調用的函數先返回。用的函數先返回。3.4 棧的應用舉例3.4.1 數制轉換數制轉換將非負十進制整數將非負十進制整數N轉換成八進制數轉換成八進制數分析：分析：N除除8取余，直至商為取余，直至商為0，求得的余數逆序輸出即，求得的余數逆序輸出即為對應的八進制數?？捎脳肀４媲蟮玫挠鄶?，出棧為對應的八進制數?？捎脳肀４媲蟮玫挠鄶?，出棧的順序即為對應八進制數的正確位序。的

15、順序即為對應八進制數的正確位序。void conversion()/將輸入的任意一個非負十進制數轉換成八進制數將輸入的任意一個非負十進制數轉換成八進制數InitStack(S);scanf(N);while(N)Push(S,N%8);N/=8;while(!StackEmpty(S) Pop(s,e);printf(%d,e);/ conversion3.4.2 括號匹配的檢驗括號匹配的檢驗 假設表達式中允許括號嵌套假設表達式中允許括號嵌套,則檢驗括號是否匹配的方則檢驗括號是否匹配的方法可用法可用“期待的急迫程度期待的急迫程度”這個概念來描述。例：這個概念來描述。例： （）（）（）（） （

16、）（ )）（）（）（）（）（）（）（ （）（）（）（） （）（）解題思路：解題思路：n遇到左括號，進棧；遇到左括號，進棧；n遇到右括號，若棧不空且和棧頂的括號是一對，則出遇到右括號，若棧不空且和棧頂的括號是一對，則出棧；棧；否則，若和棧頂的不匹配或棧已空或已無右括號但棧否則，若和棧頂的不匹配或棧已空或已無右括號但棧里還有左括號，出錯里還有左括號，出錯3.4.3 表達式求值表達式求值表達式的形式：表達式的形式：#a+b*c-d/e#步驟：步驟：n構造算符優(yōu)先表構造算符優(yōu)先表n寫算法寫算法n#入棧；入棧；n遇到不等于遇到不等于#的字符或棧頂字符不等于的字符或棧頂字符不等于#(都等于都等于#則則結束

17、結束)：n若是操作數，進操作數棧；n若是運算符，和棧頂的運算符比較優(yōu)先級 優(yōu)先級高于棧頂運算符，進運算符棧；輸入下一字符 優(yōu)先級低于棧頂運算符，運算符出棧，兩操作數出棧，運算后將結果進操作數棧； 優(yōu)先級相等，脫括號，輸入下一字符3.5 隊列3.5.1 抽象數據類型隊列的定義抽象數據類型隊列的定義 隊列隊列(Queue)也是一種運算受限的線性表。也是一種運算受限的線性表。它只允許它只允許在表的一端進行插入，而在另一端進行刪除。在表的一端進行插入，而在另一端進行刪除。允許刪允許刪除的一端稱為隊頭除的一端稱為隊頭(front)，允許插入的一端稱為隊尾，允許插入的一端稱為隊尾(rear)。例如：排隊購

18、物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此的成員總是先離開隊列。因此隊列亦稱作先進先出隊列亦稱作先進先出(First In First Out)的線性表，簡稱的線性表，簡稱FIFO表。表?？贞犃锌贞犃谐鲫牫鲫犎腙犎腙犼狀^隊頭隊尾隊尾a1 a2 a3 an 長度為長度為n的非空隊列的非空隊列隊列的抽象數據定義見課本3.5.2 循環(huán)隊列循環(huán)隊列隊列的順序表示和實現隊列的順序表示和實現用一組地址連續(xù)的存儲單元存放從隊頭到隊尾的元素。用一組地址連續(xù)的存儲單元存放從隊頭到隊尾的元素。n入隊時將新元素插入入隊時將新元素插入rear所指的位

19、置，然后將隊尾指針加。所指的位置，然后將隊尾指針加。n出隊時，刪去出隊時，刪去front所指的元素，然后將隊頭指針加并返所指的元素，然后將隊頭指針加并返回被刪元素?；乇粍h元素。由此可見：由此可見：n當當front=rear時，隊列為空。時，隊列為空。n在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置。指向隊尾元素的下一位置。front reara1a2a3a4什么是假溢出？什么是假溢出？在順序隊中，當尾指針已經到了數組的上界，不能再插在順序隊中，當尾指針已經到了數組的上界，不能再插入新的隊尾元素，否則就會溢出，但其實數組

20、前段還入新的隊尾元素，否則就會溢出，但其實數組前段還有空位置，這就叫有空位置，這就叫“假溢出假溢出”。解決假溢出的途徑解決假溢出的途徑采用循環(huán)隊列采用循環(huán)隊列隊空時：隊空時：front=rear隊滿時：隊滿時：front=rear解決辦法：解決辦法：n約定約定front指向指向rear的下的下一個位置（環(huán)狀的下一一個位置（環(huán)狀的下一個位置）時為滿，即浪個位置）時為滿，即浪費費1個元素空間，隊列最個元素空間，隊列最多可有多可有n-1個元素個元素n設一標志位表示隊列是設一標志位表示隊列是滿還是空滿還是空n用一個計數器記錄隊列用一個計數器記錄隊列中元素的個數中元素的個數J2 J3J1 J4 J5fr

21、ontrear(1)隊列的定義：隊列的定義：#define MAXQSIZE100typedef structQElemtype*base;int front;intrear;SqQueue;隊空條件隊空條件 : front = rear (初始化時：初始化時：front = rear )隊滿條件：隊滿條件： front = (rear+1) % MAXQSIZE 隊列長度：隊列長度：（rearfront MAXQSIZE ）% MAXQSIZE 循環(huán)隊列的操作實現循環(huán)隊列的操作實現1）初始化一空隊列）初始化一空隊列算法要求：生成一空隊列算法要求：生成一空隊列算法操作：為隊列分配基本容量空間算

22、法操作：為隊列分配基本容量空間 設置隊列為空隊列，即設置隊列為空隊列，即 front=rear=0算法：算法：Status InitQueue ( SqQueue &Q )/初始化空循環(huán)隊列初始化空循環(huán)隊列 q Q.base=(QElemType *)malloc(sizeof(QElemType）*MAXQSIZE) ; /分配空間分配空間 if (!Q.base) exit(OVERFLOW); /失敗，退出程序失敗，退出程序 Q.front =Q.rear=0; /置空隊列置空隊列 return OK; /InitQueue;算法說明：向循環(huán)隊列的隊尾插入一個元素算法說明：向循環(huán)

23、隊列的隊尾插入一個元素分分 析析：(1) 插入前應當先判斷隊列是否滿插入前應當先判斷隊列是否滿 if ( Q . rear + 1 ) % MAXQSIZE )=Q.front) return ERROR;(2）插入動作）插入動作 Q.base Q.rear = e; Q.rear = ( Q.rear + 1 ) % MAXQSIZE; 2） 入隊操作入隊操作J2 J3J1 J4J5frontrearStatus EnQueue(SqQueue &Q, QElemType e)/向循環(huán)隊列向循環(huán)隊列 q 的隊尾加入一個元素的隊尾加入一個元素 e if ( (Q.rear+1) % M

24、AXQSIZE = = Q.front ) return ERROR ; Q.base Q.rear = e; /存儲存儲 Q.rear = ( Q . rear + 1 ) % MAXQSIZE;/指針后移指針后移 return OK; / EnQueue;算法算法J2 J3J1 J4J5frontrear3）出隊操作）出隊操作算法說明：刪除隊頭元素，返回其值算法說明：刪除隊頭元素，返回其值 e 分分 析：析： （1） 在刪除前應當判斷隊列是否空；在刪除前應當判斷隊列是否空； if (Q.front = Q.rear ) return ERROR; （2）出隊動作）出隊動作 因為隊頭指針因為

25、隊頭指針front指向隊頭元素的位置，所以：指向隊頭元素的位置，所以： e = Q.base Q.front ; Q.front = ( Q . front + 1 ) % MAXQSIZE; J2 J3J1 J4J5frontrearStatus DeQueue ( SqQueue &Q, QElemType &e) /若隊列不空，刪除循環(huán)隊列若隊列不空，刪除循環(huán)隊列 Q 的隊頭元素，的隊頭元素， /由由 e 返回其值，并返回返回其值，并返回OK if ( Q.front = = Q.rear ) return ERROR; /隊列空隊列空 e = Q.base Q.fron

26、t ; Q.front=(Q.front+1) % MAXQSIZE ; return OK; / DeQueue算法：算法：J2 J3J1 J4J5frontrear4）求隊列長度）求隊列長度int Queuelength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXSIZE;J2 J3J1 J4J5frontrear(2)隊列定義：隊列定義：#defineMAXSIZE100typedef structQelemtype *base;intfront;intrear;intflag;SqQueue;隊空條件隊空條件 : front = rea

27、r&flag=0 (初始化時：初始化時：front = rear=0,flag=0 )隊滿條件：隊滿條件： front = =rear&flag=1隊列長度：隊列長度：L=（rearfront MAXSIZE ）% MAXSIZE （隊不滿時）或（隊不滿時）或 MAXSIZE （隊滿時）（隊滿時）Status InitQueue ( SqQueue &q )/初始化空循環(huán)隊列初始化空循環(huán)隊列 q q.base=(QElemType *)malloc(sizeof(QElemType）* MAXSIZE); /分配空間分配空間 if (!q.base) exit(OVER

28、FLOW); /失敗，退出程序失敗，退出程序 q.front=q.rear=0; /置空隊列置空隊列q.flag=0; return OK; /InitQueueStatus EnQueue(SqQueue &q, QElemType e) /向循環(huán)隊列向循環(huán)隊列 q 的隊尾加入一個元素的隊尾加入一個元素 e if ( q.rear= = q.front&q.flag=1 ) return ERROR ; q.base q.rear = e; /存儲存儲 q.rear = ( q.rear + 1 ) % MAXSIZE; /指針后移指針后移 if(q.rear=q.front

29、) q.flag=1; /插入后隊列滿，插入后隊列滿，flag置置1 return OK; / EnQueueStatus DeQueue ( SqQueue &q, QElemType &e) /若隊列不空，刪除循環(huán)隊列若隊列不空，刪除循環(huán)隊列 q 的隊頭元素，的隊頭元素， /由由 e 返回其值，并返回返回其值，并返回OK if (q.front = = q.rear&q.flag=0) return ERROR; /隊隊列空列空 e = q.base q.front ; q.front=(q.front+1) % MAXSIZE ; if(q.front = = q

30、.rear ) q.flag=0; return OK; / DeQueuegint Queuelength(SqQueue q)if(q.rear=q.front&q.flag=1) return MAXSIZE;else return (q.rear-q.front+MAXSIZE)%MAXSIZE;3.5.3 鏈隊列鏈隊列 隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅在表隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。頭刪除和表尾插入的單鏈表。由于需要在隊頭刪除、隊尾插入，設頭指針和尾指針。由于需要在隊頭刪除、隊尾插入，設頭指針和尾指針。 Q.frontQ.

31、rear帶頭結點的空鏈隊列帶頭結點的空鏈隊列 Q.frontQ.rear x 元素元素x入隊列入隊列 Q.frontQ.rear x y 元素元素y入隊列入隊列 Q.frontQ.rear x y 元素元素x出隊列出隊列鏈隊列的類型鏈隊列的類型LinkQueue的定義：的定義： typedef struct QNode/隊列結點類型隊列結點類型 QElemType data; struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue; /鏈隊列類型鏈隊列類型初始化以下基本操

32、作針對帶頭結點的隊列以下基本操作針對帶頭結點的隊列status InitQueue(LinkQueue &Q)/構造一個空隊列構造一個空隊列Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK; /InitQueue Q.frontQ.rear銷毀隊列status DestroyQueue(LinkQueue &Q) /銷毀隊列銷毀隊列Qwhile(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;/DestroyQueueQ.frontQ.rear y x進隊status EnQueue(LinkQueue &am