數(shù)據(jù)結(jié)構(gòu) 第三章棧隊列

1、第三章第三章 棧和隊列棧和隊列 本章介紹在程序設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu)本章介紹在程序設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu) 棧和隊列棧和隊列 第三章第三章 棧和隊列棧和隊列 3.1 3.1 棧棧 3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 3.3 棧與遞歸棧與遞歸 3.4 3.4 隊列隊列 3.1 3.1 棧棧3.13.1 .1 .1 棧的概念棧的概念3.13.1 .2 .2 棧的順序存儲和實現(xiàn)棧的順序存儲和實現(xiàn)3.13.1 .3 .3 棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)3.1 棧棧棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表（a1, a2, .

2、, ai -1, ai , ai+1, , an ）插入插入刪除刪除3.1.1棧的定義和抽象數(shù)據(jù)類型棧的定義和抽象數(shù)據(jù)類型一一 什么是棧什么是棧說明：設(shè)（說明：設(shè)（a1, a2, a3, , an ） 是一個棧是一個棧 1）表尾稱為棧頂，表頭稱為棧底）表尾稱為棧頂，表頭稱為棧底 ，即，即a1為棧底元素，為棧底元素，an為為 棧頂元素；棧頂元素； 2）在表尾插入元素的）在表尾插入元素的 操作稱進(jìn)棧操作，在表尾刪除元素操作稱進(jìn)棧操作，在表尾刪除元素 的操作稱為出棧操作的操作稱為出棧操作; 3）元素按）元素按a1, a2, a3, , an 的次序進(jìn)棧的次序進(jìn)棧, 第一個進(jìn)棧的元素第一個進(jìn)棧的元素

3、一定在棧底，最后一個進(jìn)棧的元素一定在棧頂一定在棧底，最后一個進(jìn)棧的元素一定在棧頂, 第一個第一個 出棧的元素為棧頂元素；出棧的元素為棧頂元素； 4）棧的元素具有后進(jìn)先出的特點）棧的元素具有后進(jìn)先出的特點,所以棧又稱為后進(jìn)先出所以棧又稱為后進(jìn)先出 表（表（LIFO表）；表）； 5）由于進(jìn)棧、出棧操作總是在棧頂一端進(jìn)行，通常設(shè)置稱）由于進(jìn)棧、出棧操作總是在棧頂一端進(jìn)行，通常設(shè)置稱 為棧頂指針的變量為棧頂指針的變量(Top)指示棧頂?shù)奈恢谩Ｖ甘緱ｍ數(shù)奈恢?。棧棧底底棧棧頂頂（a1, a2, . , ai -1, ai , ai+1, , an ）進(jìn)棧進(jìn)棧出棧出棧棧的示意圖棧的示意圖出棧出棧進(jìn)棧進(jìn)棧棧的

4、特點棧的特點后進(jìn)先出后進(jìn)先出第一個進(jìn)棧的元素在棧底，第一個進(jìn)棧的元素在棧底，最后一個進(jìn)棧的元素在棧頂，最后一個進(jìn)棧的元素在棧頂，第一個出棧的元素為棧頂元素，第一個出棧的元素為棧頂元素，最后一個出棧的元素為棧底元素最后一個出棧的元素為棧底元素棧頂棧頂棧底棧底a an na a2 2a a1 1二二 棧的基本操作棧的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：構(gòu)造一個空棧功能：構(gòu)造一個空棧S； 2） 銷毀棧操作銷毀棧操作DestroyStack(&S) 功能：銷毀一個已存在的棧功能：銷毀一個已存在的棧; 3） 置空棧操作置空棧操作ClearStack(&a

5、mp;S) 功能：將棧功能：將棧S置為空棧置為空棧; 4） 取棧頂元素操作取棧頂元素操作GetTop(S, &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e 返回返回; 5）進(jìn)棧操作）進(jìn)棧操作Push(&S, e) 功能：元素功能：元素e進(jìn)棧進(jìn)棧; 6）退棧操作）退棧操作Pop(&S, &e) 功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e返回返回; 7）判空操作）判空操作StackEmpty(S) 功能：若棧功能：若棧S為空，則返回為空，則返回True，否則返回否則返回False;toptopbasebasebasebasetoptopbasebas

6、etoptopbasebasetoptopA AA AB BC CD DE EA AB B 棧操作圖示棧操作圖示空棧空棧 A A進(jìn)棧進(jìn)棧 B C D E B C D E 進(jìn)棧進(jìn)棧E D C E D C 出棧出棧 棧的順序存儲結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元棧的順序存儲結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個稱為棧頂指針的變量指示置由一個稱為棧頂指針的變量指示 。 棧的順序存貯結(jié)構(gòu)也稱為順序棧。棧的順序存貯結(jié)構(gòu)也稱為順序棧。3.1.2 棧的順序存儲和實現(xiàn)棧的順序存儲和實現(xiàn) 與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)

