26. Атд очередь
Очередь (Queue)– еще один вид линейного списка. Способ доступа к элементам очереди ограничен двумя концами списка, при этом все операции вставки выполняются в конце списка, а все операции удаления – в начале. Структура обслуживается по принципу FIFO (First-In – First-Out – первый пришел – первый ушел). АТД очередь характеризуется следующими основными операциями:
-
Вставка элемента в конец очереди.
-
Удаление элемента из начала очереди.
Рассмотрим реализацию АТД очередь на связных списках. Очередь характеризуется парой указателей: head – указателем на начало очереди, и tail – указателем на конец очереди.
Type List=^node;
Node=record
Elem: integer;
Next: list;
End;
Queue=record
Head, tail: list;
End;
Пустая очередь, то есть состояние, когда между началом и концом очереди нет элементов, соответствует совпадению этой пары указателей. При этом в пустой очереди мы предусмотрим фиктивный ведущий узел, который позволит эффективно реализовать операцию вставки первого элемента.
Procedure QueueInit (var Q: queue);
Begin
New(Q.head);
Q.head^.next:=nil;
Q.tail:=Q.head;
End;
Function QueueEmpty(Q: queue): Boolean;
Begin
QueueEmpty:=Q.head=Q.tail;
End;
При изменении содержания очереди за счет вставки или удаления элементов меняется ее состояние и соответственно, значения указателей tail и head. При вставке элемента создается новый узел и связывается с последним существующим узлом, адрес которого определяет значение указателя tail. После этого указатель tail меняет значение на адрес нового узла. Удаление происходит из узла, следующего за фиктивным, после чего он сам становится фиктивным. Заметим, что удаляемый элемент остается в узле, но перестает быть частью очереди:
Procedure Insert (x: integer; var Q: queue);
Var P: list;
Begin
New(P);
P^.elem:=x;
P^.next:=nil;
Q.tail^.next|:=P;
Q.tail:=P;
End;
Procedure remove (var x: integer; var Q: queue);
Var P: list;
Begin
P:=Q.head;
Q.head:=Q.head^.next;
X:=Q.head^.elem;
Dispose(P);
End;
В случае, когда максимальный размер очереди известен, АТД очередь может быть реализован на массиве, длина которого a priori определяет максимальный размер очереди. В приведенной реализации очередь состоит из массива elem и указателей head, tail, которые интерпретируются как индексы массива. В начальном состоянии очередь пуста и оба указателя имеют нулевое значение:
Const MaxQueueSize= ; {максимальный размер очереди}
Type Queue=record
Elem: array[0..MaxQueueSize-1-1] of integer;
Head,tail: 0..MaxQueueSize;
End;
Procedure QueueInit (var Q: queue);
Begin
Q.head:=0; Q.tail:=0;
End;
Function QueueEmpty(Q: queue): Boolean;
Begin
Queyeempty:=(Q.head=Q.tail);
End;
Procedure Insert (x: integer; var Q: queue);
Begin
Q.elem[Q.tail]:=x;
Q.tail:=(Q.tail+1) mod MaxQueueSize;
End;
Procedure Remove (var x: integer; var Q:Queue);
Begin
X:=Q.elem[Q.head];
Q.head:=(Q.head+1) mod MaxQueueSize;
End;
Очереди находят широкое применение в программировании, в частности, в таких приложениях, как последовательность обработки задач в операционных системах, буферизация задач принтера в системе входных и выходных потоков, организация буфера ввода с клавиатуры, моделирование процессов обслуживания клиентов и т.д.