c++ - 循环队列和循环链表

Question

我想明确区分循环队列和循环单链表？？虽然一开始，两者看起来几乎一样......

Answer 1

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

假设底层数组的长度为 7，并且用户入队了五个值，那么底层数组中的值如下所示:

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

现在用户想要出队一个元素，从位置 0 中删除值 3。作为队列实现者，您必须弄清楚如何处理这个问题。一个基本的解决方案是将所有值向下移动一个位置，这样底层数组现在看起来像这样:

            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 | 

尾部现在环绕到数组的开头。

循环链表:头指向尾的链表。它是一个通用的循环结构。它可用于实现循环队列/缓冲区，也可用于其他用途。