7、構(gòu)存儲。與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)構(gòu)存儲。一、棧的順序存儲結(jié)構(gòu)一、棧的順序存儲結(jié)構(gòu) 1 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)SqStack：結(jié)構(gòu)類型名；結(jié)構(gòu)類型名；SqStack類型的變量是結(jié)構(gòu)變量，它的三個域類型的變量是結(jié)構(gòu)變量，它的三個域 分別是：分別是： base：稱為棧底指針，指向棧底位置；稱為棧底指針，指向棧底位置； top： 稱為棧頂指針，約定棧頂指針指向棧頂元素的下（后面）一稱為棧頂指針，約定棧頂指針指向棧頂元素的下（后面）一 個位置；個位置； Stacksize：用于存放當(dāng)前分配（存放用于存放當(dāng)前分配（存放棧棧元素）的存儲空間的大??；元素）的存儲空間的大??；# #define

8、 STACK_INIT_SIZE 100 / define STACK_INIT_SIZE 100 / 棧存儲空間的初始分配量棧存儲空間的初始分配量# #define STACKINCREMENT 10 / define STACKINCREMENT 10 / 棧存儲空間的分配增量棧存儲空間的分配增量typedeftypedef structstruct SElemTypeSElemType * *base; /base; /?？臻g基址棧空間基址SElemTypeSElemType * *top /top /棧頂指針棧頂指針intint stacksizestacksize; /; /當(dāng)前分配

9、的?？臻g大小當(dāng)前分配的?？臻g大小 / /（以（以sizeof(SElemTypesizeof(SElemType) )為單位）為單位） SqStackSqStack; ;2 順序棧的類型定義順序棧的類型定義3 順序棧的圖示順序棧的圖示a an na ai 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 0當(dāng)棧用順序結(jié)構(gòu)存儲時，當(dāng)棧用順序結(jié)構(gòu)存儲時，棧的基本操作如建空棧、棧的基本操作如建空棧、進(jìn)棧

10、、出棧等操作如何實現(xiàn)？進(jìn)棧、出棧等操作如何實現(xiàn)？二二 順序棧基本操作的算法順序?；静僮鞯乃惴?）初始化操作）初始化操作InitStack_Sq(SqStack &S) 參數(shù)：參數(shù)：S是存放棧的結(jié)構(gòu)變量；是存放棧的結(jié)構(gòu)變量； 功能：建一個空棧功能：建一個空棧S； 算法算法Status InitStack_Sq(SqStack &S) /構(gòu)造一個空棧構(gòu)造一個空棧S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /為順序棧動態(tài)分配存儲空間為順序棧動態(tài)分配存儲空間 if (! S. base) exi

11、t(OVERFLOW); /存儲分配失敗存儲分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作圖示初始化操作圖示 初始化操作圖示初始化操作圖示算法算法Status DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若

12、棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g） free (S.base); / 回收棧空間回收?？臻g S.base = S.top = null; S.stacksize = 0; return OK;/ DetroyStack_Sq2） 銷毀棧操作銷毀棧操作 DestroyStack_Sq(SqStackSqStack &S &S ) 功能：銷毀一個已存在的棧功能：銷毀一個已存在的棧;S.top =nullS.top =nullS.stacksizeS.stacksizeS.base =nullS.base =null 0 0 n nn-1n-1i-1i-1i-2i

13、-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE 銷毀前 銷毀后銷毀棧操作圖示3）置空棧操作置空棧操作ClearStack_Sq(SqStack &S) 功能：將棧功能：將棧S置為空棧置為空棧 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g） S.to

14、p = S.base ; return OK; / ClearStack_Sq 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_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-

15、1a a2 2a a1 1置空棧操作圖示置空棧操作圖示S.base=S.topS.base=S.top表明棧為空表明棧為空置空前置空前置空后置空后 算法算法Status 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,

16、SElemType &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e返回返回; 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_INIT_SIZESTACK_INIT_SIZEe ea an n 取棧頂元素操作圖示取棧頂元素操作圖示n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZ

17、ESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 15）進(jìn)棧操作進(jìn)棧操作Push(SqStackSqStack &S, &S, SElemTypeSElemType e e) 功能：元素功能：元素e 進(jìn)棧進(jìn)棧; 進(jìn)棧操作主要步驟：進(jìn)棧操作主要步驟： 1）S是否已滿，是否已滿， 若若棧棧滿，重新分配存儲空間；滿，重新分配存儲空間； 2）將元素將元素e 寫入棧頂；寫入棧頂； 3）修改棧頂指針，使棧頂指針指向棧頂元素）修改棧頂指針，使棧頂指針指向棧頂元素 的下（后面）一個位置；的下（后面）一個位置； n nn-1n-1i-1i-1i-2i-2

18、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 1a an na ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE e 進(jìn)棧前進(jìn)棧前 e 進(jìn)棧后進(jìn)棧后 進(jìn)棧操作圖示進(jìn)棧操作圖示進(jìn)棧操作算法：進(jìn)棧操作算法：Status Push(SqSt

19、ack &S, SElemType e) /將元素將元素e插入棧成為新的棧頂元素插入棧成為新的棧頂元素 if (S.top-S.base=S.stacksize) /棧滿，追加存儲空間棧滿，追加存儲空間 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) *sizeof(ElemType); if (! S. base) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+

