Реферат: Динамические структуры данных: очереди

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).

Очередь разумнее всего моделировать, отобразив её на двунаправленный кольцевой список. В этом случае в заглавном звене будет присутствовать информация как об указателе на голову, так и на хвост очереди.

Выделим типовые операции над очередями:

добавление элемента в очередь (помещение в хвост);

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

проверка, пуста ли очередь;

очистка очереди.

Вот модуль, содержание которого составляют реализованные типовые операции над очередями.

{Язык Pascal}

Unit Spisok2;

Interface

Type BT = LongInt;

U = ^Zveno;

Zveno = Record Inf : BT; N, P: U End;

Procedure V_Och(Var First : U; X : BT);

Procedure Iz_Och(Var First : U; Var X : BT);

Procedure Ochistka(Var First: U);

Function Pust(First : U) : Boolean;

Implementation

Procedure V_Och;

Var Vsp : U;

Begin

New(Vsp);

Vsp^.Inf := X;

If First = Nil then begin Vsp^.N := Vsp; Vsp^.P := Vsp; First := Vsp end

else begin Vsp^.N := First; Vsp^.P := First^.P; First^.P^.N := Vsp; First^.P := Vsp; end;

End;

Procedure Iz_Och;

Var Vsp : U;

--> ЧИТАТЬ ПОЛНОСТЬЮ <--