Для создания новой пустой или очистки существующей очереди достаточно присвоить указателям на первый и последний элементы значение nil.
procedure CreateQueue (var FirstElem, LastElem: Queue);
begin
FirstElem:= nil;
LastElem:= nil
end;
Проверка очереди на пустоту
Условием пустоты очереди является значения указателей на первый и последний элементы, равные nil.
function QueueIsClear(var FirstElem, LastElem: Queue): Boolean;
begin
QueueIsClear:= (FirstElem= nil) and (LastElem= nil)
end;
Включение элемента в очередь
Для включения элемента в очередь, необходимо создать новый элемент типа очередь, затем инициализировать его информационное поле. В заключение изменить его указатель и указатель на последний элемент очереди так, чтобы последним стал новый элемент.
procedure IncludeInQueue(var FirstElem, LastElem: Queue; NewElem: TypeOfElem);
var
ServiceVar: Queue;
begin
{создание нового элемента}
new(ServiceVar);
ServiceVar^.Elem:= NewElem;
ServiceVar^.NextElem:= nil;
if (FirstElem= nil) and (LastElem= nil) then begin
{создать очередь из одного элемента}
FirstElem:= ServiceVar;
LastElem:= ServiceVar
end
else begin
{созданный элемент поместить в конец очереди}
LastElem^.NextElem:= ServiceVar;
LastElem:= ServiceVar
end
end;
Выбор элемента из очереди
При выборе элемента из очереди информационное поле первого ее элемента должно быть присвоено результирующей переменной, а сам элемент должен быть исключен из очереди и удален. Здесь необходима также проверка на то, являлся ли этот элемент в очереди единственным, и если да, то необходимо соответствующим образом изменить указатель на последний элемент.
procedure SelectFromQueue(var FirstElem, LastElem: Queue; var Result: TypeOfElem);
var
ServiceVar: Queue;
begin
if not ((FirstElem= nil) and (LastElem= nil)) then begin
Result:= FirstElem^.Elem;
ServiceVar:= FirstElem;
{убираем 1-ый элемент из очереди}
FirstElem:= FirstElem^.NextElem;
{был ли это последний элемент}
if FirstElem= nil then
LastElem:= nil;
dispose(ServiceVar)
end
end;
Стек на базе списка
Из механизма LIFO следует, что в стеке доступен только последний занесенный его элемент – так называемая вершина стека. Главный элемент, представляющий весь список как единый объект, в случае стека оказывается лишним, его роль выполняет вершина стека. Элемент, занесенный в стек раньше других имеет ссылку nil.
Стек
 |
Рис. 8. Организация стека на основе линейного списка [3].
Структура данных, представляющая стек, могла бы выглядеть следующим образом:
type
TypeOfElem= {};
Assoc= ^ElementOfStack;
ElementOfStack= record
Elem: TypeOfElem;
NextElem: Pointer
end;
Stack= Assoc;
Рассмотрим реализацию основных операций над стеком.
Создание (очистка) стека
Для создания нового пустого или очистки существующего стека достаточно присвоить указателю на первый его элемент (вершину) значение nil.
procedure CreateStack (var StackHead: Stack);
begin
StackHead:= nil
end;