20、=e; /元素元素e 插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針 return OK;/Push6）出）出棧操作棧操作Pop(SqStack &S, SElemType &e )功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e 返回返回;出棧操作基本步驟出棧操作基本步驟算法算法Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e 返回其值，并返回返回其值，并返回OK； /否則返回否則返回ERROR if (S.top= = S.base) return ERROR; /棧

21、空，返回?？?，返回ERROR e = * -S.top; /刪除棧頂元素，用刪除棧頂元素，用e 返回其值，并修改棧頂指針返回其值，并修改棧頂指針 return OK;/PopS.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 nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stac

22、ksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an-1n-1a ai ia ai-1i-1a a1 1e ea an n 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱鏈棧，棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱鏈棧，如圖所示：如圖所示：Data nextData nextS S棧頂棧頂棧底棧底a an-1n-1a a1 1a an n3.1.3 3.1.3 棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)說明說明 1）鏈?zhǔn)綏？捎镁€性鏈表表示；）鏈?zhǔn)綏？捎镁€性鏈表表示； 2）鏈?zhǔn)綏５臈ｍ斨羔樉褪擎湵淼念^指針；）鏈?zhǔn)綏５臈ｍ斨羔樉褪擎湵淼念^指針； 3）進(jìn)棧操作就是在該線性鏈表第一個元素）進(jìn)棧操作

23、就是在該線性鏈表第一個元素 結(jié)點之前插入一個新結(jié)點，出棧操作就是結(jié)點之前插入一個新結(jié)點，出棧操作就是 刪除鏈表的第一個元素結(jié)點。刪除鏈表的第一個元素結(jié)點。 在前面學(xué)習(xí)了線性鏈表的插入刪除操作在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法。大家不妨試一試。等操作的算法。大家不妨試一試。鏈?zhǔn)綏D示鏈?zhǔn)綏D示Data nextData nextS S棧頂棧頂棧底棧底a an-1n-1a a1 1a an n 小小 結(jié)結(jié) 1 棧是限定僅能在表尾一端進(jìn)行插入、刪除棧是限定僅能在表尾一端進(jìn)行插入、刪除 操作的線性表；操作的線性表；

24、 2 棧的元素具有后進(jìn)先出的特點；棧的元素具有后進(jìn)先出的特點； 3 棧頂元素的位置由一個稱為棧頂指針的變棧頂元素的位置由一個稱為棧頂指針的變 指示，進(jìn)棧、出棧操作要修改棧頂指針；指示，進(jìn)棧、出棧操作要修改棧頂指針； 3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 棧結(jié)構(gòu)具有后進(jìn)先出的特征，使棧成為程序設(shè)計中的有棧結(jié)構(gòu)具有后進(jìn)先出的特征，使棧成為程序設(shè)計中的有用工具，本節(jié)介紹棧的幾個簡單應(yīng)用的實例。用工具，本節(jié)介紹棧的幾個簡單應(yīng)用的實例。例例1 1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 1 1）問題）問題 在計算機基礎(chǔ)課中，我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問在計算機基礎(chǔ)課中，我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問題。十題。十八進(jìn)制轉(zhuǎn)換、十八

25、進(jìn)制轉(zhuǎn)換、十二進(jìn)制轉(zhuǎn)換等。下面我們二進(jìn)制轉(zhuǎn)換等。下面我們設(shè)計一程序?qū)崿F(xiàn)十進(jìn)制數(shù)到八進(jìn)制數(shù)的自動轉(zhuǎn)換。即該程設(shè)計一程序?qū)崿F(xiàn)十進(jìn)制數(shù)到八進(jìn)制數(shù)的自動轉(zhuǎn)換。即該程序功能為：對于輸入的任意一個非負(fù)十進(jìn)制數(shù)，顯示輸出序功能為：對于輸入的任意一個非負(fù)十進(jìn)制數(shù)，顯示輸出與其等值的八進(jìn)制數(shù)。與其等值的八進(jìn)制數(shù)。 2 2） 求解方法求解方法 這個問題的求解方法有很多，我們這里介紹的方法基于這個問題的求解方法有很多，我們這里介紹的方法基于下列原理：下列原理： N = (Ndiv8)10 8+N mod 8 N：十進(jìn)制數(shù)，十進(jìn)制數(shù)，div：整除運算，整除運算，mod：求余運算；求余運算； (1348)10 = 2

26、83+5 82+0 8+4 = (2504)8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 由上述求解過程可以看出，在計算過程中是從低位到高位由上述求解過程可以看出，在計算過程中是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而顯示時按照我們的習(xí)慣是從順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而顯示時按照我們的習(xí)慣是從高位在前，低位在后，即按從高位到低位的順序輸出高位在前，低位在后，即按從高位到低位的順序輸出, , 即后計即后計算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點，因此可將計算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點，因此可將計算過程中得到的八進(jìn)制數(shù)

