Статическая реализация очереди

Пусть в очереди требуется сохранять целые числа, причем заранее известно их максимальное количество. Тогда для реализации очереди надо объявить массив и две переменные – указатель начала очереди First и указатель конца очереди Last. Будем считать, что очередь-массив заполняется (растет) от первых элементов массива к последним. Тогда указатель First будет определять первую занятую ячейку массива, а указатель Last - первую свободную ячейку. Тогда пустую очередь определим как First = Last = 1 (если индексация элементов массива начинается с 1), и при каждом добавлении нового элемента переменная Last увеличивается на 1, а при удалении на 1 увеличивается указатель First. Последовательность операций для массива из пяти элементов показана на следующей схеме:

1. Пустая очередь: First = Last =1

2. Добавлено первое число 15, First = 1, Last = 2

3. Добавлено второе число 33, First = 1, Last = 3

4. Добавлено третье число 07, First = 1, Last = 4

5. Удалено число 15, First = 2, Last = 4

6. Удалено число 33, First = 3 , Last = 4

7. Добавлено число 44, First = 3 , Last = 5

Рассмотренная выше простейшая реализация очереди-массива имеет один существенный недостаток: освобождающиеся при удалении ячейки в начале массива НЕ используются при последующих добавлениях, и поэтому при интенсивном использовании очереди быстро может возникнуть ситуация, когда указатель Last выходит за пределы массива, тогда как в начале массива есть свободные ячейки.

Для устранения этого недостатка можно использовать два подхода:

· при очередном удалении элемента из начала очереди сдвигать все элементы влево на одну ячейку, что при большом числе элементов в очереди может привести к большим вычислительным затратам

· более эффективно использовать так называемую кольцевую очередь, в которой при достижении указателем Last конца массива добавление производится в начало массива:

8. Добавлено число 11, First = 3 , Last = 6 (= 1)

9. Новое число 22 добавляется в первую ячейку:

First = 3 , Last = 2

10. Добавлено число 99, First = 3 , Last = 3

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

Для программной реализации удобно ввести переменную-счетчик числа элементов в очереди, с помощью которой легко отслеживаются состояния пустой и заполненной очереди.

Само добавление элемента в очередь выполняется следующим образом:

· проверить возможность добавления (в массиве есть свободные ячейки?)

· добавить элемент в массив по индексу Last

· изменить указатель Last на 1

· если Last выходит за пределы массива, то установить Last в 1

• увеличить счетчик числа элементов в очереди

Удаление элемента из очереди:

· проверить возможность удаления (в очереди есть элементы?)

· извлечь элемент из массива по индексу First и выполнить с ним необходимые действия

· увеличить указатель First на 1

· если First выходит за пределы массива, то установить First в 1

· уменьшить счетчик числа элементов в очереди