我希望你能清楚地说明循环队列和循环单链表的区别。尽管在外观上两者看起来几乎相同...
我希望你能清楚地说明循环队列和循环单链表的区别。尽管在外观上两者看起来几乎相同...
循环队列或循环缓冲区:是一种实现队列的方法。例如,假设您想使用数组实现队列。您需要编写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 |
但是这可能需要不必要地每次出队时都复制很多值!为了避免这种情况,一种方法是将头指针的位置从0改为1。
head tail
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
value: | free | 12 | 5 | 4 | 71 | free | free |
tail head
position: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
value: | 91 | free | free | free | 71 | 22 | 8 |
在循环链表中,最后一个节点的下一个指针指向链表的头部。而在循环缓存中,我们只需维护两个索引front和rear,它们分别指向缓存的开头和结尾。
除非另有规定(插入或删除位置),操作通常发生在末尾/尾部。在循环缓存中,删除发生在前面的索引上,添加发生在尾部;即消费者从缓存的前面消费,生产者将内容追加到末尾。