advancedatastructurereviewofchapter3

advancedatastructurereviewofchapter3内容摘要：

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 實作 Queue，會面臨無法判斷 Queue 是空的或是滿的問題。 因為 front == rear 時 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：犧牲空間 任何時候只允許 MaxSize1 個元素在 Queue 中  Method 2：犧牲時間 增加一個變數，記錄上一次的動作。  因為 Queue 元素的新增與刪除非常頻繁，所以我們較常採用 Method 1  還有沒有其他的解法。 （當然有） 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。 }。