资料结构-堆叠与伫列

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

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

3、 (3) n：記錄堆疊的大小。 (4) top：是一個指向堆疊頂端的指標，亦即指向堆疊中下一個可以再存放資料的指標。 (5) STACK-FULL( )：是一個錯誤警告副程式，用來表示現在的堆疊已經滿了，無法再做加入資料的動作了。(6) ：表示將右邊的資料存入左邊所指的位置，所以“stack(top)data”表示將資料data存入stack + top所指的位置中。 7第一節堆疊自堆疊中取出一筆資料，並刪除該筆資料的演算法： 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第一節堆疊 STACK_EMPTY( )是一個錯誤警告副程式，用來表示現在的堆疊已經是空的，無法再做取出或刪除資料的動作了。 註：以上兩個演算法PUSH( )及POP( )，若陣列起始編碼是從1開始，則堆疊可以加入或刪除n筆資料；但若是從零開始，則演算法POP( )中之if判斷式須修改成if (top=0) then call STACK-EMPTY( )，如此即可加入或刪除n+1筆資料了。 9第二節佇列一、定義 佇列是一個有序串列 (ordered list)，所有的加入與刪除分別發生在串列的不同端，加入的一端稱為後端 (rear)，

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

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

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

8、指標 的差別是，Q指標不會任意改變，它永遠指向佇 列開始的位置，但front指標會隨資料自佇列中 刪除而跟著做改變。 (2) QUEUE_EMPTY( )：是一個錯誤警告副程 式，用來表示現在的佇列已經是空的，無 法再做取出或刪除資料的動作了。註：以上兩個演算法ADDQ( )及DELETEQ( )，若陣列起始編號是從0開始，則可以加入或刪除n+1筆資料，若是從1開始，則可以加入或刪除n筆資料。 16第二節佇列五、環狀佇列（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第二節佇列自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第二節佇列以上兩個演算法ADDCQ( )及DELETECQ( )，若陣列起始編號是從1開始，則可以加入或刪除n個資料；但若是從0開始，則演算法須分別修改如下： (n必須大於0 才有意義) 19第二節佇列 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