循環隊列大小

可能重複：
how to find number of elements in a Circular Queue 循環隊列大小

我實現一個循環隊列，但我不能得到正確的隊列的大小。我發現了一個關於同一問題的前一個主題，提出的解決方案是使用兩個指針，並增加第二個指針，但它不指向與第一個指針相同的對象。但我認爲這個appoach只有在隊列中有不同的對象時才能工作。就我而言，所有的對象都是相似的。我怎樣才能得到循環隊列的大小？這個公式不爲我工作太：

int size = abs(m_front -m_tail) ;

凡m_front和m_tail是尾部和前隊列索引。

感謝

來源

2012-08-23 Galileo

問：你的隊列實現爲一個數組嗎？如果它只是一個鏈表，那麼你可以做的最好的決定是什麼時候front == tail;你*不能*確定「大小」，除非你自己保持計數。 – paulsm4

同一個：http://stackoverflow.com/questions/4459141/how-to-find-number-of-elements-in-a-circular-queue –

@ paulsm4：是的，它是作爲一個數組實現的。當front == tail時，它只是表示數組是空的。 – Galileo

這應做到：

if m_front > m_tail 
    size = (m_front - m_tail) 
else 
    size = (m_front + N - m_tail)

其中N是你的數組的長度。

或者，您可以通過在Queue()時遞增計數器來自行跟蹤它，並在Dequeue()時遞減計數器。

來源

2012-08-23 22:40:15

請注意，只有頭尾索引，如果您允許填充所有「N」個地方，則無法確定列表是空還是全。速度的最佳解決方案是防止填充最後一個位置，而存儲的最佳解決方案是在Push和Pop操作期間保持「空」或「滿」標誌。 – paddy

感謝您的回覆。我不知道爲什麼，但上面的公式不起作用：它總是給我一個零的結果......關於你的第二個命題，當我們試圖增加和減少隊列時，這個過程不會創建一個訪問競爭在時間的大小（enqueue和dequeuerun平行）?? – Galileo

如果你使用線程，你應該使用同一個鎖對象來鎖定這個（和你的隊列/出隊方法）。 –

循環隊列大小

回答

相關問題