27、順序進(jìn)棧，出棧序列打印輸出的就是算過程中得到的八進(jìn)制數(shù)順序進(jìn)棧，出棧序列打印輸出的就是對應(yīng)的八進(jìn)制數(shù)。對應(yīng)的八進(jìn)制數(shù)。3 3）算法算法void conversion( ) /對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)對于輸入的任意一個非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); /建空棧建空棧 scanf(“%d”, N); /輸入一個輸入一個非負(fù)十進(jìn)制整數(shù)非負(fù)十進(jìn)制整數(shù) while(N) / N不等于零不等于零循環(huán)循環(huán) Push(S, N % 8); / N/8第一個余數(shù)進(jìn)棧第一個余數(shù)進(jìn)棧 N=N/8; /整除運算整除運算 while(! Stac

28、kEmpty) /輸出存放在棧中的八制數(shù)位。輸出存放在棧中的八制數(shù)位。 Pop(S, e); Printf(“%d”, e); /conversion 算法算法3.1例例2 括號匹配的檢驗括號匹配的檢驗假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中（）或（）或（ ）等為正確的格式，等為正確的格式，（ ）或（）或（ ）或）或 （）（）)均為不正確的格式。均為不正確的格式。算法的設(shè)計思想：算法的設(shè)計思想：1 1）凡出現(xiàn)左括弧，則進(jìn)棧；）凡出現(xiàn)左括弧，則進(jìn)棧；2 2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空 若棧空，則表明該若棧空，則表明該“右括弧右括弧”多余，多余， 否則和棧頂元素比較，否則和

29、棧頂元素比較， 若相匹配，則若相匹配，則“左括弧出棧左括弧出?！?” ， 否則表明不匹配。否則表明不匹配。3 3）表達(dá)式檢驗結(jié)束時，）表達(dá)式檢驗結(jié)束時， 若?？眨瑒t表明表達(dá)式中匹配正確，若?？?，則表明表達(dá)式中匹配正確， 否則表明否則表明“左括弧左括弧”有余。有余。出口例例3 3 迷宮求解迷宮求解入口入口求迷宮路徑算法的基本思想是：求迷宮路徑算法的基本思想是：若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)，則納入路徑，繼續(xù)前進(jìn); ;若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方向繼續(xù)探索，則后退，換方向繼續(xù)探索;若四周若四周“均無通路均無通路”，則將當(dāng)前位置從路徑中刪除出，則將當(dāng)前位

