48. Связанные динамические данные: стек.
Определение: Стек - это данные динамической структуры, которые представляют собой совокупность линейно-связанных однородных элементов, для которых разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.
Стек функционирует по принципу LIFO (Last - In - First- Out ) - "последним пришел - первым исключается".
При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.
Стек является одной из наиболее часто употребляемых структур в программировании. Это определяется тем, что при работе со стеком нет необходимости прямо использовать адресацию памяти. Самым важным применением стека в программах является использование стека для хранения адресов возврата в программу из подпрограмм или из процедур обработки прерываний, а также передача через стек параметров в процедуры (функции), размещение в стеке локальных параметров процедур. Стеки используются в работе алгоритмов, имеющих рекурсивный характер.
Так как язык Pascal не имеет непосредственно типа данных стек, то для его моделирования наиболее подходящими структурами являются массивы (статический стек для моделирования структур заданного размера ) и динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.
Условно стек можно представить в виде стакана с шариками.
Описание стека
Type Tptr=^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека }
inf :integer; {информационная часть}
link : Tptr; {соединительная часть}
end;
Работа с динамическим стеком
Для работы со стеком необходимо иметь один основной указатель на вершину стека (возьмём идентификатор Top) и один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.
Создание стека.
Исходное состояние:
Выделение памяти под первый элемент стека и занесение в него информации:
Установка вершины стека Top на созданный элемент:
Добавление элемента стека.
Исходное состояние:
Выделение памяти под новый элемент стека. Внесение значения в информационное поле нового элемента и установка связи между ним и "старой" вершиной стека Top:
Перемещение вершины стека Top на новый элемент:
Удаление элемента стека.
Исходное состояние
Извлечение информации из информационного поля вершины стека Top в переменную Val и установка на вершину стека вспомогательного указателя P:
Перемещение указателя вершины стека Top на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека:
Пример 1. Разместить в стеке 10 символов и распечатать их в обратном порядке.
Hиже приводится пример программы, использующей стек. В ней используются следующие процедуры для работы со стеком:
процедура Push(val:real), которая в зависимости от состояния стека создаёт первый или добавляет очередной элемент в вершину стека (английское название push - заталкивать);
процедура Pop(var val:real), которая извлекает информацию из вершины стека с последующим освобождением её из памяти (английское название pop - выскакивать ).
Program Stack;
Type Tptr = ^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека}
inf : char; {информационная часть}
link : Tptr; {соединительная часть}
end;
Var top : tptr; {Указатели на конец стека}
value : char;
i: byte;
Procedure Push(val : char; var Top:Tptr); {Процедура добавления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
new (p);
p^.inf:=val;
p^.link:=top;
top:=p
End;
Procedure Pop(var val : char; var Top:Tptr); {Процедура удаления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
val:=top^.inf;
p:=top;
top:=p^.link;
dispose (p)
End;
Begin
new(top); { Создание указателя на вершину стека }
top:=nil;
for i:=1 to 10 do
begin
writeln (' введите символ');
readln (value);
push(value,Top); {добавление элемента в стек}
end;
i:=10;
while top<>nil do {пока не будет достигнут конец стека}
begin
pop(value, Top); {извлечение элемента из стека}
writeln (i,'-й символ - ',value);
dec (i)
end
End.
Пример 2. Ввести с клавиатуры 8 чисел и сформировать из них два стека. В первый поместить числа, которые делятся на 2, а во второй -остальные. Распечатать оба стека.
Type Tptr=^TElem; {Тип указателя на элемент стека}
TElem = record {Тип элемента стека }
inf :integer; {информационная часть}
link : Tptr; {соединительная часть}
end;
Var top1,top2 : tptr; {Указатели на конец стеков}
value : integer;
i: byte;
Procedure Push(val : integer; var top:tptr); {Процедура добавления элемента}
Var p :tptr; {Вспомогательный указатель}
Begin
new (p);
p^.inf:=val;
p^.link:=top;
top:=p
End;
Procedure Pop(var val : integer; var top:tptr); {Процедура удаления элемента}
Var p : tptr; {Вспомогательный указатель}
Begin
val:=top^.inf; p:=top;
top:=p^.link; dispose (p)
End;
Begin
new (top1); {Создание указателя на вершину 1-го стека }
new (top2); { Создание указателя на вершину 2-го стека }
top1:=nil; top2:=nil;
for i:=1 to 8 do
begin
writeln (' введите число'); readln (value);
if value mod 2 =0 then
push(value,top1)
else
push(value,top2)
end;
writeln (' 1-й стек - числа делятся на 2 ');
while top1<>nil do
begin
pop(value,top1);
writeln (value);
end;
writeln (' 2-й стек - - числа не делятся на 2');
while top2<>nil do
begin
pop(value,top2);
writeln (value);
end
End.
Задание. Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.
Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:
стек непуст: из стека извлекают один элемент;
стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.
После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.