數(shù)據(jù)結(jié)構(gòu)課件 棧和隊(duì)列

1、第三章第三章 棧和隊(duì)列棧和隊(duì)列 本章學(xué)習(xí)兩種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它們特殊本章學(xué)習(xí)兩種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它們特殊在定義的操作不同，即插入和刪除操作只能在線在定義的操作不同，即插入和刪除操作只能在線性表的兩端進(jìn)行。性表的兩端進(jìn)行。 只能在一端進(jìn)行的只能在一端進(jìn)行的- 棧棧 分別在兩端進(jìn)行的分別在兩端進(jìn)行的- 隊(duì)列隊(duì)列 重點(diǎn)本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問(wèn)題中正確使用。 知識(shí)點(diǎn) 順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列. 你見(jiàn)過(guò)餐館中一疊一疊的盤子嗎？如果它 們是按1,2,n 的次序往上疊的，那么使用時(shí)候 的次序應(yīng)是什么樣的？. 在日常生活中，為了維持正常的社會(huì)秩序 而出現(xiàn)的常見(jiàn)現(xiàn)象是

2、什么？ 棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作，而隊(duì)列必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。 插 入 刪 除線性表： Insert(L,i,x) Delete(L,i) (1in+1) (1in)棧：Insert(L,n+1,x) Delete(L,n)隊(duì)列：Insert(L,n+1,x) Delete(L,1)第三章第三章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧1 、棧（、棧（stack) ：是一種特殊的線性表（數(shù)：是一種特殊的線性表（數(shù)據(jù)元素之間的關(guān)系是線性關(guān)系），據(jù)元素之間

3、的關(guān)系是線性關(guān)系），其插入、其插入、刪除只能在表的一端進(jìn)行，另一端固定不動(dòng)。刪除只能在表的一端進(jìn)行，另一端固定不動(dòng)。棧頂（棧頂（top ) ：插入、刪除的一端；：插入、刪除的一端；棧底（棧底（bottom ) ：固定不動(dòng)的一端；：固定不動(dòng)的一端；入棧（入棧（push ) ：又稱壓入，即插入一個(gè)元素；：又稱壓入，即插入一個(gè)元素；出棧（出棧（pop) ：又稱彈出，即刪除一個(gè)元素；：又稱彈出，即刪除一個(gè)元素； 一、抽象數(shù)據(jù)類型棧的定義一、抽象數(shù)據(jù)類型棧的定義2 、說(shuō)明：設(shè)（說(shuō)明：設(shè)（a1, a2, a3, , an ） 是一個(gè)棧是一個(gè)棧 （a1, a2, . , ai -1, ai , ai+1,

4、, an ）棧棧底底棧棧頂頂進(jìn)棧進(jìn)棧出棧出棧1）表尾稱為棧頂，表頭稱為棧底）表尾稱為棧頂，表頭稱為棧底 ，即，即a1為棧底元素，為棧底元素，an為棧頂元素為棧頂元素;2）在表尾插入元素的）在表尾插入元素的 操作稱進(jìn)棧操作，在表頭刪除元素的操作稱為操作稱進(jìn)棧操作，在表頭刪除元素的操作稱為出棧操作出棧操作;3）元素按）元素按a1, a2, a3, , an 的次序進(jìn)棧的次序進(jìn)棧, 第一個(gè)進(jìn)棧的元素一定在第一個(gè)進(jìn)棧的元素一定在棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂, 第一個(gè)出棧的元素為棧頂元素；第一個(gè)出棧的元素為棧頂元素；棧的示意圖棧的示意圖棧特點(diǎn)：由于限制了插入刪除只

5、能在一端進(jìn)行，那棧特點(diǎn)：由于限制了插入刪除只能在一端進(jìn)行，那么元素的操作順序有么元素的操作順序有“先進(jìn)后出先進(jìn)后出”或或“后進(jìn)先出后進(jìn)先出”的特點(diǎn)的特點(diǎn)(Last In First out-LIFO First In Last out -FILO ) 第一個(gè)進(jìn)棧的元素在第一個(gè)進(jìn)棧的元素在棧底，最后一個(gè)進(jìn)棧棧底，最后一個(gè)進(jìn)棧的元素在棧頂，第一的元素在棧頂，第一個(gè)出棧的元素為棧頂個(gè)出棧的元素為棧頂元素，最后一個(gè)出棧元素，最后一個(gè)出棧的元素為棧底元素的元素為棧底元素課堂練習(xí)課堂練習(xí)假設(shè)有假設(shè)有A ， B , C , D 四個(gè)元素；它們?nèi)霔４嗡膫€(gè)元素；它們?nèi)霔４涡驗(yàn)樾驗(yàn)锳一一 B 一一C 一一D 出棧

