【正文】 ear = newPtr。 end 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 81 用課本的作法 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 82 課本作法 (p. 225): Pre: queue is a metadata structure Post: dataIn has been inserted Return: true if successful, false if overflow algorithm enqueue (ref queue metadata, val dataIn dataType) if (queue full) return false end if allocate (newPtr) newPtr?data = dataIn newPtr?next = null pointer if ( zero) //Case 1 = newPtr else //Case 2 ?next = newPtr end if = newPtr = + 1 return true end enqueue 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 83 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 84 Delete(Q) nil F R item deleteLoc ? ? F ? Ret ? begin if (front = nil) then Queue Empty。 else begin ? deleteLoc = front。 ? item = front?data。 ? front = front?link。 ? Ret(deleteLoc)。 if (front = nil) then rear = nil。 end。 end ? 假設(shè) Queue中只有一個 node，回收後 把 Rear指向 nil. ? 主要是耽心 系統(tǒng)不會自動將 Rear設(shè)成 nil，使得 Rear指標(biāo) 無效 !! F item ? ? Ret ? nil F ? R deleteLoc 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 85 課本作法 : Pre: queue is a metadata structure Post: data at front of queue returned to user through item and front element deleted and recycled Return: true if successful, false if underflow algorithm enqueue (ref queue metadata, ref item dataType) if ( is 0) return false end if ? Item = ?data ? deleteLoc = if ( 1) = null pointer end if ? = ?next = – 1 ? recycle (deleteLoc) return true end enqueue 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 86 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 87 Front(Q) 即課本中的 queueFront 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 88 Isempty(Q) 即課本中的 emptyQueue 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 89 IsFull(Q) 即課本中的 fullQueue 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 90 以上所有 C++實(shí)作皆在Section 56 (p. 246) 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 91 ▓ 用 Array製作 利用 Linear Array 利用 Circular Array with (n1) space used 利用 Circular Array with n space used When we implement a queue in an array, we use indexes rather than pointers. 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 92 利用 Linear Array Create(Q) 宣告 : Q: array[1?n] of items // 宣告 Q是一個 Array Front: integer = 1 //初 值 Rear: integer = 1 //初 值 AddQ(Q, item)?Queue begin if (rear = n) then QueueFull。 else begin rear = rear +1 Q[rear] = item end end. 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 93 DeleteQ(Q)? item, Queue begin if (rear = front) then QueueEmpty。 else begin front = front +1 item = Q[front] end end. 問題 : 當(dāng) rear = n 時， Queue並不代表真正為滿的情況 ! 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 94 When the data are grouped at the end of the array, we need to find a place for the new element when we enqueue data. One solution is to shift all of the elements from the end to the beginning of the array. 然而，此種作法導(dǎo)致 Queue之 Add動作時間為 O(n) ∵ 是用 廻圈 來實(shí)作資料的搬移，此為額外的處理且花費(fèi)時間太大 ?整體效益差 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 95 利用 Circular Array with (n1) space used Create(Q) 宣告 : Q: Array[0?n 1] front = rear = 0 //初 值 AddQ(item, Q) ?Queue begin rear = (rear+1) mod n。 //rear指標(biāo)先前進(jìn) if rear = front QueueFull。 //表示 Queue滿了 rear = rear1 mod n。 //將 rear重設(shè)回前一格 else Q[rear]=item。 end。 1 2 3 ? n1 R ? R = (R+1) mod n 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 96 DeleteQ(Q) ?item begin if front=rear //先檢 查 QueueEmpty。 else begin front = (front+1) mod n。 item = Q[front]。 end。 end。 特點(diǎn) : 最多只利用到 n1 格空間 若硬要使用到 n 格空間，則 rear = front 條件成立時， 無法真正區(qū)分出Queue為 Full或 Empty ∵ 判斷 Full與 Empty的條件式相同 (皆為 rear = Full) Add與 Delete之動作時間皆為 O(1) ∵ 沒有資料挪移 的動作 !! F R X X X X X X X X X X X X 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 97 利用 Circular Array with n space used 引進(jìn)一個 Tag變數(shù) ，用以 協(xié)助判斷 Queue為 Empty或 Full: 該變數(shù)為 Boolean型態(tài) 若 Tag = True: 則可協(xié)助判斷是否為 Full 若 Tag = False: 則可協(xié)助判斷是否為 Empty 不是光靠 Tag就能做正確判斷 !! 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 98 Create(Q) 宣告 : Q: Array[0?n 1] front = rear: int = 0 //初 值 Tag: Boolean = 0 //初 值 AddQ(item, Q) ?Queue begin if (rear = front and Tag = 1) QueueFull。 else begin rear = (rear+1) mod n。 //rear指標(biāo)前進(jìn) Q[rear]=item。 if (rear=front) Tag=1。 end。 end。 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 99 DeleteQ(Q) ?item begin if (Front=Rear and Tag=0) QueueEmpty。 else begin Front = (Front+1) mod n。 item = Q[Front]。 if (Front=Rear) Tag=0。 end。 end。 特點(diǎn) : 最多可利用到 n 格空間 Add與 Delete之運(yùn)作時間稍長 ∵ 多了一條 if測試 ，來測試 Tag值 設(shè)定，且此兩個運(yùn)作使用上極頻繁 ?整體時間效益稍嫌 Poor!! F R X X X X X X X X X X X X 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 100 補(bǔ) 充 國立聯(lián)合大學(xué) 資訊管理學(xué)系 資料結(jié)構(gòu)課程 (陳士杰 ) 101 補(bǔ) 1: 後序式、前序式轉(zhuǎn)中序式 Prefix ? Infi