Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
LIFO = Last In – First Out
«Кто последним вошел, тот первым вышел».
Структура
const MAXSIZE = 100;
type Stack = record { стек на 100 символов }
data: array[1..MAXSIZE] of char;
size: integer; { число элементов }
end;
Добавление
procedure Push( var S: Stack; x: char);
begin
if S.size = MAXSIZE then Exit;
S.size := S.size + 1;
S.data[S.size] := x;
end;
Снятие
function Pop ( var S:Stack ): char;
begin
if S.size = 0 then begin
Result := char(255);
Exit;
end;
Result := S.data[S.size];
S.size := S.size - 1;
end;
Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
[()]{} ][ [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.
Алгоритм:
1)в начале стек пуст;
2)в цикле просматриваем все символы строки по порядку;
3)если очередной символ – открывающая скобка, заносим ее на вершину стека;
4)если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);
5)если в конце стек не пуст, выражение неправильное.
var br1, br2, expr: string;
i, k: integer;
upper: char; { то, что сняли со стека }
error: Boolean; {признак ошибки }
S: Stack;
begin
br1 := '([{'; br2 := ')]}';
S.size := 0;
error := False;
writeln('Введите выражение со скобками');
readln(expr);
{основной цикл обработки }
for i:=1 to length(expr)
do begin
for k:=1 to 3 do begin
if expr[i] = br1[k] then begin {откр. скобка }
Push(S, expr[i]);{втолкнуть в стек}
break;
end;
if expr[i] = br2[k] then begin { закр. скобка }
upper := Pop(S); {снять символ со стека }
error := upper <> br1[k];
break;
end;
end;
if error then break;
end;
if not error and isEmpty(S) then
writeln('Выражение правильное.')
else writeln('Выражение неправильное.')
end.
Системный стек windows
Используется для
1)размещения локальных переменных;
2)хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры);
3)передачи параметров в функции и процедуры;
4)временного хранения данных (в программах на языке Ассмеблер).
Переполнение стека (stack overflow):
1)слишком много локальных переменных
(выход – использовать динамические массивы);
2)очень много рекурсивных вызовов функций и процедур
(выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).
21.