2

我们只是在课堂上学习循环队列，我有几个问题。由于我们将尾部定义为最后一个值旁边的空白区域，如下图所示： 

|1| |3|4|5|6|

头部将指向数字 3，尾部将指向 1 和 3 之间的空白空间。我很困惑如果该空间被填满会发生什么，例如下面：

|1|2|3|4|5|6|

那么头部仍然指向3，但是尾部需要指向之前空白框之后的下一个框，因此它会指向3，或者头部。我该怎么办？

4

4 回答 4

6

当这种情况发生时，您的队列已满。在处理可以推送的新项目时，您有几种选择：

  1. 丢弃推送的事件：只有在弹出其他项目时才能再次推送项目。既没有head也没有tail更新。

    示例：考虑一个已填满的事件队列，新请求被简单地忽略。

  2. 丢弃（弹出）队列中最旧的事件：在这种情况下，您将和指针都更新到一个位置。headtail

    示例：缓冲来自网络摄像头的传入图像帧以进行处理。对于“实时”提要，您可能更愿意在处理出现中断时丢弃较旧的帧。

  3. 创建一个更大的队列：即动态分配更多内存

    示例：您使用循环队列，因为它是一种高效的实现，在您推送项目时大部分时间不需要内存分配。但是，您不希望丢失队列中的项目，因此您允许偶尔重新分配更多内存

正确的操作取决于您的应用程序。

PS.：您的实现基于在队列中保留一个空槽以区分满缓冲区和空缓冲区。另一种选择是保留队列中元素数量的计数器以进行区分。更多信息可以在循环缓冲区（维基百科）上找到。

于 2012-07-05T21:06:50.183 回答
3

正如我所想的那样，循环队列是循环的，部分原因是它没有被“填满”。它将始终保持一定数量的元素，并根据需要丢弃旧的元素。

所以你永远不会填满空白；如果您插入一个新元素，您将删除一个旧元素，因此仍然会有一个空白空间。

换句话说，在您的图表中，如果您插入一个新数字，例如 0，您的队列如下所示（假设1是最后一个元素，3第一个元素）：

|1| |3|4|5|6|

然后它将如下所示：

| |0|3|4|5|6|

但是，如果您想要的话，循环队列的某些实现会在达到其全长时简单地抛出异常/错误。看看这个例子。

于 2012-07-05T20:59:05.807 回答
0

这是我找到的关于队列的最简洁的解释。您可以在此基础上扩展您的队列。资料来源：“算法”，Robert Sedgewick 着。

常量最大值=100；

var queue: aray[0..max]of integer;
     head,tail: integer;

procedure put(v:integer);    
  begin
    queue[tail] := v;   
    tail := tail + 1;   
    if (tail > max) then tail := 0;
  end;

function get: integer;  
  begin
    get := queue[head];
    head := head + 1;   
    if (head > max) then head := 0; 
  end;

procedure queueinitialize;   
  begin
    head := 0;
    tail := 0;
  end;

function queueempty: boolean;   
  begin   
    queueempty := (head = tail);
  end;

“需要维护两个索引，一个到队列的开头（头），一个到结尾（尾）。队列的内容是数组中头尾之间的所有元素，考虑到“ wraparound" 当遇到数组末尾时返回 0。如果 head = tail 则队列定义为空；如果 head = tail + 1，或 tail = max 且 head = 0，则定义为满。 "

于 2013-07-09T00:44:25.663 回答
0

当头部和尾部指向同一个位置时，我们说队列已满。不能添加更多元素。要添加任何元素，您必须从队列中删除一个元素。这样头部将增加并且再次生成一个空间。

于 2014-03-17T13:01:45.833 回答