6、次序任意，出棧次序任意，請(qǐng)問(wèn)不可能得到下面哪些出棧序列？請(qǐng)問(wèn)不可能得到下面哪些出棧序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D (5 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D 3 、 棧的基本操作棧的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：構(gòu)造一個(gè)空棧功能：構(gòu)造一個(gè)空棧S； 2） 銷毀棧操作銷毀棧操作DestroyStack(&S) 功能：銷毀一個(gè)已存在的棧功能：銷毀一個(gè)已存在的棧; 3） 置空棧操作置空棧操作Cle

7、arStack(&S) 功能：將棧功能：將棧S置為空棧置為空棧; 4）判空棧操作）判空棧操作StackEmpty(S) 功能：若棧為空棧，返回功能：若棧為空棧，返回TRUE，否則，否則FALSE 5）取長(zhǎng)度操作）取長(zhǎng)度操作StackLength(S) 功能：返回棧功能：返回棧S的元素個(gè)數(shù)的元素個(gè)數(shù) 6）取棧頂元素操作）取棧頂元素操作GetTop(S, &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e 返回返回;7）進(jìn)棧操作）進(jìn)棧操作Push(&S, e)功能：元素功能：元素e進(jìn)棧進(jìn)棧;8）退棧操作）退棧操作Pop(&S, &e) 功能：棧頂元素退棧

8、，并用功能：棧頂元素退棧，并用e返回返回;7）棧遍歷）棧遍歷StackTraverse(S) 功能：從棧底到棧頂依次調(diào)用函數(shù)功能：從棧底到棧頂依次調(diào)用函數(shù)visit().4、棧的ADT描述棧的抽象數(shù)據(jù)類型定義為： ADT Stack 數(shù)據(jù)對(duì)象：Dai|aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1 , ai D, i=2,.,n 約定an端為棧頂,a1端為棧底?；静僮鳎夯静僮鳎? ADT Stack 二 棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)和線性表類似，棧也有兩種存儲(chǔ)表示，其順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧順序棧。和順序表類似，對(duì)順序棧也需要事先為它分配一個(gè)可以容納最多元素的存

9、儲(chǔ)空間。 順序存儲(chǔ)方式：順序存儲(chǔ)方式：同一般線性表的順序存儲(chǔ)結(jié)構(gòu)同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。完全相同。是利用一組連續(xù)的內(nèi)存單元依次存放是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一，棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示個(gè)稱為棧頂指針的變量指示 。 實(shí)際是棧中元素的個(gè)數(shù) 順序棧類型的定義 / 結(jié)構(gòu)定義： typedef struct ElemType *base; / 存儲(chǔ)空間基址 int top; / 棧頂指針 int stacksize; / 允許的最大存儲(chǔ)空間 Stack; 棧頂指針總是指在棧頂元素的后面一個(gè)位置上 top=0

10、123450棧空top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為stacksizetop=0,?？眨藭r(shí)出棧，則下溢（underflow)top= stacksize,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptop特點(diǎn)：簡(jiǎn)單、方便，但易產(chǎn)生溢出。特點(diǎn)：簡(jiǎn)單、方便，但易產(chǎn)生溢出。上溢（上溢（Overflow ) 棧已經(jīng)滿，又要壓入元素；棧已經(jīng)滿，又要壓入元素； 下溢（下溢（Underflow ) 棧已經(jīng)空，還要彈出元素；棧已經(jīng)空，還要彈出元素；注：上溢是一種錯(cuò)誤，使問(wèn)題的處理無(wú)法進(jìn)行下去；注：上溢是一種錯(cuò)誤，使問(wèn)題的處理無(wú)

11、法進(jìn)行下去；而下溢一般認(rèn)為是一種結(jié)束條件，即問(wèn)題處理結(jié)束。而下溢一般認(rèn)為是一種結(jié)束條件，即問(wèn)題處理結(jié)束。# #define STACK_INIT_SIZE 100define STACK_INIT_SIZE 100/棧存儲(chǔ)空間的初始分配量棧存儲(chǔ)空間的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10/ / 棧存儲(chǔ)空間的分配增量棧存儲(chǔ)空間的分配增量typedef structtypedef structSElemType SElemType * *base;base;/棧空間基址?？臻g基址稱為棧底指針，指向棧底位置稱為棧底指針，指向棧

12、底位置SElemType SElemType * *top top /棧頂指針棧頂指針, ,約定棧頂指針指向棧頂元素的約定棧頂指針指向棧頂元素的 /下（后面）一個(gè)位置；下（后面）一個(gè)位置； int stacksize; int stacksize; /當(dāng)前分配的?？臻g大小當(dāng)前分配的棧空間大小 / /（以（以sizeof(SElemType)sizeof(SElemType)為單位為單位） SqStackSqStack;/ ;/ SqStack:：結(jié)構(gòu)類型名結(jié)構(gòu)類型名順序棧的存儲(chǔ)表示順序棧的存儲(chǔ)表示 n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksi

13、zeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作圖示初始化操作圖示順序?；静僮鞯乃惴樞驐；静僮鞯乃惴?）初始化操作）初始化操作InitStack_Sq(SqStack &S) 參數(shù)：參數(shù)：S是存放棧的結(jié)構(gòu)變量；是存放棧的結(jié)構(gòu)變量； 功能：建一個(gè)空棧功能：建一個(gè)空棧S；Status InitStack_Sq(SqStack &S) /構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /為順序棧動(dòng)態(tài)

14、分配存儲(chǔ)空間為順序棧動(dòng)態(tài)分配存儲(chǔ)空間 if (! S. base) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitStack_SqStatus DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; /若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g） free (S.base); / 回收棧空間回收?？臻g S.base = S.top = null; S.stacksize = 0; retu

15、rn OK; / DetroyStack_Sq2） 銷毀棧操作銷毀棧操作 DestroyStack_Sq(SqStack &SSqStack &S ) 功能：銷毀一個(gè)已存在的棧功能：銷毀一個(gè)已存在的棧;S.top = nullS.top = nullS.stacksizeS.stacksizeS.base = nullS.base = null 0 0 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_IN

16、IT_SIZESTACK_INIT_SIZE 銷毀前銷毀前 銷毀后銷毀后銷毀棧操作圖示銷毀棧操作圖示3）置空棧操作置空棧操作ClearStack_Sq(SqStack &S) 功能：將棧功能：將棧S置為空棧置為空棧 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若棧未建立（尚未分若棧未建立（尚未分 /配?？臻g）配?？臻g） S.top = S.base ; return OK; / ClearStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai

17、ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a2 2a a1 1置空棧操作圖示置空棧操作圖示S.base=S.topS.base=S.top表明棧為空表明棧為空置空前置空前置空后置空后Status