30、置從路徑中刪除出去。去。設(shè)定初值為入口位置設(shè)定初值為入口位置, ,以正東為起始方向以正東為起始方向； dodo if( if(當(dāng)前位置可通當(dāng)前位置可通) ) 則將當(dāng)前位置插入棧頂；則將當(dāng)前位置插入棧頂； if(if(該位置是出口位置該位置是出口位置) ) exit(0)exit(0)； else else 按順時針下一方向為新的當(dāng)前位置；按順時針下一方向為新的當(dāng)前位置； elseelse* * while(while(棧不空）；棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：若?？?，則表明迷宮沒有通路。若棧空，則表明迷宮沒有通路。else * if if(

31、 (棧不空棧不空&棧頂位置尚有其他方向未被探索棧頂位置尚有其他方向未被探索) ) 新的當(dāng)前位置為新的當(dāng)前位置為: : 沿順時針方向旋轉(zhuǎn)沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊； if if( (棧不空棧不空&棧頂位置的四周均不可通棧頂位置的四周均不可通) ) 刪去棧頂位置；刪去棧頂位置；/ / 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？?；直至找到一個可通的相鄰塊或出棧至?？眨?/else例例4 表達(dá)式求值表達(dá)式求值1）問題的提出）問題的提出

32、假若我們想在計算機上設(shè)計一個小計算器（程序），其假若我們想在計算機上設(shè)計一個小計算器（程序），其功能為：從鍵盤上輸入一個算術(shù)表達(dá)式（由運算符操作數(shù)構(gòu)成功能為：從鍵盤上輸入一個算術(shù)表達(dá)式（由運算符操作數(shù)構(gòu)成的字符串）的字符串）,在屏幕上顯示輸出表達(dá)式的求值結(jié)果。在屏幕上顯示輸出表達(dá)式的求值結(jié)果。 顯然這個小計算器程序應(yīng)該對你鍵入的表達(dá)式進(jìn)行求值。顯然這個小計算器程序應(yīng)該對你鍵入的表達(dá)式進(jìn)行求值。在該程序中如何對鍵入的表達(dá)式求值呢？在該程序中如何對鍵入的表達(dá)式求值呢？ 又如，高級語言中都有表達(dá)式，例賦值語句：變量又如，高級語言中都有表達(dá)式，例賦值語句：變量=表達(dá)表達(dá)式；該語句的執(zhí)行過程為：先求出表

33、達(dá)式的值，式；該語句的執(zhí)行過程為：先求出表達(dá)式的值， 然后將其值然后將其值賦給賦值號左邊的變量。這個表達(dá)式的值是如何求出的？賦給賦值號左邊的變量。這個表達(dá)式的值是如何求出的？ 下面我們就來設(shè)計一個表達(dá)式求值算法。下面我們就來設(shè)計一個表達(dá)式求值算法。2 2）表達(dá)式的構(gòu)成）表達(dá)式的構(gòu)成 操作數(shù)操作數(shù)+ +運算符運算符+ +界限符（如括號）界限符（如括號）3 3）表達(dá)式的求值：）表達(dá)式的求值： 例例 5+6 5+6 (1+2)- 4(1+2)- 4 按照四則運算法則，上述表達(dá)式的計算過程為：按照四則運算法則，上述表達(dá)式的計算過程為： 5+ 6 5+ 6 (1+2)- 4=5+6 (1+2)- 4=5

34、+6 3-4 = 5+18-4= 23-4=193-4 = 5+18-4= 23-4=19 表達(dá)式中運算符的運算順序為：表達(dá)式中運算符的運算順序為： + + ， ， + +， - - ， 如何確定運算符的運算順序？如何確定運算符的運算順序？1 12 23 34 41 12 23 34 44） 算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運算符表達(dá)式中任何相鄰運算符 1、 2的優(yōu)先關(guān)系有：的優(yōu)先關(guān)系有： 1 2： 1的優(yōu)先級高于的優(yōu)先級高于 2 由四則運算法則，可得到如下的算符優(yōu)先關(guān)系表：由四則運算法則，可得到如下的算符優(yōu)先關(guān)系表：+ 21 - -* */ /( () )# #+ - + -

35、* * / ( ) # / ( ) # = = = 算符間的優(yōu)先關(guān)系表算符間的優(yōu)先關(guān)系表注：注： 1 2是相鄰算符，是相鄰算符， 1在左，在左， 2在右在右5 5 ) ) 算符優(yōu)先算法算符優(yōu)先算法 我們再來分析一下表達(dá)式我們再來分析一下表達(dá)式5+45+4 (1+2)-6 (1+2)-6 計算過程：計算過程： 從左向右掃描表達(dá)式：從左向右掃描表達(dá)式： 遇操作數(shù)遇操作數(shù)保存；保存； 遇運算符號遇運算符號 j與前面的剛掃描過的運算符與前面的剛掃描過的運算符 i比較比較 若若 i j 則保存則保存 j，（，（ 因此已保存的運算符的優(yōu)先關(guān)系為因此已保存的運算符的優(yōu)先關(guān)系為 1 2 3 j 則說明則說明

36、i是已掃描的運算符中優(yōu)先級最高者，可進(jìn)行運算；是已掃描的運算符中優(yōu)先級最高者，可進(jìn)行運算； 若若 i = j 則則 i為（，為（， j 為為 ），說明括號內(nèi)的式子已計算完，需要消去括號；），說明括號內(nèi)的式子已計算完，需要消去括號； 5+4 (1+2)- 6我們可以利用兩個棧分別保存掃描過程中遇到的操作數(shù)和運算符。我們可以利用兩個棧分別保存掃描過程中遇到的操作數(shù)和運算符。后面也許有優(yōu)先級后面也許有優(yōu)先級更大的算符更大的算符表達(dá)式求值示意圖：表達(dá)式求值示意圖：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR棧棧# #OPNDOPND棧棧toptopbase

37、base5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5讀入表達(dá)式過程：讀入表達(dá)式過程：+ +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+1

38、8=235+18=2323-4=1923-4=19 在算符優(yōu)先算法中，建立了兩個工作棧。一個是在算符優(yōu)先算法中，建立了兩個工作棧。一個是OPTR棧，用以保存運算符棧，用以保存運算符一個是一個是OPND棧，用以保存操作數(shù)或運算結(jié)果。棧，用以保存操作數(shù)或運算結(jié)果。 operandType EvaluateExpression( ) /算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和和OPND分別為運算符棧和分別為運算符棧和 /運算數(shù)棧，運算數(shù)棧，OP為運算符集合。為運算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND

39、); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是運算符則進(jìn)棧不是運算符則進(jìn)棧 else / In(c, OP)判斷判斷c是否是否 /是運算符的函數(shù)是運算符的函數(shù) 續(xù)續(xù) switch (Precede(GetTop(OPTR), c) case : /新輸入的算符新輸入的算符c優(yōu)先級低，即棧頂算符優(yōu)先權(quán)高，優(yōu)先級低，即棧頂算符優(yōu)先權(quán)高， /出棧并將運算結(jié)果入棧出棧并將運算結(jié)果入棧OPND Pop(OPTR, theta); Pop(OPND, b); P

40、op(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND);/EvaluateExpression第三章第三章 習(xí)題一習(xí)題一習(xí)題五習(xí)題五1 P21-23 1 P21-23 3.1, 3.2, 3.7 3.1, 3.2, 3.72 2 編編寫鏈?zhǔn)綏＿M(jìn)棧、出棧操作的算法，并畫出鏈?zhǔn)綏＿M(jìn)棧操作寫鏈?zhǔn)綏＿M(jìn)棧、出棧操作的算法，并畫出鏈?zhǔn)綏＿M(jìn)棧操作前、進(jìn)棧操作后的圖示前、進(jìn)棧操作后的圖示 習(xí)題取自習(xí)題取自數(shù)據(jù)結(jié)構(gòu)題集數(shù)據(jù)結(jié)構(gòu)題集 C C語言版語言版 嚴(yán)尉敏等編嚴(yán)尉敏等編 清華大學(xué)出版社清華

