資料結(jié)構(gòu)-堆疊與佇列

1、資料結(jié)構(gòu)第三章堆疊與佇列1大綱第一節(jié)堆疊 第二節(jié)佇列 2第一節(jié)堆疊一、定義 堆疊是一個(gè)有序串列，所有的加入(insert)與刪除(delete)動(dòng)作均是在堆疊的頂端(top)進(jìn)行，具有先進(jìn)後出(FILO)或後進(jìn)先出(LIFO)的特性。 3第一節(jié)堆疊二、應(yīng)用 1. 副程式的呼叫及返回處理。 2. 遞迴程式的呼叫及返回處理。 3. 算術(shù)式的轉(zhuǎn)換。 4. 二元樹(shù)的走訪(fǎng)。 5. 圖形的走訪(fǎng)。 6. 中斷的處理。 4第一節(jié)堆疊三、堆疊的工作定義 1. CREATE(S)：建立一個(gè)空的堆疊。 2. PUSH(data, S)：將資料加入堆疊的頂端。 3. POP(S)：傳回堆疊頂端的資料，並將該筆資料 自

2、堆疊中刪除。 4. TOP(S)：傳回堆疊頂端的資料，但不將該筆資 料自堆疊中刪除。 5. EMPTY(S)：若堆疊內(nèi)已無(wú)任何資料，就傳回真 (true)，否則就傳回假(false)。 5第一節(jié)堆疊四、加入及刪除資料的演算法 將一筆資料加入堆疊中的演算法：Procedure PUSH(data, stack, n, top)If (topn) then Call STACK-FULL( )Else stack(top)data toptop+1end if end PUSH6第一節(jié)堆疊 (1) data：代表欲加入堆疊中的資料。 (2) stack：是一個(gè)指向堆疊起點(diǎn)的指標(biāo)(pointer)。

3、 (3) n：記錄堆疊的大小。 (4) top：是一個(gè)指向堆疊頂端的指標(biāo)，亦即指向堆疊中下一個(gè)可以再存放資料的指標(biāo)。 (5) STACK-FULL( )：是一個(gè)錯(cuò)誤警告副程式，用來(lái)表示現(xiàn)在的堆疊已經(jīng)滿(mǎn)了，無(wú)法再做加入資料的動(dòng)作了。(6) ：表示將右邊的資料存入左邊所指的位置，所以“stack(top)data”表示將資料data存入stack + top所指的位置中。 7第一節(jié)堆疊自堆疊中取出一筆資料，並刪除該筆資料的演算法： Procedure POP(stack, data, top)if ( top=1) then Call STACK_EMPTY( )else top top-1 da

4、ta stack(top)end if end POP 8第一節(jié)堆疊 STACK_EMPTY( )是一個(gè)錯(cuò)誤警告副程式，用來(lái)表示現(xiàn)在的堆疊已經(jīng)是空的，無(wú)法再做取出或刪除資料的動(dòng)作了。 註：以上兩個(gè)演算法PUSH( )及POP( )，若陣列起始編碼是從1開(kāi)始，則堆疊可以加入或刪除n筆資料；但若是從零開(kāi)始，則演算法POP( )中之if判斷式須修改成if (top=0) then call STACK-EMPTY( )，如此即可加入或刪除n+1筆資料了。 9第二節(jié)佇列一、定義 佇列是一個(gè)有序串列 (ordered list)，所有的加入與刪除分別發(fā)生在串列的不同端，加入的一端稱(chēng)為後端 (rear)，

5、而刪除的一端稱(chēng)為前端 (front)，具有先進(jìn)先出 (FIFO) 的特性。 10第二節(jié)佇列二、應(yīng)用 1.作業(yè)系統(tǒng)的工作排程。 2.電腦的模擬（simulation）程式。 3.輸出入工作緩衝區(qū)（buffer）。 11第二節(jié)佇列三、佇列的工作定義 1. CREATE(Q)：建立一個(gè)空的佇列。 2. ADDQ(data, Q)：將資料加入佇列的尾端(rear)。 3. DELETEQ(Q)：傳回佇列前端(front)的資料，並將 該筆資料自佇列中刪除。 4. FRONT(Q)：傳回佇列前端的資料，但不會(huì)將該筆 資料自佇列中刪除。 5. EMPTY(Q)：若佇列為空的(empty)，代表佇列內(nèi)已 無(wú)

6、任何資料，因此就傳回真(true)；否則就傳回假 (false)，代表佇列不為空的，亦即佇列內(nèi)尚有資料。 12第二節(jié)佇列四、加入及刪除資料的演算法 將一筆資料加入佇列中的演算法： Procedure ADDQ(data, Q, n, rear) if (rearn) then call QUEUE_FULL( ) else Q(rear)data rearrear+1 end if end ADDQ 13第二節(jié)佇列 (1)data：代表欲加入佇列中的資料。(2)Q：是一個(gè)指向佇列起點(diǎn)的指標(biāo)。(3)n：記錄佇列的大小。(4)rear：是一個(gè)指向佇列尾端的指標(biāo)。(5)QUEUE_FULL( )：是

7、一個(gè)錯(cuò)誤警告副程式， 用來(lái)表示現(xiàn)在的佇列已經(jīng)滿(mǎn)了，無(wú)法再做加 入資料的動(dòng)作了。(6)：表示將右邊的資料存入左邊所指的位 置，所以“Q (rear)data”表示將資料data存 入到Q + rear所指的位置中。 14第二節(jié)佇列自佇列中取出一筆資料，並刪除該筆資料的演算法： Procedure DELETEQ(Q, data, front, rear ) if(front=rear) then call QUEUE_EMPTY( )else dataQ(front) frontfront+1end if end DELETEQ 15第二節(jié)佇列 (1) front：是一個(gè)指向佇列前端的指標(biāo)，與Q

8、指標(biāo) 的差別是，Q指標(biāo)不會(huì)任意改變，它永遠(yuǎn)指向佇 列開(kāi)始的位置，但front指標(biāo)會(huì)隨資料自佇列中 刪除而跟著做改變。 (2) QUEUE_EMPTY( )：是一個(gè)錯(cuò)誤警告副程 式，用來(lái)表示現(xiàn)在的佇列已經(jīng)是空的，無(wú) 法再做取出或刪除資料的動(dòng)作了。註：以上兩個(gè)演算法ADDQ( )及DELETEQ( )，若陣列起始編號(hào)是從0開(kāi)始，則可以加入或刪除n+1筆資料，若是從1開(kāi)始，則可以加入或刪除n筆資料。 16第二節(jié)佇列五、環(huán)狀佇列（Circular Queue） 將一筆資料加入circular queue中的演算法： Procedure ADDCQ(data, Q, n, front, rear)if(

9、rear MOD n)+1=front) then call QUEUE_FULL( )else Q(rear)data rear(rear MOD n)+1end ifend ADDCQ17第二節(jié)佇列自circular queue 中取出一筆資料，並刪除該資料的演算法： Procedure DELETECQ(data, Q, n, front, rear)if(front =rear) then call QUEUE_EMPTY( )else dataQ(front) front(front MOD n) + 1end if end DELETECQ 18第二節(jié)佇列以上兩個(gè)演算法ADDCQ( )及DELETECQ( )，若陣列起始編號(hào)是從1開(kāi)始，則可以加入或刪除n個(gè)資料；但若是從0開(kāi)始，則演算法須分別修改如下： (n必須大於0 才有意義) 19第二節(jié)佇列 Procedure ADDCQ(data, Q, n, front, rear)if (rear+1) MOD n=front) then call QUEUE_FULL( )else Q(rear)data rear(rear+1) MOD nend ifend ADD