18、GetTop_Sq(SqStack S, SelemType &e) / 若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素，并返回/OK；否則返回否則返回ERROR if (S.top= =S.base) return ERROR; /若棧為空若棧為空 e = * (S.top-1); return OK;/GetTop_Sq4） 取棧頂元素操作取棧頂元素操作GetTop_Sq(SqStack S, SElemType &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e返回返回; n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na

19、ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an n 取棧頂元素操作圖示取棧頂元素操作圖示5）進(jìn)棧操作進(jìn)棧操作Push(SqStack &S, SElemType eSqStack &S, SElemType e) 功能：元素功能：元素e 進(jìn)棧進(jìn)棧; 進(jìn)棧操作主要步驟：進(jìn)棧操作主要步驟： 1）S是否已滿，是否已滿， 若若棧棧滿，重新分配存儲(chǔ)空間；滿，重新分配存儲(chǔ)空間； 2）將元素將元素e 寫入棧頂；寫入棧頂； 3）修

20、改棧頂指針，使棧頂指針指向棧頂元素的）修改棧頂指針，使棧頂指針指向棧頂元素的下（后面）一個(gè)位置；下（后面）一個(gè)位置； n nn-1n-1i-1i-1i-2i-2 0 0n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 1anana ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_S

21、IZESTACK_INIT_SIZE e 進(jìn)棧前進(jìn)棧前 e 進(jìn)棧后進(jìn)棧后 進(jìn)棧操作圖示進(jìn)棧操作圖示Status Push(SqStack &S, SElemType e) /將元素將元素e插入棧成為新的棧頂元素插入棧成為新的棧頂元素,要考慮上溢情況要考慮上溢情況 if (S.top-S.base=S.stacksize) /棧滿，追加存儲(chǔ)空間棧滿，追加存儲(chǔ)空間 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) sizeof(ElemType); if (! S. base) exit(OVERFLOW

22、); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /元素元素e 插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針 return OK; /Push進(jìn)棧操作算法：進(jìn)棧操作算法：Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e 返回其值并返回返回其值并返回OK /否則返回否則返回ERROR if (S.top= = S.base) return ERROR; /棧空，返回?？眨祷?/p>

23、ERROR e = * -S.top; /刪除棧頂元素，用刪除棧頂元素，用e 返回其值，并修返回其值，并修 /改棧頂指針改棧頂指針 return OK; /Pop6）出）出棧操作棧操作Pop(SqStack &S, SElemType &e )功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e 返回返回;S.topS.topS.stacksizeS.stacksizeS.baseS.base n nn-1n-1i-1i-1i-2i-2 0 0a an na ai ia ai-1i-1a a1 1STACK_INIT_SIZESTACK_INIT_SIZE 出棧操作前出棧操作前n

24、 nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a1 1 出棧操作后出棧操作后a an ne e出棧操作圖示出棧操作圖示鏈棧鏈棧即為棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鏈棧的結(jié)點(diǎn)結(jié)構(gòu)和單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)相同。由于棧只在棧頂作插入和刪除操作，因此鏈棧中不需要頭結(jié)點(diǎn)，但是鏈棧中指針的方向是從棧頂指向棧底的，這正好和單鏈表是相反的。 鏈棧中結(jié)點(diǎn)的定義： 鏈棧結(jié)構(gòu)定義：typedef struct LNode ElemType

25、 data; struct LNode *next;* SLink;typedef struct SLink top; /棧頂指針 int length; /棧中元素個(gè)數(shù)LStack;鏈棧的基本操作和順序棧操作基本相同，只需修改兩處：初始化時(shí)不需要maxsize的參數(shù)在進(jìn)行入棧操作時(shí)不需要顧忌棧的空間是否已經(jīng)被填滿。void InitStack ( LStack &S ) / 構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧 SS.top = NULL; / 設(shè)棧頂指針的初值為空S.length = 0; / 空棧中元素個(gè)數(shù)為0 / InitStack void Push ( LStack &S, E

26、lemType e )/ 在棧頂之上插入元素在棧頂之上插入元素 e 為新的棧頂元素為新的棧頂元素p = (LNode *)malloc(sizeof(LNode); / 建新的結(jié)點(diǎn)if(!p) exit(1);/ 存儲(chǔ)分配失敗p - data = e;p - next = S.top;/ 鏈接到原來(lái)的棧頂S.top = p; / 移動(dòng)棧頂指針+S.length; / 棧的長(zhǎng)度增1 / Push .棧底toptopxpbool Pop ( LStack &S, ElemType &e ) / 若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用 e 返回其值，返回其值，

27、/ 并返回并返回 TRUE；否則返回；否則返回 FALSEif ( !S.top )return FALSE; else e = S.top - data; / 返回棧頂元素 q = S.top; S.top = S.top - next;/ 修改棧頂指針 -S.length; / 棧的長(zhǎng)度減1 delete q; / 釋放被刪除的結(jié)點(diǎn)空間 return TRUE; / Pop top .棧底topq 小小 結(jié)結(jié) 1.棧是限定僅能在表尾一端進(jìn)行插入、 刪除操作的線性表；2. 棧的元素具有后進(jìn)先出的特點(diǎn)；3. 棧頂元素的位置由一個(gè)稱為棧頂指針的變量表示，進(jìn)棧、出棧操作要修改棧頂指針；3.2 棧的

28、應(yīng)用舉例棧的應(yīng)用舉例 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2輸出順序輸出順序計(jì)算順序計(jì)算順序數(shù)制轉(zhuǎn)換 十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N = (N div d)d + N mod d (其中：div 為整除運(yùn)算，mod 為求余運(yùn)算)例如：(1348)10 = (2504)8 由上述求解過(guò)程可以看出，在計(jì)算過(guò)程中是從低由上述求解過(guò)程可以看出，在計(jì)算過(guò)程中是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而顯示位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而顯示時(shí)按照我們的習(xí)慣是高位

29、在前，低位在后，即按時(shí)按照我們的習(xí)慣是高位在前，低位在后，即按從高位到低位的順序輸出從高位到低位的順序輸出, 即后計(jì)算出的（高）位即后計(jì)算出的（高）位數(shù)先輸出，具有數(shù)先輸出，具有后進(jìn)先出后進(jìn)先出的特點(diǎn)，因此可將計(jì)算的特點(diǎn)，因此可將計(jì)算過(guò)程中得到的八進(jìn)制數(shù)順序進(jìn)棧，出棧序列打印過(guò)程中得到的八進(jìn)制數(shù)順序進(jìn)棧，出棧序列打印輸出的就是對(duì)應(yīng)的八進(jìn)制數(shù)。輸出的就是對(duì)應(yīng)的八進(jìn)制數(shù)。3） 算法算法void conversion( ) /對(duì)于輸入的任意一個(gè)非負(fù)十對(duì)于輸入的任意一個(gè)非負(fù)十/進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); /建空棧建空棧 scan

