logo标签列表

循环队列和循环链表

c++linked-listqueue
4

我希望你能清楚地说明循环队列和循环单链表的区别。尽管在外观上两者看起来几乎相同...

3
链表可以用来实现循环队列，但循环队列不一定要用链表来实现。 - obataku
@oldrinb 我们知道循环链表可以用来实现队列和栈。但是作为一个一般性问题，问栈是否可以用来实现循环链表是否可行呢？ - user6639553
3个回答
9

循环队列或循环缓冲区：是一种实现队列的方法。例如，假设您想使用数组实现队列。您需要编写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 |

尾部现在围绕到数组的开始处。 循环链表：一个链表，其中头指针指向尾部。它是一个通用的循环结构。它可以用于实现循环队列/缓冲区，也可以用于其他用途。
1
循环链表和循环队列/循环缓存/环形缓存的主要区别在于：

  • 在循环链表中，最后一个节点的下一个指针指向链表的头部。而在循环缓存中，我们只需维护两个索引front和rear，它们分别指向缓存的开头和结尾。

  • 除非另有规定（插入或删除位置），操作通常发生在末尾/尾部。在循环缓存中，删除发生在前面的索引上，添加发生在尾部；即消费者从缓存的前面消费，生产者将内容追加到末尾。

1
那么，究竟主要的区别是什么呢？ - keerthi
2
如果您将其实现为数组，则只需要在缓冲区中进行一次查找即可获取所需元素。否则，如果它是一个列表，则需要逐个节点遍历以获取所需的元素。这种结构在资源紧张的环境中使用，其中每个 CPU 周期都很重要，并且内存非常有限（因此不允许缓冲区无限扩展）。 - Mihai Todor
我们知道循环链表可以用来实现队列和栈。但是作为一个普遍的问题，问栈能否用来实现循环链表是否可接受？ - user6639553
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接