Представление статической очереди

Статистическую очередь можно представить несколькими способами:

а) линейным массивом с двумя указателями: на начало и на конец очереди. Указатель на начало определяет позицию очереди (массива), откуда можно взять элемент, указатель на конец – позицию, куда кладем элемент:

struct ch1

{ int begin, end;

type data [ N ]; }

 

Задать очередь – это определить переменную Q типа ch1:

ch1 Q;

Чтобы инициализировать очередь достаточно определить начальное значение указателя на начало и/или конец очереди. Для этого полю begin дадим значение, не принадлежащее диапазону от 0 до N-1 (а полю end можно задать значение, указывающее на первый элемент очереди – это упростит работу с указателями при включении элемента в очередь). При включении элемента в непустую очередь увеличивается на единицу значение указателя end, при взятии элемента из очереди значение указателя на начало. При включении элемента в пустую очередь увеличиваются оба указателя.

В этом варианте не используются освободившиеся после взятия элементов из очереди позиции, поэтому возможно мнимое переполнение очереди. Если end равно N-1 и begin равно 0 – очередь полна, а если begin больше 0, то очередь псевдополна (т.е. из очереди были взяты элементы и в начале массива есть свободные позиции).

Обращение к элементу:

- при взятии из очереди:

Q.data [ Q.begin ],

- при занесении в очередь:

Q.data [ Q.end ].

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

 

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

struct ch2

{ int end;

type data [ N ] };

в) линейным массивом с двумя указателями (аналогично варианту а). При достижении конца массива (последнего элемента) очередь сдвигается на начало массива (к первому элементу), если есть свободные позиции в начале массива. Таким образом, освобождаемся от псевдопереполнения очереди;

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

Таким образом, в циклической очереди при достижении конца массива (end = N-1) и наличии свободных позиций в начале (begin > 0), новый элемент помещается в массив на место с индексом 0, при этом указателю end присваивается значение 0.

Очередь будет полна, если поле end = N-1, а поле begin = 0 или поле end = K, а begin = K+1. Здесь 0 < K < N-1.