30、f(“%d”, N); /輸入一個(gè)輸入一個(gè)非負(fù)十進(jìn)制整數(shù)非負(fù)十進(jìn)制整數(shù) while(N) / N不等于零不等于零，循環(huán)，循環(huán) Push(S, N % 8); / N/8第一個(gè)余數(shù)進(jìn)棧第一個(gè)余數(shù)進(jìn)棧 N=N/8 ; /整除運(yùn)算整除運(yùn)算 while(! StackEmpty) /輸出存放在棧中的八進(jìn)制數(shù)。輸出存放在棧中的八進(jìn)制數(shù)。 Pop(S, e); Printf(“%d”, e); /conversion 2 表達(dá)式求值表達(dá)式求值1） 表達(dá)式的構(gòu)成表達(dá)式的構(gòu)成 操作數(shù)操作數(shù)+運(yùn)算符運(yùn)算符+界符（如括號(hào)）界符（如括號(hào)）2） 表達(dá)式的求值：表達(dá)式的求值： 例例 5+6 (1+2)- 4 按照四則運(yùn)

31、算法則，上述表達(dá)式的計(jì)算過(guò)程為：按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表達(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋罕磉_(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋?+ ， ， +， -如何確定運(yùn)算符的運(yùn)算順序？如何確定運(yùn)算符的運(yùn)算順序？3） 算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運(yùn)算符表達(dá)式中任何相鄰運(yùn)算符 1、 2的優(yōu)先關(guān)系有：的優(yōu)先關(guān)系有： 1 2： 1的優(yōu)先級(jí)高于的優(yōu)先級(jí)高于 2 由四則運(yùn)算法則，可得到如下的算符優(yōu)先關(guān)系表：由四則運(yùn)算法則，可得到如下的算符優(yōu)先關(guān)系表：+ 21- -* */ /( () )# #+ - + - *

32、* / ( ) # / ( ) # = = = 算符間的優(yōu)先關(guān)系表算符間的優(yōu)先關(guān)系表注：注： 1 2是相鄰算符，是相鄰算符，1在左在左 2在右在右4) 算符優(yōu)先算法算符優(yōu)先算法 我們?cè)賮?lái)分析一下表達(dá)式我們?cè)賮?lái)分析一下表達(dá)式5+4 (1+2)- 6 計(jì)算過(guò)程：計(jì)算過(guò)程： 從左向右掃描表達(dá)式：從左向右掃描表達(dá)式： 遇操作數(shù)遇操作數(shù)保存；保存；遇運(yùn)算符號(hào)遇運(yùn)算符號(hào) j與前面的剛掃描過(guò)的運(yùn)算符與前面的剛掃描過(guò)的運(yùn)算符 i比較比較 若若 i j 則保存則保存 j，（，（ 因此已保存的運(yùn)算符的優(yōu)先關(guān)系為因此已保存的運(yùn)算符的優(yōu)先關(guān)系為 1 2 3 j 則說(shuō)明則說(shuō)明 i是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)

33、算；是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算； 若若 i = j 則則 i為（，為（， j 為為 ），說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括），說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)；號(hào)； 5+4 (1+2)- 6后面也許有優(yōu)先后面也許有優(yōu)先級(jí)更大的算符級(jí)更大的算符算法思想：(1) 設(shè)置兩個(gè)棧：運(yùn)算符棧（OPTR)和操作數(shù)棧（OPND)(2)設(shè)置數(shù)據(jù)棧為空棧，表達(dá)式起始符“#”為算符棧的棧底元素。(3)自左向右，依次掃描表達(dá)式中的基本符號(hào)，若掃描的基本符號(hào)為操作數(shù)，則將操作數(shù)入OPND棧。(4)若基本符號(hào)為運(yùn)算符，則和OPTR棧頂元素的優(yōu)先級(jí)比較（棧頂元素為C1,讀到的算符為C2）： （a）c

34、1c2，c1出棧，從OPND棧取出兩個(gè)元素（a和b），按c1進(jìn)行運(yùn)算，并把運(yùn)算結(jié)果放入OPND棧。(5)重復(fù)上述過(guò)程，直到表達(dá)式求值完畢（OPTR棧為空棧）表達(dá)式求值示意圖：表達(dá)式求值示意圖：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR棧棧# #OPNDOPND棧棧toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818

35、toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5讀入表達(dá)式過(guò)程：讀入表達(dá)式過(guò)程： + +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+18=235+18=2323-4=1923-4=193.4 棧的應(yīng)用舉例棧的應(yīng)用舉例 在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是OPTR棧，用以保存棧，用以保存運(yùn)算符運(yùn)算符,一個(gè)是一個(gè)是OPND棧，用以保存操作數(shù)或運(yùn)算結(jié)果。棧

