1、 通常稱，棧和隊列是限定通常稱，棧和隊列是限定插入和刪除插入和刪除只只能在表的能在表的“端點端點”進行的線性表。進行的線性表。 線性表線性表 棧棧 隊列隊列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊列是兩種常用的數據類型棧和隊列是兩種常用的數據類型第三章 棧和隊列3.1 棧棧3.2 棧的應用舉例棧的應用舉例3.4 隊列隊列學習提要：學習提要：1.1.掌握棧和隊列這兩種抽象數據類型的特點，掌握棧和隊列這兩種抽象數據類型的特點， 并能在

2、相應的應用問題中正確選用它們。并能在相應的應用問題中正確選用它們。2.2.熟練掌握棧類型的兩種實現方法，即兩種存熟練掌握棧類型的兩種實現方法，即兩種存 儲結構表示時的基本操作實現算法，特別應儲結構表示時的基本操作實現算法，特別應 注意棧滿和棧空的條件以及它們的描述方法。注意棧滿和棧空的條件以及它們的描述方法。3.3.熟練掌握循環隊列和鏈隊列的基本操作實現熟練掌握循環隊列和鏈隊列的基本操作實現 算法，特別注意隊滿和隊空的描述方法。算法，特別注意隊滿和隊空的描述方法。重難點內容：重難點內容： 順序棧的相關操作、循環隊列的判空判滿順序棧的相關操作、循環隊列的判空判滿3.1 棧（棧（stack）3.1

3、.1 棧的類型定義棧的類型定義3.1.2 棧的表示和實現棧的表示和實現棧的定義和特點棧的定義和特點v定義：限定僅在定義：限定僅在表尾表尾進行插入或刪除操進行插入或刪除操作的線性表，表尾作的線性表，表尾棧頂棧頂，表頭，表頭棧底棧底，不含元素的空表稱不含元素的空表稱空棧空棧。ana1a2.棧底棧底棧棧頂頂.出棧出棧進棧進棧棧棧s=(a1,a2,an)v特點：先進后出（特點：先進后出（FILO）或后進先出）或后進先出（LIFO）3.1.1 棧的類型定義 ADT Stack 數據對象數據對象： D ai | ai ElemSet, i=1,2,.,n, n0 數據關系數據關系： R1 | ai-1,

4、aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT Stack 棧的類型定義棧的類型定義InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()順序棧順序棧3.1.2 棧的表示和實現棧的表示和實現 類似于線性表的順序映象實現，類似于線性表的順序映象實現，指向表尾的指針可以作為指向表尾的指針可以作為棧頂指針棧頂指針。/- 棧的順序存儲表示棧的順序存儲表示 -

5、 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;利用數組靜態分配定義：利用數組靜態分配定義：Typedef struct stackSelemType stackmaxsize;int top; /top=-1空棧空棧top=maxsize-1滿滿順序棧示意圖順序棧示意圖*base*topstacksize.a1.aian*base*topstacksize初始初始空空棧棧*top = *

6、base; stacksize = STACK_INIT_SIZE順序棧順序棧dcba實現：一維數組實現：一維數組sMtop123450進棧進棧A棧滿棧滿BCDEF設數組維數為設數組維數為M Mtop=base,top=base,棧空，此時出棧，則棧空，此時出棧，則下溢下溢（underflow)underflow)top=M,top=M,棧滿，此時入棧，則棧滿，此時入棧，則上上溢溢（overflow)overflow)toptoptoptoptop123450空棧空棧topbasebasetop出棧出棧toptop棧空棧空base棧底指針棧底指針base,base,始終始終指向棧底位置；指向棧

