Help Needed in Connecting These Two Concepts

Recently picked up "Ring Queue" concept, since I am more familiar with Tortoise and Hare algorithm for linked list cycle detection, I wonder if the Ring Queue working principle has some kind of connection with the above cycle detection algorithm in Linked List since they are both doing trav开发者_C百科erse around a cycle then two pointers meet.

A circular-buffer is a data-structure, and Floyd's algorthm is an... algorithm, so there are limits to any analogy.

But I will try:

+-------------------+-----------------------------------+---------------------------+
|                   |          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. Act I: The circular-buffer tortoise begins the story sleeping, unlike Floyd's algorithm, where it too moves (albeit slowly).
2. Climax: If the hare meets the tortoise, the cycle has been "found". This is guaranteed to occur in a circular-buffer despite the fact that the tortoise has been sleeping (the buffer is circular, so all points in it are part of the cycle). This is unlike Floyd's algorithm, in which the meeting may not occur since the linked-list may not have a cycle. Additionally, the cycle (if present) may not include the starting point, which is why a sleeping tortoise would not have been appropriate for its plot.
3. Act II / Ending: When the hare meets the (sleeping) tortoise in a circular-buffer, it wakes it up, and then they walk together in unison, traversing the cycle for ever and ever. In Floyd's algorithm, the meeting of the two is the end of the story, although the story may also end with the hare reaching the finish-line (meeting someone else?).

I think you are only seeing patters here.

A circular buffer is just a data-structure. The Tortoise & Hare algorithm is also applicable to things that aren't just circular queues and even in cases where the "pointers" are implicit (like finding fixed points for functions).

I'm not sure if these are directly related.

In the linked list detection algorithm, we are trying to detect the possibility of a cycle in a linked list by choosing a scheme that forces two pointers to collide if there is a list.

In the circular buffer, the pointer collision means either that the buffer is full or that it's empty.

My guess at the only connection that we can draw here is that circular data structures are amenable to detection of certain conditions with only two pointers moving locally, rather than a more 'global' algorithm. For example, finding a cycle in a linked list could also be done via a DFS.