36、，用以保存操作數(shù)或運(yùn)算結(jié)果。 operandType EvaluateExpression( ) /算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和和OPND分別為運(yùn)算符棧分別為運(yùn)算符棧和運(yùn)算數(shù)棧，和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。為運(yùn)算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是運(yùn)算符則進(jìn)棧不是運(yùn)算符則進(jìn)棧,In(c, O

37、P)判斷判斷c是否是運(yùn)算符的函數(shù)是否是運(yùn)算符的函數(shù) else 續(xù)續(xù) switch (Precede(GetTop(OPTR), c) case : /新輸入的算符新輸入的算符c優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán)優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán) /高高,出棧并將運(yùn)算結(jié)果入棧出棧并將運(yùn)算結(jié)果入棧OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression3括弧匹配檢驗(yàn) 假設(shè)表達(dá)式中

38、允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯(cuò)誤的匹配。問(wèn)題：如何檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？解決辦法：用期待的急迫程度這個(gè)概念來(lái)描述。 對(duì)于后出現(xiàn)的左括號(hào),它等待與其匹配的右括號(hào)出 現(xiàn)的急迫心情要比先出現(xiàn)的左括號(hào)高,也就是說(shuō),對(duì) 左括號(hào)來(lái)說(shuō),后出現(xiàn)的比先出現(xiàn)的優(yōu)先等待檢測(cè). 對(duì)右括號(hào)來(lái)說(shuō),每個(gè)出現(xiàn)的右括號(hào)要去找在它之前最后出現(xiàn)的那個(gè)左括號(hào)去匹配.例如考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8顯然,必須將先后出現(xiàn)的左括號(hào)依次保存,為了反映這個(gè)優(yōu)先程度,保存左括號(hào)的結(jié)構(gòu)應(yīng)該使用棧 對(duì)

