簡單隊列算法

這是不是請求排隊算法，我知道有很多。簡單隊列算法

我正在閱讀一本C＃書，它用一個代碼示例解釋了Circular Queue算法。在第13,14和15行，他解釋瞭如何檢查隊列是否已滿。但我不明白爲什麼第一個可選條件是必要的。有人能告訴我一個需要它的情況嗎？

下面是類代碼：

我的問題是關於這個部分：（putloc + 1 == getloc）

public bool Put(char ch) {  
    /* Queue is full if either putloc is one less than 
    getloc, or if putloc is at the end of the array 
    and getloc is at the beginning. */ 
    if (putloc + 1 == getloc || ((putloc == q.Length - 1) && (getloc == 0))) 
    { 
     return false; 
    }

來源

2009-10-19 Daniel S

第一次檢查是執行以下部分評論中的聲明。

putloc比getloc

需要這種檢查，因爲您的隊列爲圓形少一個。如果您始終可以認爲隊列的末尾是陣列中的最後一個元素，則不需要檢查。在這種情況下，儘管...隊列的末尾可能發生在陣列的中間，在這種情況下，隊列將變滿並且您遇到了這種情況。

來源

2009-10-19 19:18:55

謝謝！這是最終讓我更加思考的答案，並讓我瞭解了循環隊列概念。忍受着我，我只有15歲，而且我在數學上也不例外:) – 2009-10-19 19:39:43

說getloc是5並且putloc是4，那麼這意味着你沒有更多空間來放置任何東西。因爲如果你把東西放在5號，那麼你就失去了5號，因爲你還沒有讀出來。

來源

2009-10-19 19:20:27 BFree

該邏輯可以通過以下形式可以更好地理解：

int new_putloc = (putloc + 1) % q.Length; 
if (new_putloc == getloc) return false;

原始代碼只是打破上述邏輯下到兩種情況：

putloc不倒帶，則new_putloc = putloc 1
putloc被倒帶，則put_loc = q.Length-1

來源

2009-10-19 19:23:23 Codism

在一個循環隊列中，無論什麼時候你將東西推入它，putLoc都會向下移動數組，最後環繞。無論何時你從隊列中彈出一些東西，getLoc會向下移動數組，最後也會打包。 putLoc位於getLoc之前時，該隊列被視爲已滿。

有2種情況可能發生。如果getLoc從來沒有移動過，或者恰好已經回到數組的開頭，那麼當putLoc位於數組的末尾（下一次推動會使它換行爲0）時，它位於0並且隊列已滿。這是if語句的後半部分。

如果隊列中有幾個值已經彈出，那麼getLoc可能位於數組的中間。在這種情況下，當putLoc位於數組的末尾時，隊列是滿的，但是當它被環繞並且位於getLoc之前時。 if語句的第一部分（你正在詢問的部分）正在處理的情況就是這種情況。

來源

2009-10-19 19:24:00 Herms

這兩個實際上是相同的條件。從模平等角度考慮它。

當添加的最新元素位於位置N（模長度）並且最早的元素位於位置N + 1（模長）時，用數組實現的循環隊列已滿。這意味着隊列中有「長度」元素，並且沒有更多空間可用於新隊列，因此已滿。

有許多方法可以對該測試進行編碼，但代碼示例使用的方法是使用直接算術版本而不使用模數。

你也可以這樣的代碼是：

if ((putloc + 1) % q.length == getloc) {}

，這將是邏輯上是相同的，只要getloc正確界定爲0和q.length - 1之間。

來源

2009-10-19 19:24:37 jprete

表達式的左半部分是幾乎適用於所有場景的主要部分，右半部分是唯一的邊緣情況，其中putloc是隊列的結尾，getloc是隊列的開始。當putloc爲4且getloc爲5時，左側爲true，但當隊列長度爲10且putloc爲9且getloc爲0時，右側爲true。

來源

2009-10-19 19:26:07

隊列已滿，如果 (((in+1)%queue_length)==out) 隊列爲空，如果 (in==out) 注意，「在」是指向該數據推入隊列，而「出」點的數據的流行形式隊列。

來源

2010-11-02 20:17:32

簡單隊列算法

回答

相關問題