全循环队列? [英] Full Circular Queue?
问题描述
我们刚刚在课堂上学习循环队列，我有几个问题.由于我们将尾部定义为最后一个值旁边的空白区域，如下所示:
We are just learning about circular queue in class, and I got a few questions. Since we define the tail as the empty space next to the last value, such as shown below:
|1| |3|4|5|6|
头部将指向数字 3，尾部将指向 1 和 3 之间的空白空间.如果该空间被填满会发生什么，我很困惑，例如下面:
The head will be pointing to the number 3, and the tail will be pointing to the empty space between 1 and 3. I am confused on what happens if that space is filled up, so for example below:
|1|2|3|4|5|6|
那么head仍然会指向3，但是tail需要指向前面的空白框之后的下一个框，因此它会指向3，或者header.我该怎么办?
Then the head will still be pointing to 3, but the tail needs to be pointing to the next box after the blank box before, thus it will be pointing to 3, or the header. What should I do about this?
推荐答案
发生这种情况时，您的队列已满.在处理可以推送的新项目时，您有几种选择:
When this situation occurs, your queue is full. You have a few options when to deal with new items that can be pushed:
丢弃pushed事件:只有当其他一些item被弹出时才能再次pushitem.
head和tail都没有更新.
示例:想象一个已填满的事件队列，新请求被简单地忽略了.
Example: Think of an event queue that has filled up, new requests are simple ignored.
丢弃(弹出)队列中最旧的事件:在这种情况下，您将两者更新head和tail指针一地点.
示例:缓冲来自网络摄像头的传入图像帧以进行处理.对于实时"提要，您可能更愿意在处理过程中出现故障时丢弃较旧的帧.
Example: buffering incomming image frames from a webcam for processing. For a 'live' feed you may prefer to discard the older frames when the processing has a hickup.
创建更大的队列:即动态分配更多内存
create a bigger queue: that is, allocate more memory on the fly
示例:您使用循环队列，因为它是一种高效的实现，当您推送项目时，大部分时间不需要内存分配.但是，您不想丢失队列中的项目，因此您可以偶尔重新分配更多内存
Example: you use a circular queue since it an efficient implementation that doesn't require memory allocation most of the time when you push items. However, you do not want to loose items on the queue so you allow reallocating more memory once in a while
正确的操作取决于您的应用程序.
What the right action is depends on your application.
PS.:您的实现基于在队列中保留一个空槽来区分满缓冲区和空缓冲区.另一种选择是在队列中的元素数量上保留一个计数器以进行区分.更多信息可以在循环缓冲区(维基百科)上找到.
PS.: Your implementation is based on keeping an empty slot in your queue to distinguish full and empty buffer. Another option is to keep a counter on the number of elements in your queue to make this distinction. More info can be found on Circular buffer (Wikipedia).
这篇关于全循环队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