39、于出現(xiàn)的右括號(hào)來(lái)說(shuō),只要棧頂元素相匹配即可.如果棧頂?shù)淖罄ㄌ?hào)正好和它匹配,就可將它從棧頂刪除.什么樣的情況是“不匹配”的情況呢？1和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?棧中并沒(méi)有左括弧等在那里；3棧中還有左括弧沒(méi)有等到和它相匹配的右括弧。Bool match()InitStack(S); /初始化棧初始化棧 ch=getchar(); /接收第一個(gè)括號(hào)接收第一個(gè)括號(hào) while(ch!=#) /不是結(jié)束符不是結(jié)束符 if(ch=(|ch=) /左括號(hào)時(shí)進(jìn)棧左括號(hào)時(shí)進(jìn)棧 push(S,ch); /if else if(ch=) /) 時(shí)檢測(cè)匹配時(shí)檢測(cè)匹配 if(!StackEmpty(S) gettop(S

40、,e); /取棧頂元素取棧頂元素 if(e=() /匹配成功匹配成功 pop(S); /if else return false; /匹配失敗匹配失敗 /if /elseElse /時(shí)檢測(cè)匹配時(shí)檢測(cè)匹配 if(!StackEmpty(S) gettop(S,e); /取棧頂元素取棧頂元素 if(e=) /匹配成功匹配成功 pop(S); /if else return false; /匹配失敗匹配失敗 /if /else ch=getchar();/whileIf(!StackEmpty(S) return false; /棧中還有沒(méi)有匹配棧中還有沒(méi)有匹配 /成功的左括號(hào)成功的左括號(hào) else

41、 return true;/match算法實(shí)現(xiàn)算法實(shí)現(xiàn)4.迷宮求解問(wèn)題計(jì)算機(jī)解迷宮時(shí)，通常用的是“窮舉求解窮舉求解”的方法. 1進(jìn)入迷宮之后，不管在迷宮的哪一個(gè)位置上，都先往東走，如果走得通就繼續(xù)往東走，如果在某個(gè)位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個(gè)走得通的方向繼續(xù)往前直到出口為止；2如果某個(gè)位置上四個(gè)方向都走不通的話，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒(méi)有方向可試了就再退一步，如果所有已經(jīng)走過(guò)的位置的四個(gè)方向都試探過(guò)了，一直退到起始點(diǎn)都沒(méi)有走通，那就說(shuō)明這個(gè)迷宮根本不通； 為了保證在任何位置上都能沿原路退回，需要用 一個(gè)“后進(jìn)先出”的結(jié)構(gòu)即棧來(lái)保存從

42、入口到當(dāng)前 位置的路徑。并且在走出出口之后，棧中保存的 正是一條從入口到出口的路徑。算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索；若當(dāng)前位置“不可通”，則應(yīng)順著“來(lái)的方向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。 偽碼算法 ：設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； / 納入路徑 若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則 若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為

43、: 沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置； / 從路徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?； while (棧不空)； 沒(méi)有路徑存在3.3 棧與遞歸 由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過(guò)程具有后由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過(guò)程具有后進(jìn)先出的特性，可利用棧來(lái)實(shí)現(xiàn)數(shù)據(jù)處理過(guò)程。下進(jìn)先出的特性，可利用棧來(lái)實(shí)現(xiàn)數(shù)據(jù)處理過(guò)程。下面我們將看到可以用棧來(lái)實(shí)現(xiàn)遞歸。面我們將看到可以用棧來(lái)實(shí)現(xiàn)遞歸。1什么是遞歸什么是遞歸 遞歸是一個(gè)很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多遞歸是一個(gè)很有用的工具，在數(shù)學(xué)和程

44、序設(shè)計(jì)等許多領(lǐng)域中都用到了遞歸。遞歸定義：簡(jiǎn)單地說(shuō)，一個(gè)領(lǐng)域中都用到了遞歸。遞歸定義：簡(jiǎn)單地說(shuō)，一個(gè)用自己定義自己的概念用自己定義自己的概念,稱為遞歸定義。稱為遞歸定義。例例 n!= 1 2 3 4 (n-1) n n!遞歸定義遞歸定義 n!= 1 當(dāng)當(dāng) n=0時(shí)時(shí) n!= n (n-1)! 當(dāng)當(dāng)n 0時(shí)時(shí)用(n-1)!定義n!棧與遞歸2.遞歸函數(shù)遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過(guò)一系列調(diào)用：一個(gè)直接調(diào)用自己或通過(guò)一系列調(diào)用間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接調(diào)用自己直接調(diào)用自己B間接調(diào)用自

45、己間接調(diào)用自己棧與遞歸遞歸是程序設(shè)計(jì)中的有用工具，下面舉例說(shuō)明遞歸算法的編寫遞歸是程序設(shè)計(jì)中的有用工具，下面舉例說(shuō)明遞歸算法的編寫和執(zhí)行過(guò)程。和執(zhí)行過(guò)程。2遞歸算法的編寫遞歸算法的編寫1）將問(wèn)題用遞歸的方式描述（定義）將問(wèn)題用遞歸的方式描述（定義）2）根據(jù)問(wèn)題的遞歸描述（定義）編寫遞歸算法）根據(jù)問(wèn)題的遞歸描述（定義）編寫遞歸算法 問(wèn)題的遞歸描述（定義）問(wèn)題的遞歸描述（定義） 遞歸定義包括兩項(xiàng)遞歸定義包括兩項(xiàng) 基本項(xiàng)（終止項(xiàng)）基本項(xiàng)（終止項(xiàng)）：描述遞歸終止時(shí)問(wèn)題的求解；：描述遞歸終止時(shí)問(wèn)題的求解； 遞歸項(xiàng)：遞歸項(xiàng)：將問(wèn)題分解為與原問(wèn)題性質(zhì)相同，但規(guī)模較小將問(wèn)題分解為與原問(wèn)題性質(zhì)相同，但規(guī)模較小

46、的問(wèn)題；的問(wèn)題； 棧與遞歸棧與遞歸例例1 編寫求解編寫求解 階乘階乘n! 的遞歸算法的遞歸算法首先給出階乘首先給出階乘n! 的遞歸定義的遞歸定義 n!的遞歸定義的遞歸定義 基本項(xiàng)：基本項(xiàng)： n!=1 當(dāng)當(dāng) n=1 遞歸項(xiàng)：遞歸項(xiàng)： n!=n (n-1)! 當(dāng)當(dāng) n 1 有了問(wèn)題的遞歸定義，很容易寫出對(duì)應(yīng)的遞歸算法：有了問(wèn)題的遞歸定義，很容易寫出對(duì)應(yīng)的遞歸算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 If（n=1） return（1）；）； Else return（n*fact (n-1)）；）；/fact 棧與遞歸棧與遞歸例例2. 編寫求解編

47、寫求解Hanoi塔問(wèn)題的遞歸算法塔問(wèn)題的遞歸算法 有三個(gè)各為有三個(gè)各為X，Y，Z的塔座，在的塔座，在X項(xiàng)有項(xiàng)有n個(gè)大小不個(gè)大小不同，依小到大編號(hào)為同，依小到大編號(hào)為1，2n的圓盤。的圓盤。 現(xiàn)要求將現(xiàn)要求將X上上的的n個(gè)圓盤移至個(gè)圓盤移至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放， 圓盤移動(dòng)圓盤移動(dòng)時(shí)必須遵守下列原則：時(shí)必須遵守下列原則：1）每次移動(dòng)一個(gè)盤子；）每次移動(dòng)一個(gè)盤子；2）圓盤可以放在）圓盤可以放在X，Y，Z中的任一塔座上；中的任一塔座上；3）任何時(shí)刻都不能將較大的圓盤壓放在較小圓盤之上；）任何時(shí)刻都不能將較大的圓盤壓放在較小圓盤之上；例例 n=3時(shí)圓盤移動(dòng)的過(guò)程如下圖所示時(shí)圓

48、盤移動(dòng)的過(guò)程如下圖所示：abc321 11213121棧與遞歸棧與遞歸Y YX XZ Z棧與遞歸棧與遞歸首先給出求解首先給出求解Hanoi塔問(wèn)題塔問(wèn)題 的遞歸描述（定義）的遞歸描述（定義） 基本項(xiàng)：基本項(xiàng)： n=1時(shí)，將時(shí)，將n號(hào)圓盤從號(hào)圓盤從X移至移至Z； 遞歸項(xiàng)：遞歸項(xiàng)： n1時(shí)，時(shí)， 將將X上上1n-1號(hào)圓盤移至號(hào)圓盤移至Y； 將將X上的上的n號(hào)圓盤從號(hào)圓盤從X移至移至Z; 將將Y上上1n-1號(hào)圓盤從號(hào)圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的的問(wèn)題的求解歸問(wèn)題的求解歸結(jié)為規(guī)模為結(jié)為規(guī)模為n-n-1 1的問(wèn)題的求的問(wèn)題的求解解有了問(wèn)題的遞歸定義，很容易寫出對(duì)應(yīng)的遞歸有了問(wèn)題的遞歸定義

49、，很容易寫出對(duì)應(yīng)的遞歸算法：算法：void hanoi (int n, char x, char y, char z) /將塔座將塔座x上按直徑由小到大且自上而下編號(hào)為上按直徑由小到大且自上而下編號(hào)為1至至n的的n個(gè)圓盤按規(guī)則搬到塔座個(gè)圓盤按規(guī)則搬到塔座z上，上，y可用作輔助塔座。可用作輔助塔座。 if (n= =1) move(x,1,z); /將編號(hào)為將編號(hào)為1的圓盤從的圓盤從x移動(dòng)移動(dòng)z else hanoi(n-1, x, z, y); /將將x上編號(hào)為上編號(hào)為1至至n-1的圓盤移到的圓盤移到y(tǒng), z作輔助塔作輔助塔 move(x, n, z); /將編號(hào)為將編號(hào)為 n的圓盤從的圓盤從

50、x移到移到z hanoi(n-1, y, x, z)； /將將y上編號(hào)為上編號(hào)為1至至n-1的圓盤移到的圓盤移到z，x作輔助塔作輔助塔 棧與遞歸棧與遞歸3 遞歸函數(shù)的實(shí)現(xiàn)遞歸函數(shù)的實(shí)現(xiàn)先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。 A( )B( );C( )B( )C( );調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序 A B C函數(shù)返回順序 C B A后調(diào)用的函數(shù)先返回后調(diào)用的函數(shù)先返回 函數(shù)調(diào)用機(jī)制可通過(guò)棧來(lái)實(shí)現(xiàn)函數(shù)調(diào)用機(jī)制可通過(guò)棧來(lái)實(shí)現(xiàn)計(jì)算機(jī)正是利用棧來(lái)實(shí)現(xiàn)函計(jì)算機(jī)正是利用棧來(lái)實(shí)現(xiàn)函數(shù)的調(diào)用和返回的數(shù)的調(diào)用和返回的棧與遞歸棧與遞歸我們看一下我們看一下n=3 n=3 階乘函數(shù)階乘函數(shù)

51、fact(n)fact(n)的執(zhí)行過(guò)程的執(zhí)行過(guò)程Main( ) int n=3,y;L y= fact(n);調(diào)調(diào)用用調(diào)用調(diào)用int fact (n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=3int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=2int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=1L 3L 3L1 1L1 1L1 2L1 2

52、返回1 1返回2 2返返回回6 61 1n*fact (n-1)n*fact (n-1)fact(n)返回地址 實(shí)參 注意遞歸調(diào)用中 棧的變化2 、隊(duì)列的特點(diǎn)：由于限制了插入、刪除分別在兩端進(jìn)行，、隊(duì)列的特點(diǎn)：由于限制了插入、刪除分別在兩端進(jìn)行，那么元素的操作順序有那么元素的操作順序有“先進(jìn)先出先進(jìn)先出”或或“后進(jìn)后出后進(jìn)后出”的特點(diǎn)的特點(diǎn)（First In First Out-FIFO Last In Last Out - LILO） 1 、隊(duì)列（、隊(duì)列（Queue ) ：是一種特殊的線性表是一種特殊的線性表(數(shù)據(jù)元數(shù)據(jù)元 之間的關(guān)系是線性關(guān)系之間的關(guān)系是線性關(guān)系.其插入、刪除分別在表的其插

53、入、刪除分別在表的兩端進(jìn)行，一端只能插入、另一端只能刪除。兩端進(jìn)行，一端只能插入、另一端只能刪除。)隊(duì)首（隊(duì)首（front ) ：進(jìn)行刪除的一端；：進(jìn)行刪除的一端；隊(duì)尾（隊(duì)尾（rear ) ：進(jìn)行插入的一端；：進(jìn)行插入的一端；入隊(duì)：在隊(duì)尾插入一個(gè)元素；入隊(duì)：在隊(duì)尾插入一個(gè)元素；出隊(duì)：在隊(duì)首刪除一個(gè)元素；出隊(duì)：在隊(duì)首刪除一個(gè)元素；3.4隊(duì)列3.4.13.4.1抽象數(shù)據(jù)類型隊(duì)列的定義抽象數(shù)據(jù)類型隊(duì)列的定義 a1 a2 a3 an入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列隊(duì)列的示意圖隊(duì)列的示意圖隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)先進(jìn)先出先進(jìn)先出第一個(gè)入隊(duì)的元素在隊(duì)頭，第一個(gè)入隊(duì)的元素在隊(duì)頭，最后一個(gè)入隊(duì)的元素在隊(duì)尾，最后一個(gè)入隊(duì)的元素

