yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Реализация очередей с помощью указателей

Алгоритмы структуры данных

Реализация очередей с помощью указателей

Как и для стеков, любая реализация списков допустима для представления очередей. Однако учитывая особенность очереди (вставка новых элементов только с одного, заднего, конца), можно реализовать оператор ENQUEUE более эффективно, чем при обычном представлении списков. Вместо перемещения списка от начала к концу каждый раз при пополнении очереди мы можем хранить указатель (или курсор) на последний элемент очереди. Как и в случае со стеками, можно хранить указатель на начало списка — для очередей этот указатель будет полезен при выполнении команд FRONT и DEQUEUE. В языке Pascal в качестве заголовка можно использовать динамическую переменную и поместить в нее указатель на начало очереди. Это позволяет удобно организовать очищение очереди.

Сейчас мы рассмотрим реализацию очередей с использованием указателей языка Pascal. Читатель может разработать аналогичную реализацию с применением курсоров, но в случае очередей мы имеем возможность более эффективного их (очередей) представления, основанного на массивах, и с непосредственным использованием указателей, чем при попытке моделирования указателей с помощью курсоров. В конце этого раздела мы обсудим также реализацию очередей на основе так называемых "циклических массивов". Для начала реализации очередей с помощью массивов необходимо сделать объявление ячеек следующим образом;

type

celltype = record

element:   elementtype;

next:   ↑ celltype

end;

Теперь можно определить список, содержащий указатели на начало и конец очереди. Первой ячейкой очереди является ячейка заголовка, в которой поле element игнорируется. Это позволяет, как указывалось выше, упростить представление для любой очереди. Мы определяем АТД QUEUE (Очередь)

type

QUEUE = record

front,   rear:  ↑ celltype

end;

В листинге 2.10 представлены программы для пяти операторов, выполняемых над очередями. В процедуре MAKENULL первый оператор new(Q.front) определяет динамическую переменную (ячейку) типа celltype и назначает ей адрес Q.front. Второй оператор этой процедуры задает значение поля next этой ячейки как nil. Третий оператор делает заголовок для первой и последней ячеек очереди.

Процедура DEQUEUE(Q) удаляет первый элемент из очереди Q, "отсоединял" старый заголовок от очереди. Первым элементом списка становится новая динамическая переменная ячейки заголовка.

Листинг 2.10.

procedure MAKENULL (var Q: QUEUE );

begin

new(Q.front); { создание ячейки заголовка }

Q.front↑.next:= nil;

Q.rear:= Q.front

end; { MAKENULL }

 

function EMPTY ( Q: QUEUE ): boolean;

begin

if Q.front = Q.rear then

return(true)

else

return(true)

end; { EMPTY }

 

function FRONT ( Q: QUEUE ): elementtype;

begin

if EMPTY(Q) then

error('Очередь пуста')

else

return(Q.front↑.next↑.еlеmеnt)

end; { FRONT }

 

procedure ENQUEUE ( x: elementtype; var Q: QUEUE );

begin

new(Q.rear↑.next);

Q.rear:= Q.rear↑.next;

Q.rear↑.element:= x;

Q.reart.next:= nil

end; { ENQUEUE }

 

procedure DEQUEUE ( var Q: QUEUE );

begin

if EMPTY(Q) then

error('Очередь пуста')

else                       

Q.front:= Q.front↑.next

end;    {   DEQUEUE   }

На рис. 2.10 показан результат последовательного применения команд MAKENULIXQ), ENQUEUE(x, Q), ENQUEUE(y, Q) и DEQUEUE(Q). Отметим, что после исключения из очереди оператором DEQUEUE(Q) элемента х он остается в поле element ячейки заголовка, но перестает быть частью очереди.

 

24