使用圓形陣列執行隊列

我已經在互聯網上找到了這些算法，但我不明白爲什麼在排隊方法中我們將大小與N-1進行比較？請幫助我謝謝！使用圓形陣列執行隊列

Algorithm size(): 
return (N-f+r)mod N 



Algorithm enqueue(e): 
if size()=N-1 then 
    throw a FullQueueException 
Q[r]<---e 
r<----(r+1)mod N

2010-06-05 user355002

我們需要上下文。那些不是算法。他們是僞碼的小塊。 – 2010-06-05 16:01:33

您提供了一個非常破碎（而且不正確）的實現。

也就是說，數組中的循環隊列通常從給定索引開始，到達另一個給定索引（因此f和r）。但是，不管你做什麼，你都不能在隊列中擁有比在底層數組中更多的項目。

此處的大小函數應該計算隊列中元素的數量。如果該數字變得危險地接近總陣列大小，則該隊列已滿。

2010-06-05 16:03:54 Uri

感謝您的回答，但它也是這樣寫「尺寸== N」？ – user355002 2010-06-05 16:31:48

@matin：首先，你還想保持size（），因爲這是函數調用。 ==會檢查相等性。 =不會編譯。 – Uri 2010-06-06 01:03:09

@matin：由於使用了模運算符，size（）總是返回範圍爲0..N-1的數字。 – meriton 2010-06-06 13:25:08

我同意@Matthew Flaschen的評論，但我會猜測。我懷疑這個隊列是N長的，並且一個元素被保留用於哨兵搜索。不過，我不會這樣做。

2010-06-05 16:05:47

+1同意;本文詳細闡述：http://en.wikipedia.org/wiki/Circular_buffer#Difficulties – trashgod 2010-06-05 16:40:16

給定一個循環隊列的實現，其中開始和結束被保留爲指示以分配的底層數組的大小爲模的模數，例如N，有必要使隊列的實際容量（不是數組）小於N否則，開始和結束標記將是相等的，並且在空白和完整之間會有不明確之處。

因此，當分配的底層陣列的大小爲N時，隊列的真實容量爲N-1。這就是測試的原因。

實際上可以使用所有的N個插槽和消除隱含在採用索引模n的分割。

2010-06-06 13:09:37 pgast

當大小爲N-1時，隊列滿了的原因是在這個簡單的實現中，'r'表示下一個空閒元素的索引，'f'表示下一個要檢索的元素。如果'f'和'r'相等，則隊列爲空，所以如果增加'r'將導致它等於'f'，則隊列已滿。

在這個實現中，至少有一個元素總是空的。這通常比添加更多的邏輯來區分'f'和'r'相等並且隊列滿了的情況與空的情況相比更有效率。

順便說一句，在大多數處理器的MOD功能是很多比使用邏輯這樣更昂貴：

Algorithm enqueue(e): 
rNext<---r + 1 
if rNext = N 
    rNext<---0 
if rNext = r then 
    throw a FullQueueException 
r<---rNext 
Q[r]<---e

2012-07-09 18:40:07

回答