54、在隊(duì)尾，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，最后一個(gè)出隊(duì)的元素為隊(duì)尾元素最后一個(gè)出隊(duì)的元素為隊(duì)尾元素 隊(duì)列類似于日常的排隊(duì)，新來(lái)的人站在隊(duì)尾，隊(duì)頭的人進(jìn)隊(duì)列類似于日常的排隊(duì)，新來(lái)的人站在隊(duì)尾，隊(duì)頭的人進(jìn)行事務(wù)處理后離隊(duì)。行事務(wù)處理后離隊(duì)。 隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾元素隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾元素的位置，這兩個(gè)變量分別稱為隊(duì)頭指針、隊(duì)尾指針；的位置，這兩個(gè)變量分別稱為隊(duì)頭指針、隊(duì)尾指針；2. 隊(duì)列的基本操作隊(duì)列的基本操作1）初始化操作）初始化操作InitQueue( &Q) 功能：構(gòu)造一個(gè)空隊(duì)列功能：構(gòu)造一個(gè)空隊(duì)列Q；2）銷

55、毀操作銷毀操作DestroyQueue( &Q) 功能：銷毀已存在隊(duì)列功能：銷毀已存在隊(duì)列Q；3）置空操作置空操作ClearQueue(&Q) 功能：功能： 將隊(duì)列將隊(duì)列Q置為空隊(duì)列置為空隊(duì)列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若隊(duì)列功能：若隊(duì)列Q為空，則返回為空，則返回True，否則返回否則返回False； 5）取隊(duì)頭元素操作取隊(duì)頭元素操作GetHead(Q,&e) 功能：取隊(duì)頭元素，并用功能：取隊(duì)頭元素，并用e返回；返回；6）入隊(duì)操作入隊(duì)操作EnQueue( &Q, e ) 功能：將元素功能：將元素e插入插入Q的隊(duì)尾；的隊(duì)尾；7）出隊(duì)