41、大學(xué)出版社3.3 棧與遞歸棧與遞歸 由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過程具有后進(jìn)先出的特性，可由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過程具有后進(jìn)先出的特性，可利用棧來實現(xiàn)數(shù)據(jù)處理過程。下面我們將看到可以用棧來實現(xiàn)遞歸。利用棧來實現(xiàn)數(shù)據(jù)處理過程。下面我們將看到可以用棧來實現(xiàn)遞歸。1什么是遞歸什么是遞歸 遞歸是一個很有用的工具，在數(shù)學(xué)和程序設(shè)計等許多領(lǐng)域中都用到遞歸是一個很有用的工具，在數(shù)學(xué)和程序設(shè)計等許多領(lǐng)域中都用到了遞歸。了遞歸。遞歸定義：簡單地說，一個用自己定義自己的概念遞歸定義：簡單地說，一個用自己定義自己的概念,稱為遞歸定義。稱為遞歸定義。例例 n!= 1 2 3 4 (n-1) n n!遞歸

42、定義遞歸定義 n!= 1 當(dāng)當(dāng) n=1時時 n!= n (n-1)! 當(dāng)當(dāng)n 1時時用用(n-1)!(n-1)!定義定義n!n!2 遞歸函數(shù)：一個直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱遞歸函數(shù)：一個直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱 為遞歸函數(shù)。為遞歸函數(shù)。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接調(diào)用自己直接調(diào)用自己B間接調(diào)用自己間接調(diào)用自己遞歸是程序設(shè)計中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。遞歸是程序設(shè)計中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。2遞歸算法的編寫遞歸算法的編寫1）將問題用遞歸的方式描述（定義

43、）將問題用遞歸的方式描述（定義）2）根據(jù)問題的遞歸描述（定義）編寫遞歸算法）根據(jù)問題的遞歸描述（定義）編寫遞歸算法 問題的遞歸描述（定義）問題的遞歸描述（定義） 遞歸定義包括兩項遞歸定義包括兩項 基本項（終止項）：描述遞歸終止時問題的求解；基本項（終止項）：描述遞歸終止時問題的求解； 遞歸項：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題；遞歸項：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題； 例例 n!的遞歸定義的遞歸定義 基本項：基本項： n!=1 當(dāng)當(dāng) n=1 遞歸項：遞歸項： n!=n (n-1)! 當(dāng)當(dāng) n 1用用(n-1)!(n-1)!定義定義n!n!例例1 編寫求解編寫求解 階

44、乘階乘n! 的遞歸算法的遞歸算法首先給出階乘首先給出階乘n! 的遞歸定義的遞歸定義 n!的遞歸定義的遞歸定義 基本項：基本項： n!=1 當(dāng)當(dāng) n=1 遞歸項：遞歸項： n!=n (n-1)! 當(dāng)當(dāng) n 1 有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 if（n=1） return（1）；）； else return（n*fact (n-1)）；）；/fact 例例2. 編寫求解編寫求解Hanci塔問題的遞歸算法塔問題的遞歸算法 有三個各為有三個各為X，Y，

45、Z的塔座，在的塔座，在X項有項有n個大小不同，依個大小不同，依小到大編號為小到大編號為1，2n的圓盤。的圓盤。 現(xiàn)要求將現(xiàn)要求將X上的上的n個圓盤移個圓盤移至至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放， 圓盤移動時必須遵守下列原圓盤移動時必須遵守下列原則：則：1）每次移動一個盤子；）每次移動一個盤子；2）圓盤可以放在）圓盤可以放在X，Y，Z中的中的任一塔座上；任一塔座上；3）任何時刻都不能將較大的圓盤壓放在較小圓盤之上；）任何時刻都不能將較大的圓盤壓放在較小圓盤之上；例例 n=3時時圓盤移動的過程如下圖所示圓盤移動的過程如下圖所示：a ab bc c3 32 21 1 1 11 12

46、21 13 31 12 21 1Y YX XZ Z首先給出首先給出求解求解Hanci塔問題塔問題 的遞歸描述（定義）的遞歸描述（定義） 基本項：基本項： n=1時，將時，將n號圓盤從號圓盤從X移至移至Z； 遞歸項：遞歸項： n1時，時， 將將X上上1n-1號圓盤移至號圓盤移至Y； 將將X上的上的n號圓盤從號圓盤從X移至移至Z; 將將Y上上1n-1號圓盤從號圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的問題的問題的求解歸結(jié)為規(guī)模的求解歸結(jié)為規(guī)模為為n-1n-1的問題的求的問題的求解解有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：void hanoi

47、(int n, char x, char y, char z) /將塔座將塔座x上按直徑由小到大且自上而下編號為上按直徑由小到大且自上而下編號為1至至n的的n個圓盤按規(guī)則搬到個圓盤按規(guī)則搬到 /塔座塔座z上，上，y可用作輔助塔座?？捎米鬏o助塔座。 /搬動操作搬動操作move(x, n, z),將編號為將編號為 n的圓盤從的圓盤從x移到移到z /printf(“%d Move disk %di from %c to %cn”, +c, n, x, z); if (n= =1) move(x,1,z); /將編號為將編號為1的圓盤從的圓盤從x移動移動z else hanoi(n-1, x, z,

48、y); /將將x上編號為上編號為1至至n-1的圓盤移到的圓盤移到y(tǒng), z作輔助塔作輔助塔 move(x, n, z); /將編號為將編號為 n的圓盤從的圓盤從x移到移到z hanoi(n-1, y, x, z)； /將將y上編號為上編號為1至至n-1的圓盤移到的圓盤移到z，x作輔助塔作輔助塔 算法算法3.5 Hanci塔問題塔問題 3 遞歸函數(shù)的實現(xiàn)遞歸函數(shù)的實現(xiàn) 在遞歸函數(shù)的執(zhí)行中，在遞歸函數(shù)的執(zhí)行中， 需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？先看一般函數(shù)的調(diào)用機制如何實現(xiàn)的。先看一般函數(shù)的調(diào)用機制如何實現(xiàn)的。 A( )A( )B( );B( );

