Очередь
Очередью будем называть структуру данных, для которой определены операции
добавления и удаления элементов.
Очередь, в которой нет ни одного элемента, называется пустой. В этом случае
указатели start и Last указывают на одно и то же место.
Очередь можно реализовать несколькими способами. Простейшим способом
реализации служит массив и два указателя. Первый указывает на начало очереди, а
второй, соответственно, на ее конец.
Начало очереди — это номер элемента массива, который будет удаляться.
Конец очереди — это номер элемента массива, в который будут заноситься
данные.
Реализация очереди на базе массива
Как уже было сказано, программисту массив дан свыше, все остальные структуры
данных нужно реализовывать на его основе. Конечно, такая реализация может быть
многоэтапной, и не всегда массив выступает в качестве непосредственной базы
реализации. В случае очереди наиболее популярны две реализации: непрерывная на
базе массива, которую называют также реализацией на базе кольцевого буфера, и
ссылочная реализация, или реализация на базе списка.
При непрерывной реализации очереди в качестве базы выступает массив
фиксированной длины N, таким образом, очередь ограничена и не может содержать
более N элементов. Индексы элементов массива изменяются в пределах от 0 до N - 1.
Кроме массива, реализация очереди хранит три простые переменные: индекс начала
очереди, индекс конца очереди, число элементов очереди. Элементы очереди
содержатся в отрезке массива от индекса начала до индекса конца.
При добавлении нового элемента в конец очереди индекс конца сперва
увеличивается на единицу, затем новый элемент записывается в ячейку массива с этим
индексом. Аналогично, при извлечении элемента из начала очереди содержимое ячейки
массива с индексом начала очереди запоминается в качестве результата операции,
затем индекс начала очереди увеличивается на единицу. Как индекс начала очереди, так
и индекс конца при работе двигаются слева направо. Что происходит, когда индекс конца
очереди достигает конца массива, т.е. N - 1?
Ключевая идея реализации очереди состоит в том, что массив мысленно как бы
зацикливается в кольцо. Считается, что за последним элементом массива следует его
первый элемент (напомним, что последний элемент имеет индекс N - 1, а первый —
индекс 0). При сдвиге индекса конца очереди вправо в случае, когда он указывает на
последний элемент массива, он переходит на первый элемент. Таким образом,
непрерывный отрезок массива, занимаемый элементами очереди, может переходить
через конец массива на его начало.
Если некоторый элемент занесен в очередь раньше других, то он раньше других и
подлежит обработке. Данное определение можно сравнить с обычной очередью в
магазине — если покупатель пришел первым, то он и обслуживается первым. Другими
словами, очередь — эта та структура данных, в которую элемент "заходит" первый и
первый же "выходит". Именно поэтому очередь нередко обозначают аббревиатурой FIFO
(First In, First Out — первый зашел, первый вышел).
Элементы удаляются из очереди в том же порядке, в котором они были добавлены
в очередь.
Пусть у нас есть очередь из трех элементов а, В и С, в которую первым был
помещен элемент а, а последним —- элемент С.