使用Scala中的數組實現隊列排隊的方法

Question

def enqueue(elem: T): Unit = {  
    A(rear) = elem 
    rear += 1 
    size += 1 
    if (size == 0) { 
     front = 0 
     rear = 0 
     } 
    if (size == A.length) { 
     grow() 
     } 
    } 

我正在實現一個使用數組的隊列，並且在排隊方法中存在一些問題，但我無法弄清楚錯誤到底在哪裏。所以你可以給我一些提示，說明我犯了什麼錯誤。 在上面的代碼中，size是數組隊列中元素的數量，grow是在數組滿了時將數組加倍的函數。先謝謝你。

Answer 1

你沒有告訴任何有什麼錯誤，所以這是一個黑暗中的鏡頭，而不是討論所選擇的數據結構。

該測試size == 0似乎沒用，大小將不會是零後一個enqueue。但是，您所做的是告訴您在出現出現問題時所做的操作，可能會返回元素front並增加front，並減少size。

所以一些言論

1. 人們驚訝地叫預防性成長，對於給 入隊可能永遠不會發生下一個電話。你應該在 的入隊開始時進行入隊，當你缺少空間時
2. 當你退出隊列並重新入隊時，你的數據會移動到數組的右側。因此，即使在只有很少項目（大小很小）的隊列中，項目可能位於陣列的右邊緣，並且可能會用盡空間。成長（或至少爲了做某事）的測試應該在後面而不是在規模上。
3. 因此，即使陣列比所需空間多，您可能也必須增長或至少做點什麼。如果陣列幾乎滿了，你應該確實增長（即使剩下一些空間，否則你冒着入隊/出隊週期繼續複製所有的值，並讓你的表演去O（N））但是如果有很多的空閒空間，你應該簡單地將元素移回到數組的開始位置。

總結：在排隊的開始，如果後部是在陣列的長度，則必須

• 如果尺寸小於說一半的空間中，元素複製到數組中，前面的開始= 0，後部=大小
• 如果尺寸越大，分配一個新的數組，並在新的數組

Answer 2

開始複製元素如果要測試size == 0，你應該做的第一個。

如果您記錄了類的不變量以及方法的前提條件和後置條件，以確保每個方法都保留隊列實現內部的關鍵屬性，它可能會對您有所幫助。見http://en.wikipedia.org/wiki/Design_by_contract。

一個不變的可能是類似大小始終是小於或等於所述陣列的長度或大小> = 0。