49、 C( )C( ) B( )B( )C( );C( ); 調(diào)用調(diào)用調(diào)用調(diào)用返回返回返回返回函數(shù)調(diào)用順序函數(shù)調(diào)用順序 A B CA B C函數(shù)返回順序函數(shù)返回順序 C B AC B A后調(diào)用的函數(shù)先返回后調(diào)用的函數(shù)先返回 函數(shù)調(diào)用機制可通過棧來實現(xiàn)函數(shù)調(diào)用機制可通過棧來實現(xiàn)我們看一下我們看一下n=3 n=3 階乘函數(shù)階乘函數(shù)fact(n)fact(n)的執(zhí)行過程的執(zhí)行過程Main( ) Main( ) intint n=3,y; n=3,y;L y= fact(n);L y= fact(n); 調(diào)調(diào)用用調(diào)用調(diào)用調(diào)調(diào)用用int fact (n) if（n=1） return（1）；）； else

50、L1 return（n*fact (n-1)）；）；/factn=3n=3int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=2n=2int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=1n=1L 3L 3L1 1L1 1L1 2L1 2返返回回1 1返回返回2 2返返回回6 6返回地址返回地址 實參實參 注意遞歸調(diào)用中注意遞歸調(diào)用中 棧的變化棧的變化 3.4 3.4 隊列隊列3.43.4 .1

51、.1 隊列隊列的概念的概念3.43.4 .2 .2 循環(huán)隊列循環(huán)隊列 隊列隊列的順序存儲和實現(xiàn)的順序存儲和實現(xiàn)3.43.4 .3 .3 隊列隊列的鏈?zhǔn)酱鎯蛯崿F(xiàn)的鏈?zhǔn)酱鎯蛯崿F(xiàn)學(xué)習(xí)要點學(xué)習(xí)要點1 1 理解掌握隊列的結(jié)構(gòu)特征和操作特點；理解掌握隊列的結(jié)構(gòu)特征和操作特點；2 2 掌握隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及如何用掌握隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及如何用C C語言描述語言描述 它們的類型定義；它們的類型定義；3 3 掌握在兩種存儲結(jié)構(gòu)下，隊列的基本操作的算法；重點掌握掌握在兩種存儲結(jié)構(gòu)下，隊列的基本操作的算法；重點掌握 循環(huán)隊列的入隊、出隊算法，循環(huán)隊列隊空、隊滿的判別條件；循環(huán)隊

52、列的入隊、出隊算法，循環(huán)隊列隊空、隊滿的判別條件；4 4 理解隊列先進(jìn)先出的特點及在程序設(shè)計中的應(yīng)用；理解隊列先進(jìn)先出的特點及在程序設(shè)計中的應(yīng)用；基本內(nèi)容基本內(nèi)容1 1 隊列的概念，隊列的基本操作；隊列的概念，隊列的基本操作；2 2 隊列的兩類存儲結(jié)構(gòu)和它們的類型定義；隊列的兩類存儲結(jié)構(gòu)和它們的類型定義；3 3 在隊列的存儲結(jié)構(gòu)下，隊列的基本操作的算法；在隊列的存儲結(jié)構(gòu)下，隊列的基本操作的算法；4 4 隊列在程序設(shè)計中的應(yīng)用。隊列在程序設(shè)計中的應(yīng)用。3 34 4 隊列隊列3.4.1隊列的定義和抽象數(shù)據(jù)類型隊列的定義和抽象數(shù)據(jù)類型一一 什么是隊列什么是隊列隊列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插

53、入的線隊列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除說明：設(shè)（說明：設(shè)（a1,a2 , a3 , . , an ）為一隊列為一隊列 1）表尾稱作隊尾，表頭稱為隊頭；）表尾稱作隊尾，表頭稱為隊頭； 2）a1為隊頭元素，為隊頭元素，an為隊尾元素；為隊尾元素； 3）在表尾插入元素操作，稱為入隊操作；在表頭刪除元素）在表尾插入元素操作，稱為入隊操作；在表頭刪除元素 的操作，稱為出隊操作；的操作，稱為出隊操作； 4）元素按）元素按a1,a2, a3, . an 順序入隊，第一個入隊的元素為順序入隊，第一個

