资源描述
,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,資料結構,第三章堆疊與佇列,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),：傳回堆疊頂端的資料，並將該筆資料,自堆疊中刪除。,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,top,top+1,end if,end PUSH,6,第一節堆疊,(1) data,：代表欲加入堆疊中的資料。,(2) stack,：是一個指向堆疊起點的指標,(pointer),。,(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,data,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),，,而刪除的一端稱為前端,(,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),，,代表佇列內已,無任何資料，因此就傳回真,(,true),；,否則就傳回假,(,false),，,代表佇列不為空的，亦即佇列內尚有資料。,12,第二節佇列,四、加入及刪除資料的演算法,將一筆資料加入佇列中的演算法：,Procedure ADDQ(data, Q, n, rear),if (rearn) then,call QUEUE_FULL( ),else,Q(rear),data,rear,rear+1,end if,end ADDQ,13,第二節佇列,(1)data,：代表欲加入佇列中的資料。,(2)Q,：是一個指向佇列起點的指標。,(3)n,：記錄佇列的大小。,(4)rear,：是一個指向佇列尾端的指標。,(5)QUEUE_FULL( ),：是一個錯誤警告副程式，,用來表示現在的佇列已經滿了，無法再做加,入資料的動作了。,(6),：表示將右邊的資料存入左邊所指的位,置，所以“,Q (rear),data,”,表示將資料,data,存,入到,Q + rear,所指的位置中。,14,第二節佇列,自佇列中取出一筆資料，並刪除該筆資料的演算法：,Procedure DELETEQ(Q, data, front, rear ),if(front=rear) then,call QUEUE_EMPTY( ),else,data,Q(front),front,front+1,end if,end DELETEQ,15,第二節佇列,(1) front,：是一個指向佇列前端的指標，與,Q,指標,的差別是，,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(rear MOD n)+1=front) then,call QUEUE_FULL( ),else,Q(rear),data,rear,(rear MOD n)+1,end if,end ADDCQ,17,第二節佇列,自,circular queue,中取出一筆資料，並刪除該資料的演算法：,Procedure DELETECQ(data, Q, n, front, rear),if(front =rear) then,call QUEUE_EMPTY( ),else,data,Q(front),front,(front MOD n) + 1,end 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 n,end if,end ADDCQ,20,第二節佇列,Procedure DELETECQ(data, Q, n, front, rear),if(front =rear) then,call QUEUE_EMPTY( ),else,data,Q(front),front,(front+1) MOD n,end if,end DELETECQ,21,
展开阅读全文