Очередь lifo
Наиболее часто в программировании используются очереди второго вида – стеки. Принцип их работы – «Последний пришел – первый вышел».
В стеке доступна единственная позиция, называемая вершиной стека – это позиция, в которой находится последний по времени поступления в стек элемент.
Наиболее быстрое выполнение операций над стеком обеспечивает его представление в виде динамической цепочки звеньев (однонаправленного списка). Вершиной стека обычно является первое звено цепочки. Заглавное звено в цепочке стека не нужно, так как в стеке доступна только его вершина.
При использовании структуры однонаправленного списка стек задается с помощью описания типа, приведенного в примере 7.7, и дополнительно может быть введен тип указателя, представляющего стек как единую структуру, то есть ссылка на вершину стека Stek:
Type
<Задание стека по примеру 7.7>;
Stek = Adres1;
Реальный стек вводится с помощью описания переменной:
Var
St: Stek;
Схематично стек изображается аналогично цепочке (Рисунок 7 .70).
Рисунок 7.70 – Схематичное представление стека
К началу использования стека его нужно сделать пустым:
St := Nil;
А. Занесение элемента в стек
Пусть в программе имеется описание типа, приведенное в примере 7.7.
Алгоритм занесения элемента в стек:
Создание нового звена.
Занесение в новое звено элемента.
Занесение в новое звено адреса предыдущей вершины стека.
Созданное звено сделать вершиной стека.
Пример 7.13.
Процедура занесения элемента в стек. Первый параметр задает нужный стек (если их несколько), второй – заносимое в него значение.
Procedure Zanes (Var St: Stek; El:<Тип_элемента_стека>);
Var
Q: Adres1;
Begin
{1} New (Q);
{2} Q^.Element := El;
{3} Q^.Adrcled := St;
{4} St := Q
End;
Номера операторов в данной программе соответствуют номерам этапов алгоритма занесения элемента в стек.
Б. Выбор элемента из стека
Пусть в программе имеется описание типа, приведенное в примере 7.7.
Алгоритм выбора элемента из стека:
Прочитать значение из вершины стека.
Запомнить ссылку на старую вершину.
Исключить первое звено из стека.
Уничтожить первое звено.
Пример 7.14.
Процедура выбора элемента из стека. Первый параметр задает нужный стек (если их несколько), во второй передается значение из вершины стека.
Procedure Vibor (Var St: Stek; Var A: <Тип_элементов_стека>);
Var
Q: Adres1;
Begin
{1} A := St^.Element;
{2} Q := St;
{3} St := St^.Adrcled;
{4} Dispose (Q)
End;
Номера операторов в данной программе соответствуют номерам этапов алгоритма выбора элемента из стека.
Если необходимо ускорить процедуру выбора, то операторы Q := St и Dispose(Q) можно не применять. Однако это приведет к неэффективному использованию памяти.
В. Создание стека
Пусть в программе имеется описание типа, приведенное в примере 7.7.
Для создания стека может быть использована процедура Zanes из примера 7.13.
Пример 7.15.
Создание стека. Ввод исходного текста в стек. Признак окончания текста – точка.
…
Var
St: Adres1;
Bykva: Char;
Begin
St := Nil;
Read (Bykva);
While Bykva <>’.’ Do
Begin
Zanes (St, Bykva);
Read (Bykva)
End
End.