54、入隊的元素為a1 最后一個入隊的元素是最后一個入隊的元素是an 第一個出隊的元素為第一個出隊的元素為a1 ； 5）隊列具有先進(jìn)先出的特點，所以又稱為先進(jìn)先出表隊列具有先進(jìn)先出的特點，所以又稱為先進(jìn)先出表 （FIFO表）表） a a1 1 a a2 2 a a3 3 a an n入隊列入隊列隊隊頭頭隊隊尾尾出隊列出隊列隊列的示意圖隊列的示意圖隊列的特點隊列的特點先進(jìn)先出先進(jìn)先出第一個入隊的元素在隊頭，第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾，最后一個入隊的元素在隊尾，第一個出隊的元素為隊頭元素，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素最后一個出隊的元素為隊尾元素 隊列類似

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

56、rQueue(&Q) 功能：功能： 將隊列將隊列Q置為空隊列置為空隊列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若隊列功能：若隊列Q為空，則返回為空，則返回True，否則返回否則返回False；5）取隊頭元素操作取隊頭元素操作GetHead(Q,&e) 功能：取隊頭元素，并用功能：取隊頭元素，并用e返回；返回；6）入隊操作入隊操作EnQueue( &Q, e ) 功能：將元素功能：將元素e插入插入Q的隊尾；的隊尾；7）出隊操作）出隊操作DeQueue( &Q, &e) 功能：若隊列不空，則刪除功能：若隊列不空，則刪除Q的隊頭元素，用的隊

57、頭元素，用e返回其值，并返回返回其值，并返回OK，否則返回否則返回ERROR；3.4.2 循環(huán)隊列循環(huán)隊列隊列的順序存儲和實現(xiàn)隊列的順序存儲和實現(xiàn)一一 隊列的順序存貯結(jié)構(gòu)隊列的順序存貯結(jié)構(gòu) 1 隊列的順序存貯結(jié)構(gòu)隊列的順序存貯結(jié)構(gòu) 和順序棧類似，在隊列的順序存貯結(jié)構(gòu)中除了和順序棧類似，在隊列的順序存貯結(jié)構(gòu)中除了用一組連續(xù)存儲單元依次存儲從隊頭到隊尾的數(shù)據(jù)用一組連續(xù)存儲單元依次存儲從隊頭到隊尾的數(shù)據(jù)元素外，還需附加兩個變量，一個稱為隊頭指針，元素外，還需附加兩個變量，一個稱為隊頭指針，指示隊頭元素的位置；一個稱為隊尾指針，指示隊指示隊頭元素的位置；一個稱為隊尾指針，指示隊尾元素的位置。尾元素的位

58、置。Q.rearQ.rearQ.frontQ.frontJ1J1J2J2J3J3隊列的順序存貯結(jié)構(gòu)圖示隊列的順序存貯結(jié)構(gòu)圖示MAXSIZE：最大隊列空間，可根據(jù)實際應(yīng)用確定；最大隊列空間，可根據(jù)實際應(yīng)用確定； SqQueue：結(jié)構(gòu)類型名；結(jié)構(gòu)類型名； SqQueue 類型的變量是結(jié)構(gòu)變量。它的三個域分別是：類型的變量是結(jié)構(gòu)變量。它的三個域分別是： base：隊列存儲空間基址；隊列存儲空間基址； front：隊頭指針，若隊列不空，指向隊頭元素；隊頭指針，若隊列不空，指向隊頭元素； rear：隊尾指針，若隊列不空，指向隊尾元素的下一位置；隊尾指針，若隊列不空，指向隊尾元素的下一位置；# #defi

59、ne MAXSIZE 100 / define MAXSIZE 100 / 最大隊列長度最大隊列長度typedeftypedef structstruct QElemTypeQElemType * *base; /base; /初始化時動態(tài)分配初始化時動態(tài)分配存儲空間的基址存儲空間的基址 intint front; / front; /隊頭指針，指向隊頭元素隊頭指針，指向隊頭元素 intint rear; / rear; /隊尾指針，指向隊尾元素的下一個位置隊尾指針，指向隊尾元素的下一個位置 SqQueueSqQueue; ;2順序隊列的類型定義順序隊列的類型定義Q.rearQ.rearQ.f

60、rontQ.frontJ1J1J2J2J3J3Q.rearQ.rearQ.frontQ.frontJ3J3（a)a)空隊列空隊列(b)J1,J2(b)J1,J2和和J3J3相繼入隊列相繼入隊列(c)J1(c)J1和和J2J2相相繼出隊繼出隊( (d)J4,J5d)J4,J5和和J6J6相繼入相繼入隊之后隊之后, ,J3J3出隊出隊Q.rearQ.rearQ.frontQ.front0 01 12 23 34 45 5隊頭指針隊尾指針和隊列中元素之間的關(guān)系圖示隊頭指針隊尾指針和隊列中元素之間的關(guān)系圖示 設(shè)設(shè)Q為為SqQueue類型的變量，用于存儲隊列。設(shè)為隊列類型的變量，用于存儲隊列。設(shè)為隊列Q分配空間大小分配空間大小為為MAXSIZE=6，初始建隊時，令初始建隊時，令Q.front=Q.rear=0;Q.rearQ.rearQ.frontQ.frontJ6J6J5J5J4J43 . 循環(huán)隊列循環(huán)隊列 從圖從圖示示（d）中