Составители:
44
являющегося концом очереди (начало очереди всегда в первом элемен-
те массива);
– представить массив в виде циклической структуры, где первый
элемент массива следует за последним. Элементы очереди располага-
ются в «круге» элементов массива в последовательных позициях, ко-
нец очереди находится по часовой стрелке на некотором расстоянии от
начала. При этом необходимо отдельно хранить значение индекса эле-
мента массива, являющегося началом очереди, и значение индекса эле-
мента массива, являющегося концом очереди. Когда происходит добав-
ление в конец или извлечение из начала очереди, осуществляется сме-
щение значений этих двух индексов по часовой стрелке.
С точки зрения экономии вычислительных ресурсов более предпоч-
тителен второй способ. Однако здесь усложняется проверка на пустоту
очереди и контроль переполнения очереди – индекс конца очереди не
должен «набегать» на индекс начала.
Очередь как динамическую структуру данных легко организовать на
основе линейного списка. Поскольку работа идет с обоими концами
очереди, то предпочтительно будет использовать линейный двунаправ-
ленный список. Хотя, как уже говорилось при описании этого списка,
Начало
…
Конец
Добавление
Извлечение
i
Указатель
на начало очереди
Очередь
Динамическая реализация
Статическая реализация
j
Извлечение
…
nil
Начало
nil
Конец
…
Извлечение
Указатель
на конец очереди
i
…
j
Добавление
Добавление
Конец
Начало
1
2
…
…
N
Рис. 9. Очередь и ее организация
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
