连接这两个概念需要帮助

Question

最近拿起了"Ring Queue"的概念,因为我比较熟悉Tortoise和Hare算法的链表循环检测,我想知道Ring Queue工作原理是否与Linked List中的上述循环检测算法有某种联系,因为它们是两个指针在一个循环中进行遍历然后两个指针相遇.

Answer 1

甲圆形缓冲器是一个数据结构,和Floyd的algorthm是...的算法,所以存在限制任何类比.

但是我会努力的:

+-------------------+-----------------------------------+---------------------------+
|                   |          Circular buffer          |     Floyd's algorithm     |
+-------------------+-----------------------------------+---------------------------+
| Tortoise          | Start pointer                     | Slow pointer              |
| Hare              | End pointer                       | Fast pointer              |
| Act I             | Tortoise sleeps, hare walks       | Tortoise walks, hare runs |
| Act II            | Hold hands; walk together forever | No act II                 |
| Ends Romantically | Yes                               | Only if a cycle exists    |
+-------------------+-----------------------------------+---------------------------+

1. 第一幕:为圆缓冲龟开始的故事 睡觉,不像弗洛伊德的算法,它也在发展(尽管速度缓慢).
2. 高潮:如果野兔遇到乌龟,那么这个循环就已经"找到"了.尽管乌龟已经处于休眠状态(缓冲区是圆形的,因此其中的所有点都是循环的一部分),这保证会在循环缓冲区中发生.这与Floyd的算法不同,其中会议可能不会发生,因为链表可能没有循环.此外,周期(如果存在)可能不包括起点,这就是为什么睡眠龟不适合其情节的原因.
3. 第二幕/结局:当野兔在一个圆形缓冲区遇到(睡觉)的乌龟时,它将它唤醒,然后它们一起走在一起,一直走过这个循环.在弗洛伊德的算法中,两者的会面是故事的结尾,尽管故事也可能以兔子到达终点线(与其他人会面？)结束.