56、操作）出隊(duì)操作DeQueue( &Q, &e) 功能：若隊(duì)列不空，則刪除功能：若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用的隊(duì)頭元素，用e返返回其值，并返回回其值，并返回OK，否則返回否則返回ERROR；隊(duì)列的抽象數(shù)據(jù)類型定義： ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：Dai|aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 | ai-1,ai D, i=2,.,n約定其中a1端為隊(duì)列頭，an端為隊(duì)列尾基本操作： InitQueue(&Q) DestroyQueue(&Q) ClearQueue(&Q)QueueEmpty(Q)Queue

57、Length(Q)GetHead(Q,&e)EnQueue(&Q,e) DeQueue(&Q,&e)QueueTraverse(Q,visit( ) ADT Queue 3.隊(duì)列隊(duì)列ADT應(yīng)用舉例應(yīng)用舉例 打印機(jī)隊(duì)列管理：打印機(jī)隊(duì)列管理：在一臺(tái)打印機(jī)共享使用時(shí)，任何在一臺(tái)打印機(jī)共享使用時(shí)，任何時(shí)刻它只能處理一個(gè)用戶的打印請(qǐng)求。打印任務(wù)的組時(shí)刻它只能處理一個(gè)用戶的打印請(qǐng)求。打印任務(wù)的組織就用一個(gè)隊(duì)列來(lái)組織（先請(qǐng)求的，先處理）?？椌陀靡粋€(gè)隊(duì)列來(lái)組織（先請(qǐng)求的，先處理）。當(dāng)用戶發(fā)出打印請(qǐng)求時(shí)，把打印任務(wù)當(dāng)用戶發(fā)出打印請(qǐng)求時(shí)，把打印任務(wù)入隊(duì)入隊(duì)；當(dāng)打印機(jī)空閑時(shí)，從打印隊(duì)

58、列中當(dāng)打印機(jī)空閑時(shí)，從打印隊(duì)列中出隊(duì)出隊(duì)一個(gè)任務(wù)；一個(gè)任務(wù)；當(dāng)打印機(jī)阻塞時(shí)當(dāng)打印機(jī)阻塞時(shí),系統(tǒng)管理員可以系統(tǒng)管理員可以清空隊(duì)列清空隊(duì)列.1 、存儲(chǔ)方式：同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全、存儲(chǔ)方式：同一般線性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。但是由于在兩端操作，設(shè)兩個(gè)指示器，相同。但是由于在兩端操作，設(shè)兩個(gè)指示器，(rear 和和front ）分別指示隊(duì)列的尾和首。）分別指示隊(duì)列的尾和首。特別約定特別約定:頭指針始終指向隊(duì)列頭元素，而尾指針頭指針始終指向隊(duì)列頭元素，而尾指針 始終指向始終指向 隊(duì)列尾元素的下一位置！隊(duì)列尾元素的下一位置！ 空隊(duì)列：空隊(duì)列：rear = front = 0 入隊(duì)：入隊(duì)：rea

59、r =rear + 1 出隊(duì)：出隊(duì)：front = front + 1 隊(duì)列空：隊(duì)列空：front = rear 3.4.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)特點(diǎn):簡(jiǎn)單簡(jiǎn)單,方便方便,但是易產(chǎn)生但是易產(chǎn)生假假 溢出溢出.只是稱為指針，實(shí)現(xiàn)時(shí)不一定用指針變量2.隊(duì)列的簡(jiǎn)單操作的實(shí)現(xiàn)隊(duì)列的簡(jiǎn)單操作的實(shí)現(xiàn)(1）初始化）初始化 Q .front = Q.rear =0 ;(2）入隊(duì)）入隊(duì)Q .baseQ .reare ; Q .rear + + ;(3）出隊(duì)）出隊(duì)Q .front + + ;(4）判空）判空Q .front = = Q .rear ;(5）求隊(duì)長(zhǎng)）求隊(duì)長(zhǎng)Q .rear-Q .front思考：順序

60、隊(duì)列存在的問(wèn)題及解決方案思考：順序隊(duì)列存在的問(wèn)題及解決方案可以看出：當(dāng)入隊(duì)一個(gè)元素時(shí)，可能會(huì)出現(xiàn)假可以看出：當(dāng)入隊(duì)一個(gè)元素時(shí)，可能會(huì)出現(xiàn)假溢出現(xiàn)象溢出現(xiàn)象.即：空間并沒(méi)有使用完，但不能入隊(duì)！即：空間并沒(méi)有使用完，但不能入隊(duì)！解決的辦法：解決的辦法：( 1 ）平移，一旦發(fā)生假溢出，把隊(duì)列）平移，一旦發(fā)生假溢出，把隊(duì)列中所有元素移到隊(duì)列開(kāi)頭效率低中所有元素移到隊(duì)列開(kāi)頭效率低( 2 ）使用動(dòng)態(tài)數(shù)組，當(dāng)產(chǎn)生假溢出或）使用動(dòng)態(tài)數(shù)組，當(dāng)產(chǎn)生假溢出或真溢出時(shí)，都重新分配一個(gè)更大的空真溢出時(shí)，都重新分配一個(gè)更大的空間（不可?。╅g（不可?。? 3 ）使用環(huán)數(shù)組，即將順序存儲(chǔ)的空）使用環(huán)數(shù)組，即將順序存儲(chǔ)的空間視為一個(gè)環(huán)空間。間視為一個(gè)環(huán)空間。3.4.3 循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn) 方式：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，如方式：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，如圖所示，稱之為循環(huán)隊(duì)列圖所示，稱之為循環(huán)隊(duì)列.指針和隊(duì)列元素之間指針和隊(duì)列元素之間的關(guān)系不變的關(guān)系不變這種循環(huán)的圈只是一這種循環(huán)的圈只是一種邏輯上的圈種邏輯上的圈,在物理在物