3

我想在循环队列和循环单链表之间有一个明显的区别??虽然一开始,两者看起来几乎一样......

4

3 回答 3

9

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

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

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

现在用户想要出列一个元素,3从 position中删除值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 | 

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

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

于 2012-08-08T15:13:54.607 回答
1

看看这个:http: //www.vias.org/cppcourse/chap20_05.html你会注意到一个循环队列在标准定义中被实现为一个数组。

于 2012-08-08T15:00:43.570 回答
0

循环链表和循环队列/循环缓冲区/环形缓冲区的主要区别在于:

  • 在循环链表中,最后一个节点的下一个指针指向(链表的)头。在循环缓冲区中,我们只需在前后维护两个索引,它们指向缓冲区的开头和结尾。

  • 除非另有说明(插入或删除的位置),否则它发生在末尾/尾部。如果 Circular Buffer 删除发生在前面的索引处,而添加发生在尾部;即,消费者从缓冲区的前面消费,生产者追加到最后。

于 2019-05-19T16:46:32.420 回答