Стеки, очереди

Стек - это линейный список с определенной дисциплиной обслуживания, которая заключается в том, что элементы списка всегда включаются, выбираются и удаляются с одного конца, называемого вершиной стека. Доступ к элементам здесь происходит по принципу “ последним пришел - первым ушел”(LIFO - last in first out), т. е. последний включенный в стек элемент первым из него удаляется. Стеки моделируются на основе линейного списка. Включение элемента вершины стека называется операцией проталкивания в стек, а удаление элемента из вершины стека называется операцией выталкивания из стека.

Для работы со стеками необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека.

Создание стека:

Исходное состояние

Тon: = nil

2. Выделение памяти под первый элемент стека и внесение в него информации

New (P)

P^. Inf: = S

P^. Link: = nil

Установка вершины стека Тор на созданый элемент

Тор: = Р

Добавление элемента стека:

1. Выделение памяти под новый элемент

New (P)

2. Внесение значения в информационное поле нового элемента и установка связи между ним и старой вершиной стека Тор

P^. Inf: = Val (Val=10)

P^. Link: = Top.

Помещение вершины стека Тор на новый элемент

Тор: = Р

Удаление элемента стека

Извлечение информации из информационного поля вершины стека Тор в переменную Val и установка на вершину стека вспомогательного указателя Р.

Val: = Top^. Inf;

P: = Top;

Перемещение указателя вершины стека Тор на следующий элемент и освобождение памяти, занимаемой «старой» вершиной стека

Тор: - Р^. Lin K;

Pispose (P)

В качестве примера приведем программу создания и удаления стека из десяти элементов:

Pvogram Stack;

Uses Crt

Tupe

TP tr = ^Telem;

Telem = record

Inf: Real;

Link: TPtr

End;

Var

Top: TPfr;

Value: Real;

Value: Byte;

Procedure Push (Val: Real)

Var

P: TPfr;

Begin

New (P);

P^.Inf: = Val;

P^.Link: = Top

Top: = P

End;

Procedure Top (Var Val:Real);

Var

P: TPtr;

Begin

Val: = Top^. Inf;

P: = Top;

Top: = P^. Link;

Pispose (P)

End;

Begin

ClrSer;

{начальные установки указателей}

Тор: = nil

{создание стека из десяти элементов}

for i: = 1 to 10 do Push (i);

{удаление стека с распечаткой значений его элементов}

whise Top <> nil do

begin

Pop (Value);

Writeln (‘Value= ‘, Value = 5:2)

End;

End.

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

Очередь – это частный случай линейного односвязующего списка для которого разрешены только два действия: добавление элемента в конец очереди и удаление элемента из начала очереди.

Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

на начало очереди (возьмем идентификатор Beg Q)

на конец очереди (возьмем идентификатор End Q)

Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (Р).

Создание очереди:

Исходное состояние:

Beg Q: = nil

Eng Q: = nil

Выделение памяти под первый элемент

New (P)

Занесение информации в первый элемент очереди

Beg Q: = P

Eng Q: = P

Добавление элемента очереди

Выделение памяти под новый элемент и занесение в него информации:

New (P)

P^, Inf: = 5

P^, Link: = hil

Установка связи между последним элементом очереди и новым, а также перемещение указателя конца очереди End Q на новый элемент

End^. Link: = P

End Q: = P

Удаление элемента очереди

Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя Р

Val: = Beg Q^. Inf

P: = Beg Q

Перестановка указателя начала очередт Beg Q на следующий элемент используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:

Beg Q: = P^. Link

Dispose (P)

В качестве примера приведем программу создания и удаления очереди из десяти элементов:

Prodrsm Queue;

Uses Crt;

Type

TPtr = ^Telem;

TFlem = record

Inf: Real;

Link: Tptr

End;

Var

Beg Q, End Q: TP tr;

Value: Real;

i: Byte;

Procedure AddEl (Val:Real)

{создает первый и дабавляет очередной элемент в конец очереди}

Var

P: TPtr

Begin

New (P);

P^. Inf: = Val;

P^. Link: = nil;

If End Q = n:l; {если создается первый элемент очереди}

Then Beg Q: = P {если создается очередной элемент очереди}

Else Eng Q^. Link: = P;

End Q: = P;

End;

Procedure bet Del E₁ (vav Val: Real)

{извлечение информации из начального элемента очереди с последующим освобождением его памяти}

Var

P: TPtr;

Begin

Val: = Reg Q^. Inf;

P: = Beg Q;

Beg Q: = P^. Link

If Beg Q = nil {если удаляется последний элемент очереди}

Then Eng Q: = nil;

Dispose (P);

End;

Begin

ClrScr;

{начальные установки указателей}

Beg Q: = nil;

Eng Q: = nil;

{создание очереди из 10 элементов}

for I: = 1 to 10 to Add E1 (i)

{удаление очереди с распечаткой значений её элементов}

while. Beg Q <> nil do

begin

Get Del E1 (Value);

Writeln (‘Value=’, Value: 5: 2)

End;

End.