Нужна помощь в соединении этих двух понятий

Question

Недавно выбрал концепцию «Ring Queue», так как я более знаком с алгоритмом Tortoise и Hare для обнаружения цикла связанного списка, мне интересно, имеет ли принцип работы Ring Queue какую-то связь с вышеупомянутым алгоритмом обнаружения цикла в Linked Listпоскольку они оба выполняют обход цикла, встречаются два указателя.

Answer 1

A циклический буфер - это структура данных, а алгоритм Флойда - это ... алгоритм, поэтому существуют ограничения для любой аналогии.

Но я попробую:

+-------------------+-----------------------------------+---------------------------+
|                   |          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. Акт I: Черепаха с круговым буфером начинает историю спит , в отличие от алгоритма Флойда, где он тоже движется (хотя и медленно).
2. Климакс: Если заяц встречает черепаху, цикл "найден". Это гарантированно происходит в кольцевом буфере, несмотря на то, что черепаха спит (буфер круговой, поэтому все точки в нем являются частью цикла). Это отличается от алгоритма Флойда, в котором встреча может не состояться, поскольку связанный список может не иметь цикла. Кроме того, цикл (если имеется) может не включать отправную точку, поэтому спящая черепаха не подходит для ее сюжета.
3. Акт II / Окончание: Когда заяц встречает (спящую) черепаху в кольцевом буфере, он будит ее, а затем они идут вместе в унисон, проходя цикл во веки веков. В алгоритме Флойда встреча двух - это конец истории, хотя история может также закончиться тем, что заяц достиг финиша (встретившись с кем-то еще?).

Answer 2

Я не уверен, имеют ли они прямое отношение.

В алгоритме обнаружения связанного списка мы пытаемся обнаружить возможность цикла в связанном списке, выбирая схему, которая заставляет два указателя сталкиваться, если список существует.

В циклическом буфере коллизия указателей означает либо то, что буфер заполнен, либо что он пуст.обнаружение определенных условий только с двумя указателями, перемещающимися локально, вместо более «глобального» алгоритма.Например, поиск цикла в связанном списке можно также выполнить с помощью DFS.

Answer 3

Я думаю, вы видите здесь только шаблоны.

Круговой буфер - это просто структура данных.Алгоритм «Черепаха и заяц» также применим к вещам, которые не являются просто круговыми очередями и даже в случаях, когда «указатели» неявны (например, поиск фиксированных точек для функций).