Теория круговой очереди

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

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

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

Скажем, я вставляю два символа 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 Что происходит, когда вы полностью заполняете очередь, так как в Хвост и Голова находятся в одном и том же положении, то есть «К»? Если кто-то может объяснить эту концепцию немного более подробно и ясно, я был бы признателен.

Спасибо!


language-concepts
person DetroitRedCoder    schedule 08.04.2015    source источник
comment
Я разместил ответ на аналогичный вопрос, как и другие здесь: .com/questions/11352415/full-circular-queue/   -  person Mike Jablonski    schedule 08.04.2015

Ответы (2)


arrow_upward
1
arrow_downward

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

Есть много объяснений и примеров циклических очередей. Я не нашел лучшего объяснения, чем то, которое я опубликовал в ответе, который я предложил некоторое время назад здесь< /а>. Это объясняет, как голова и хвост показывают, если очередь пуста, есть место или заполнена.

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

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

person Mike Jablonski    schedule 09.04.2015

arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

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

person Tejash Desai    schedule 22.05.2015