advancedatastructurereviewofchapter3(編輯修改稿)
2024-11-05 09:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 queue = new KeyType[MaxSize]。 front = rear= 0。 } Queue Implementation II: Circular Array front = rear = 0 Initially 0 1 2 3 4 MaxSize1 ● ● Queue Implementation II: Circular Array 0 1 2 3 4 ● ● MaxSize1 front = 0 rear = 3 after insert 3 elements Insert 0 1 2 3 4 ● ● MaxSize1 front = 2 rear = 3 after delete 2 elements Delete Queue Implementation II: Circular Array ? 用 circular Array 實(shí)作 Queue，會(huì)面臨無(wú)法判斷 Queue 是空的或是滿的問(wèn)題。因?yàn)? front == rear 時(shí) Queue 可能為空，也可能為滿。 ? 如何解決？ 0 1 2 3 4 ● ● MaxSize1 front = rear = 3 Empty 0 1 2 3 4 ● ● MaxSize1 front = rear = 3 Full Queue Implementation II: Circular Array ? 解決方法，有二種 ? Method 1：犧牲空間 任何時(shí)候只允許 MaxSize1 個(gè)元素在 Queue 中 ? Method 2：犧牲時(shí)間 增加一個(gè)變數(shù)，記錄上一次的動(dòng)作。 ? 因?yàn)? Queue 元素的新增與刪除非常頻繁，所以我們較常採(cǎi)用 Method 1 ? 還有沒(méi)有其他的解法？（當(dāng)然有） Circular Array : Method 1 template class KeyType void QueuekeyType::Add(const KeyTypeamp。 x) { int newrear =(rear+1) % MaxSize if (front == newrear) QueueFull()。 else queue[rear=newrear]=x。 } 0 1 2 3 4 ● ● MaxSize1 front = 3 rear = 1 newrear = (rear + 1) % MaxSize 0 1 2 3 4 ● ● MaxSize1 front = 3 newrear = (rear + 1) % MaxSize front == newrear rear = 2 Full OK Circular Array : Method 1 template class KeyType KeyType* QueuekeyType::Delete(const KeyTypeamp。 x) { if (front == rear) { QueueEmpty()。 return。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1