Циркулярная теория очередей

Question

Мне нужна помощь в понимании концепции Circular Queue. Я прочитал пару сообщений о stackoverflow, и ни один из ответов не отвечает на ментальный блок, который у меня есть.

Например, у меня есть 8 ячеек в круглой очереди.

 Head        Tail 
empty|U | I | S | K | M | empty | empty 

Say вставить два символа F & P, который сделает изменения очереди к.

Tail Head         
empty|U | I | S | K | M | F | P 

Теперь давайте сделаем интересными вещи, что, если я удалю 3 записи.

Tail         Head     
empty| empty | empty | empty | K | M | F | P 

Очевидно, что моя голова и хвост теперь изменены, и у меня есть 3 новых доступных пятна. Но для хороших мер я хотел добавить еще две записи.

  Tail    Head     
A| B | empty | empty | K | M | F | P 

Вот мои вопросы

ли я осуществить это право? LOL Что происходит, когда вы заполняете очередь полностью, как в хвосте и голове, находятся в том же положении, что и «K»? Если кто-то может объяснить эти понятия немного более подробно и ясно, я бы это оценил.

Спасибо!

Answer 1

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

Существует много объяснений и примеров круговых очередей. Я не нашел лучшего объяснения, чем тот, который я опубликовал в ответ, который я предложил некоторое время назад here. В нем объясняется, как голова и хвост показывают, что очередь пуста, есть комната или заполнена.

В последней строке вашей диаграммы в очереди есть место для еще двух предметов. Добавление третьего сделает tail = head и перезапишет K, чего вы не хотите делать.

Когда tail = head, очередь пуста. Тестирование для полной очереди немного сложнее. См. Ссылку для полного объяснения.

Answer 2

Я реализовал это право?

Да, действительно, вы это сделали.

Что происходит, когда вы заполняете очередь полностью, как в хвосте и голове, находятся в том же положении, что и «K»?

K будет перезаписано. Это условие переполнения можно проверить по условию TAIL == HEAD.

Если кто-то может объяснить это понятие немного подробнее и ясности, я бы это оценил.

Что вы должны понимать, что в традиционной линейной очереди FIFO элементы необходимо было перемещать непрерывно, когда достигнут максимальный размер.Например, если очередь имеет размер 5, то после 5 (числа 1-5) последовательных вставок, а затем удаление (номер 1 удаляется), очередь становится [null, 2, 3, 4, 5]. Вы можете видеть здесь, что, хотя есть место для еще одного элемента, вы не можете вставить, если вы не переместите все элементы на один. Вот почему используется круговая очередь. Это не требует смещения элементов.

Однако, если ваша очередь постоянно переполнена, вся цель очереди теряется. Я бы рекомендовал использовать связанный список (линейный или круговой), поскольку он динамически добавляет и удаляет элементы.

Помните, что очередь используется практически при наличии ограничения на память. Например. Поток ввода/вывода представляет собой очередь. Когда памяти много, и переписывание данных не предпочтительнее, используются связанные списки.