Непрерывная реализация очереди с помощью массива

Реализация очереди при помощи массива немного сложнее, чем реализация стека. Вспомним, что вставка и удаление элементов выполняются с разных концов. Легко сделать вставку в конец массива (хвост очереди), если еще есть свободные ячейки памяти, но сложнее выполнить удаление первого элемента массива (это голова очереди). Поэтому способ реализации, при котором голова очереди совпадает с первым элементом массива, используют только в тех задачах, где элементы добавляются в очередь постепенно, а опустошение очереди происходит сразу целиком. В этом случае достаточно иметь только один дополнительный указатель — на хвост.

В том случае, когда необходимо эффективно реализовать и вставку, и удаление элементов, обычно используют два дополнительных. указателя — на начало очереди (голову) и конец очереди (хвост). Назовем указатели head и tail.В качестве таких указателей могут выступать как индексы элементов массива, так и непосредственно указатели на элементы. При реализации очереди на С++ обычно используются непосредствено указатели на голову и на хвост. Тогда вставка и удаление элементов очереди реализуется с помощью изменения значений этих указателей (рис.2.3). По аналогии со стеком, в пустой очереди эти указатели будут иметь значение NULL (причем одновременно оба, только один из них никогда не может быть нулевым).

Рис.2.3. Представление очереди при помощи массива и двух указателей (в начальный момент и спустя некоторое время)

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

 

Рис.2.4. Еще одно состояние очереди (хвост оказался ниже головы)

Определение очереди при реализации с помощью массива и двух указателей может иметь, например, следующий вид (считаем, что тип элементов type_of_data и максимальный размер массива maxlength уже определены):

struct queue

{ type_of_data data[maxlength]; // массив данных очереди

type_of_data *head,*tail; // указатели на голову и хвост

// базовые функции для работы с очередью

queue(){head=tail=NULL;}//конструктор - пустая очередь

void enqueue(type_of_data x); //добавление элемента в хвост

type_of_data gethead(); //получение элемента из головы

void dequeue();// удаление (извлечение) элемента из головы

bool isnull() { return head==NULL; } // проверка на пустоту

void makenull(){queue();} // доп. функция очистки очереди

};

Рассмотрим подробнее реализацию методов добавления и удаления элементов.

При добавлении необходимо обеспечить циклическое перемещение указателя tail по массиву data и своевременно обнаружить попытку переполнения очереди. В полностью заполненной очереди хвост находится непосредственно перед головой (это справедливо и для случая, когда первый элемент очереди совпадает с первым элементом массива, поскольку перемещение по массиву выполняется циклически). Попытка добавить еще один элемент в очередь приведет к тому, что значения указателей на хвост и голову сравняются, что будет служить признаком переполнения очереди (аварийная ситуация). Однако если перед добавлением элемента очередь была пуста, то равенство указателей на хвост и голову означает всего-навсего, что очередь состоит из одного элемента.

void queue::enqueue (type_of_data x) // вставка элемента

{ if (isnull()) // добавляем самый первый элемент

{tail=head=data;} //имя массива-указатель на первый элемент

else // очередь не пуста

{ tail++; //теперь проверим выход хвоста за границы массива

if (tail==data+maxlength)

tail=data; // поместили хвост в начало массива

if (head==tail) {cerr << "Очередь переполнена"; exit(2);}

}

*tail=x;// если все в порядке, поместили x в хвост очерели

}

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

void queue::dequeue () //извлечение элемента

{ if (isnull()) { cerr << "Очередь пуста"; exit(1); }

if (head==tail) // в очереди только один элемент

{head=tail=NULL;} // установили признак пустой очереди

else//поднимаем голову и проверяем выход за границы массива

{ head++; if (head==data+maxlength) head=data; }

}