7、底位置；棧頂棧頂指針指針top,top,其初值指向其初值指向棧底，始終在棧頂元棧底，始終在棧頂元素的下一個位置素的下一個位置123450ABtop=實現：一維數組實現：一維數組sM Status InitStack (SqStack &S)/ 構造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (

8、SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿，追加存儲空間 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; Status Pop (S

9、qStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回OK； / 否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;*S.top+ = ee = *-S.top 0M-1棧棧1底底棧棧1頂頂棧棧2底底棧棧2頂頂在一個程序中同時使用兩個棧在一個程序中同時使用兩個棧鏈棧鏈棧 棧的鏈式存儲結構。棧頂指針就是棧的鏈式存儲結構。棧頂指針就是鏈表的頭指針。鏈表的頭指針。棧頂指針a1an注意注意: 鏈棧中鏈棧中指針的方向指針的方向an-1注意：注意：鏈棧中的指針方向鏈棧

10、中的指針方向v 入棧操作入棧操作v 出棧操作出棧操作 .棧底棧底toptopxptop .棧底棧底topqp-next=s-top ; s-top=p q=s-top ; s-top=s-top-next 鏈棧存儲表示及入棧、出棧操作鏈棧存儲表示及入棧、出棧操作Typedef struct Lnode SelemType data; struct Lnode *next;Lnode,*Linkstack;Status push(Linkstack &S,SelemType e) p=(Linkstack)malloc(sizeof(LNode); p-data=e; p-next=S-next

11、;S-next=p;Status pop(Linkstack &S,SelemType &e) if(!S-next)return ERROR; p=S-next;S-next=p-next; e=p-data;free(p); return OK;3.2 棧的應用棧的應用3.2.1 數制轉換數制轉換3.2.2 括號匹配的檢驗括號匹配的檢驗3.2.3 行編輯程序問題行編輯程序問題3.2.4 迷宮求解迷宮求解3.2.5 表達式求值表達式求值3.2.1 數制轉換數制轉換十進制十進制N和其他和其他d進制數的轉換原進制數的轉換原理理: N=( N div d )*d + N mod d 其中：其中：d

12、iv為為整除整除運算，運算，mod為為求余求余運算運算toptop4top40top405 例如：例如： (1348)10=(2504)8，其運算過程如下：，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序top4052 void conversion( ) initstack(S); scanf (“%d”,N); while(N) push(S，N%8); N=N/8; while(! Stackempty(s) pop(S,e); printf(“%d”,e); /conversion#define S

13、TACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0typedef struct int *base; int *top; int stacksize;sqstack;棧使用的完整C程序實例int initstack(sqstackint initstack(sqstack * *s)s) s-base=(int s-base=(int * *)malloc)malloc (STACK_INIT_SIZE (STACK_INIT_SIZE* *sizeof(intsiz

14、eof(int);); s-top=s-base; s-top=s-base; s-stacksize=STACK_INIT_SIZE; s-stacksize=STACK_INIT_SIZE; return OK; return OK; void pop(sqstack void pop(sqstack * *s,ints,int * *e)e) if(s-top=s-base)return ERROR; if(s-top=s-base)return ERROR; * *e=e=* *(-s-top);(-s-top); void push(sqstack void push(sqstack

15、 * *s,ints,int e) e) if(s-top if(s-top- -s-base=s-stacksize)s-base=s-stacksize) s-base=(int s-base=(int* *)realloc(s-base,(s- )realloc(s-base,(s- stacksize+STACKINCREMENT)stacksize+STACKINCREMENT)* *sizeof(intsizeof(int);); if (!s-base)exit(OVERFLOW); if (!s-base)exit(OVERFLOW); s-top=s-base+s-stack

16、size; s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; s-stacksize+=STACKINCREMENT; * *(s-top+)=e;(s-top+)=e; main()() sqstack sqstack s; s; int n,m,e; n,m,e; initstack(&s initstack(&s);); clrscr clrscr(); /(); /清屏幕清屏幕 scanf(“%d(“%d %d”,&n,&m);/n %d”,&n,&m);/n為輸入為輸入數，數，m m為基數為基數 while(n) push(

17、&s,n%m);n=n/m; (n) push(&s,n%m);n=n/m; while(!(s.top=s.base)(!(s.top=s.base) pop(&s,&e); pop(&s,&e); printf(%d,e(%d,e); ); 3.3.2 括號匹配的檢驗括號匹配的檢驗 則則 檢驗括號是否匹配檢驗括號是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”這個概念來描述。這個概念來描述。假設在表達式中假設在表達式中（）或（）或（ ）等為正確的格式，等為正確的格式，（ ）或（）或（ ）或）或 （）（）)均均為不正確的格式。為不正確的格式。分析可能出現的分析可能出現的不匹配不匹

18、配的情況的情況: :到來的括弧到來的括弧并非是所并非是所“期待期待”的；的；例如：例如：考慮下列括號序列：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8直到結束，也沒有到來直到結束，也沒有到來所所“期待期待”的括弧。的括弧。算法的設計思想：算法的設計思想：1）凡出現）凡出現左括左括號號，則，則進棧進棧；2）凡出現）凡出現右括右括號號，首先檢查棧是否空，首先檢查棧是否空 若若棧空棧空，則表明該，則表明該“右括右括號號”多余多余， 否則否則和棧頂元素和棧頂元素比較，比較， 若若相匹配相匹配，則，則“左括左括號號出棧出棧” ， 否則表明否則表明不匹配不匹配。3）表達式檢驗結束時，）表達式

19、檢驗結束時， 若若棧空棧空，則表明表達式中，則表明表達式中匹配正確匹配正確， 否則表明否則表明“左括左括號號”有有多多余余。Status matching(string& exp) int state = 1; while (i - * / ( # =Precede: 判定運算符棧的棧頂運算符判定運算符棧的棧頂運算符1 1與讀入的運算與讀入的運算符符2 2之間的優先關系的函數。之間的優先關系的函數。Operate: 進行二元運算進行二元運算abab的函數的函數. .例：例：3 * ( 7 2 )OPND棧棧OPTR棧棧CCC3*(C7CC2C275C*5315例：例：3 * ( 7 2 ) O

20、PTR棧棧 OPND棧棧 輸入輸入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate

21、( 3, *, 5 )10 # 15 # return GetTop( OPND )OperandType EvaluateExpression() / 設OPTR和OPND分別為運算符棧和運算數棧，OP為運算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是運算符則進棧 else / while return GetTop(OPND);

22、/ EvaluateExpression switch ( precede(GetTop(OPTR), c) case : / 退棧并將運算結果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch*3.3 棧與遞歸的實現棧與遞歸的實現將所有的實在參數、返回地址將所有的實在參數、返回地址等等信息信息傳遞給被調用函數傳遞給被調用函數保存保存；為被調用函數的局部變量為被調用函數的局部變量分配分配存儲區存儲區；將將控制轉移控制轉移到被調用函數的入到被調用函數的入

23、口。口。 當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三項任務：保存保存被調函數的被調函數的計算結果計算結果；釋放釋放被調函數的被調函數的數據區數據區；依照被調函數保存的返回地依照被調函數保存的返回地址將址將控制轉移控制轉移到調用函數。到調用函數。從被調用函數返回返回調用函數之前之前，應該完成下列三項任務：多個函數嵌套調用的規則是：此時的內存管理實行“棧式管理棧式管理”后調用先返回后調用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數據區函數a的數據區函數b的數據區 遞歸

24、工作棧：遞歸工作棧：遞歸過程執行過程中占用的 數據區。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數合成 一個記錄。當前活動記錄：當前活動記錄：棧頂記錄指示當前層的 執行情況。當前環境指針：當前環境指針：遞歸工作棧的棧頂指針。遞歸函數執行的過程可視為同一函數同一函數進行嵌套調用，例如：void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n/ 的n個圓盤按規則搬到塔座z上，y可用作輔助塔座。1 if (n=1)2 move(x, 1, z); / 將編號為的圓盤從x移到z3 else 4 hanoi(n-1, x,

25、z, y); / 將x上編號為至n-1的 /圓盤移到y, z作輔助塔5 move(x, n, z); / 將編號為n的圓盤從x移到z6 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔7 8 8 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z)1 2 if (n=1)3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y,

26、x, z); 8 9 執行函數執行函數hanoi(3,a,b,c) 例：漢諾塔問題：例：漢諾塔問題：將將x柱子上的盤移到柱子上的盤移到 z柱，用柱，用 y柱放臨時盤柱放臨時盤 要求：一次只能移動一個盤，大盤不可放于小盤上要求：一次只能移動一個盤，大盤不可放于小盤上。xyzhanoi塔問題:棧的遞歸實現3.4 隊列隊列3.4.1 隊列的類型定義隊列的類型定義3.4.2 鏈隊列鏈隊列3.4.3 循環隊列循環隊列隊列隊列是限定只能在表的一端進行插入，在是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。表的另一端進行刪除的線性表。a1 a2 a3.an 入隊入隊出隊出隊frontrear隊列

27、隊列Q=(a1,a2,an)v隊列特點：先進先出隊列特點：先進先出( (FIFOFIFO) )3.4.1 隊列的類型定義隊列的類型定義v隊尾隊尾(rear)允許允許插入插入的一端的一端v隊頭隊頭(front)允許允許刪除刪除的一端的一端 ADT Queue 數據對象：數據對象： Dai | aiElemSet, i=1,2,.,n, n0 數據關系：數據關系： R1 | ai-1, ai D, i=2,.,n 約定其中約定其中a1 端為端為隊列頭隊列頭， an 端為端為隊列尾隊列尾基本操作：基本操作：隊列的類型定義 ADT Queue隊列的基本操作：隊列的基本操作： InitQueue(&Q)

28、DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()typedef struct QNode/ 結點類型結點類型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /鏈隊列類型鏈隊列類型 QueuePtr front ; /隊頭指針 QueuePtr rear ; /隊尾指針 LinkQueue;3.4.2 鏈隊

29、列隊列的鏈式表示和實現鏈隊列隊列的鏈式表示和實現a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊列frontrearx入入隊隊xfrontreary入入隊隊xyfrontrearx出出隊隊xyfrontrear空空隊隊front reary出出隊隊Q.rear - next=pQ.rear=pp= Q.front - nextQ.front - next = p - next Status InitQueue (LinkQueue &Q) / 構造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!

30、Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElem

31、Type &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;3.4.3 循環隊列隊列的順序表示和實現循環隊列隊列的順序表示和實現 #define MAXQSIZE 100 /最大隊列長度 typedef struct QElemType *base; / 動態分配存

32、儲空間 int front; / 頭指針，若隊列不空， /指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置 SqQueue;實現：用一維數組實現實現：用一維數組實現sqM123450空隊列空隊列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入隊J4J5J6frontrearrear123450frontJ1,J1,J3入隊rear123450J1,J2,J3出隊J1J2J3frontfrontfrontfrontv存在問題：存在問題：l當當front=0,rear=M時再有元素入隊發生溢出時再有元素入隊發生溢出

33、真溢出真溢出l當當front0,rear=M時再有元素入隊發生溢出時再有元素入隊發生溢出假溢出假溢出rearv解決方案解決方案l隊首固定，每次出隊剩余元素向下移動隊首固定，每次出隊剩余元素向下移動浪浪費時間費時間l循環隊列循環隊列u 基本思想：把隊列基本思想：把隊列設想成環形設想成環形，讓，讓sq0接接在在sqM-1 之后，若之后，若rear+1=M,則令則令rear=0;u實現：利用實現：利用“模模”運算運算u入隊：入隊： baserear=x; rear=(rear+1)%M; u出隊：出隊： x=basefront; front=(front+1)%M; u隊滿、隊空判定條件隊滿、隊空判定條件012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊出隊J7,J8,J9入隊入隊隊空：隊空：front=rearfront=rear隊滿：隊滿：front=rearfront=rear解