Очередь вляется особым видом списка, в который элементы добавляются с одного конца, а выбираются с другого конца. Обозначается: FIFO. Для работы с очередью в основном используют операторы:
1) MAKENULL(Q) – Создать пустую очередь.
2) BACK(x,Q) — Поместить элемент x в конец очереди Q.
3) ELEM(Q) — Возвратить значение элемента из начала очереди Q.
4) FRONT(Q) — Выбрать элемент из начала очереди Q.
5) EMPTY(Q) — Проверить, является ли очередь Q пустой.
Если для реализации очереди используется тип данных «список», то перечисленные операторы можно реализовать следующим образом:
1) Реализация одноименной функцией.
2) INS (x, LAST(Q))
, где LAST(Q) – оператор определения последней позиции списка Q.
3) x:=RET(FIRST(Q),Q);
4) x:=RET(FIRST(Q),Q); DEL(FIRST(Q),Q);
5) if Q^.next=NIL then EMPTY:=true
Else EMPTY:=false;
В отличии от стека реализация очереди в динамической памяти с помощью типа данных «список» не отличается высокой эффективностью. Существует еще один вариант построения очереди в виде однонаправленного списка в динамической памяти. Выделяют 2 специальные ячейки для определения позиций начала и конца очереди.
First – начало очереди. Last – конец очереди.
Тип элемента очереди определяется как указатель на ячейку, состоящий из 2 полей: информационного и указателя на следующий элемент. Очередь определяется как запись, состоящая из 2 ячеек.
type
QUEUE=record;
first, last:^cell;
end;
Для первой ячейки очереди, на которую указывает First, информационное поле никогда не используется. Для последней ячейки, на которую указывает Last поле NEXT всегда определяет пустой указатель.
Покажем примеры реализации операторов:
1) Создать пустую очередь
Procedure MAKENULL ( var Q:QUEUE);
begin
New(Q.first);
Q.first^.next:=NIL;
Q.last:=Q.first;
end;
2)Добавить элемент в конец очереди
Procedure BACK(x:el_type; var Q:QUEUE);
Begin
NEW(Q.Last^.next);
Q.Last:=Q.Last^.next;
Q.Last^.element:=x;
Q.Last^.next:=NIL;
End;
Абстрактные типы данных. Примеры и варианты реализации
Абстрактные типы данных. Список
Абстрактные типы данных. Реализация списка с использованием массива
Абстрактные типы данных. Реализация списка с использованием указателей (в динамической памяти)
Абстрактные типы данных. Стек
Абстрактные типы данных. Реализация очереди с помощью циклического массива