循环队列大小

可能重复：
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

如果你使用线程，你应该使用同一个锁对象来锁定这个（和你的队列/出队方法）。 –

循环队列大小

回答

相关问题