Какая реализация кольцевой очереди лучше?

Question

Я изучаю круговые очереди. Какая реализация кольцевой очереди лучше всего, реализация массива или реализация связанного списка?

Answer 1

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

Answer 2

Круговая очередь - это ограниченная очередь, в которой реализованы массивы.

Это лучше, чем обычная очередь, потому что в этом мы можем эффективно использовать пространство памяти. Если у нас есть нормальная очередь и мы удалили оттуда некоторые элементы, то там создается пустое пространство, и даже если в очереди есть пустые ячейки, то также мы не можем вставить новый элемент, потому что вставка должна выполняться только с одной стороны (т. е. сзади или сзади), а удаление должно выполняться с другой стороны (т. е. спереди или сзади). Но в случае круговой очереди передняя и задняя части рядом друг с другом.

Answer 3

Это зависит от того, какие операции вам нужно будет выполнить в круговом списке. Например, если вам нужен произвольный доступ («дайте мне 237-й элемент списка»), реализация массива будет намного быстрее.

С другой стороны, при использовании навесного оборудования вам может понадобиться иногда изменять размер списка, что будет медленно. Вы можете амортизировать это, чтобы получить амортизированное время O (1) на одну вставку, но в системе реального времени иногда медленная работа может быть неприемлемой.

Answer 4

Если вы делаете это в связанном списке, то он может фактически быть круговым, потому что последний узел будет указывать на первый.Но я думаю, вам нужно уточнить, что вы подразумеваете под «лучшим».