Абстрактный тип данных «очередь»
Очередь – это специальный тип списка. Очередью называют структуру, из которой элементы удаляются с одного ее конца, называемого началом (головой), а вставляются на противоположном конце, называемом (хвостом).
Очереди считаются списками типа FIFO (аббревиатура расшифровывается как first in first out: первым вошел – первым вышел). Две основные операции, которые определены для работы с очередью: вставка и извлечение элементов. Кроме того, используются и другие операторы.
1) MAKENULL(Q) очищает очередь Q, делая ее пустой.
2) FRONT(Q) – функция, возвращающая первый элемент очереди Q.
3) ENQUEUE(x, Q) вставляет элемент х в конец очереди Q.
4) DEQUEUE (Q) удаляет первый элемент очереди Q.
5) EMPTY (Q). Эта функция возвращает значение true (истина) тогда и только тогда, когда Q является пустой очередью.
Рассмотрим способ реализации очереди на базе списков, учитывая ее структурные и функциональные особенности. Например, при добавлении элемента в конец очереди вместо перемещения по списку от начала к концу можно хранить указатель на конец очереди. Указатель на начало очереди будет полезен при выполнении операторов, связанных с извлечением элементов из структуры. В языке Delphi в качестве заголовка можно использовать динамическую переменную и поместить в нее указатель на начало очереди, что позволит удобно организовать очищение очереди.
Определим список, содержащий указатели на начало и конец очереди. Первая ячейка очереди – это заголовок, в котором отсутствуют данные. Ниже определен абстрактный тип данных «очередь».
Type ptr = ^queue;{Указатель на элемент очереди}
Queue = record
data : integer; {Поле данных}
next, front, rear : ptr;{Указатели на следующий элемент, голову и
End; хвост очереди}
Var Q : ptr; {Указатель на заголовок очереди}
Рассмотрим программную реализацию некоторых из вышеперечисленных операторов над очередями.
1) Procedure Makenull (var q:ptr);
begin
new(q); {Создание ячейки заголовка}
q^. front:=q;
q^. front^.next:=nil;
q^. rear:=q^.front;
end;
|
2) Function empty(q:ptr):boolean;
var z:boolean;
begin
if
q^.front= q^.rear then {Проверка пустоты очереди}
z:=true
else z:=false;
end;
3)Procedure make (var q:ptr);
Var i: integer;
begin
for i:=1 to 2 do {Добавление в очередь двух элементов }
begin
new( q^.rear^.next);
q^.rear:= q^.rear^.next;
readln(q^.rear^.data);
end;
q^.rear^.next:=nil;
end;
|
4) Procedure print(var q:ptr); {Вывод на печать элементов очереди}
begin
writeln('Вывод элементов очереди');
q^.front:= q^.front^.next;
while q^.front<> nil do
begin
writeln (q^.front^.data);
q^.front:= q^.front^.next;
end;
end;
5) Procedure dequeue (var q:ptr); {Удаление первого элемента очереди}
begin
if empty (q) then
writeln('Очередь пуста')
else
q^.front:=q^.front^.next;
end;
|
