循环队列和循环链表

Question

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

Answer 1

循环队列或循环缓冲区:是一种实现队列的方法.例如,假设您要使用数组实现队列.你有你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 | 

尾巴现在缠绕到阵列的开头.

圆形链表:头部指向尾部的链表.它是一种通用的圆形结构.它可以用于实现循环队列/缓冲区,也可以用于其他东西.