循环队列和循环链表

Question

我想在循环队列和循环单链表之间有明显区别？虽然从一开始，两者看起来几乎相同......

Answer 1

查看结果：http://www.vias.org/cppcourse/chap20_05.html您会注意到循环队列在标准定义中作为数组实现。

Answer 2

循环队列或循环缓冲区：是一种实现队列的方式。例如，假设您想要使用数组实现队列。你会有你的enqueue()和dequeue()方法。

假设底层数组是长度为7的，并且用户入队五个值，所以底层数组中的值如下所示：

  head     tail 
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
value:  | 3 | 12 | 5 | 4 | 71 | free | free | 

现在用户想要出列的元素，除去值3从位置0。作为队列实施者，你必须弄清楚如何处理这个问题。一个基本的解决办法是由一个位置移动的所有值下来，底层数组现在看起来是这样的：

  head    tail 
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
value:  | 12 | 5 | 4 | 71 | free | free | free | 

，但可能需要复制不必要每次出队什么时候很多值的！避免的方法之一是说，你的头现在的位置是1而不是0，

    head    tail 
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
value:  | free | 12 | 5 | 4 | 71 | free | free | 

所以现在每次添加你只需将其添加到tail一个新的元素（并增加tail位置），并且如果删除元素，则只需移动head即可。这样你就不必做任何不必要的复制。

一旦tail到达数组的末端，它将开始回卷到数组的开始处 - 即队列将以“圆形”移动到底层数组上。例如，几个排队，和出队后，对底层数组是这样的：

    tail    head 
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
value:  | 91 | free | free | free | 71 | 22 | 8 | 

尾巴现在缠到数组的开头。

圆形链表：头部指向尾部的链表。这是一个通用的圆形结构。它可以用来实现一个循环队列/缓冲区，或者它可以用于别的东西。