Стек. Отличия стека от списка. Основные операции со стеком
Сейчас Вы познакомитесь с одной из разновидностей обычного линейного списка – стеком. Этот вид списка очень часто используется в программировании.
Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека.
Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.
Изобразим стек графически:
При программировании на Паскале стек чаще всего реализуется в виде однонаправленного списка. Каждый элемент структуры содержит указатель на следующий. Однако, к этому виду списка, по определению, неприменима операция обхода элементов. Доступ возможен только к верхнему элементу структуры.
Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.
Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.
Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.
Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.
Таким образом, описать стек можно следующим образом:
Type
EXST = ^ST;
ST = record
Data : integer;
Next : EXST;
end;
Var
Stack : EXST; {Текущая переменная} |
Если стек пуст, то значение указателя равно Nil.
Рассмотрим возможные операции со стеком.
Занесение элемента в стек
Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.
Процедура формирования стека будет иметь следующий вид:
Procedure FormStack;
Var
Stack : EXST; {Текущая переменная}
Digit : integer;
Procedure writeStack(Var u : EXST; Digit : integer);
Var
x : EXST;
Begin
new(x); {выделяем память под хранение нового элемента стека}
x^.Data := Digit; {заполняем поле данных элемента}
x^.Next := u; {новый элемент "связываем" со стеком}
u := x; {созданный элемент определяем как вершину стека}
End;
Begin
Stack := Nil; {инициализация стека}
writeln('Введите элементы стека. Окончание ввода – 0');
read(Digit);
while Digit <> 0 do
begin
writeStack(Stack, Digit);
read(Digit);
end;
End; |
Извлечение элемента из стека
В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека, и значение указателя на начало списка должно быть перенесено на следующий элемент стека.
Procedure readStack(Var u : EXST; Var i : integer);
Var
x : EXST;
Begin
i := u^.Data; {считываем значение поля данных в переменную}
x := u; {запоминаем адрес вершины стека}
u := u^.Next; {переносим вершину стека на следующий элемент}
dispose(x); {освобождаем память, занятую уже ненужным элементом стека}
End. |
Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.
Function FreeStack(u : EXST) : boolean; |
Задание. Описать функцию и закончить программу, для чего описать процедуру вывода значений элементов стека на экран (она аналогична выводу списка). Протестировать программу, дополнить комментарием.
Примеры решения задач
Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.
Program MordovskihK;
Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
End;
Var
Stack : EXST; {Текущая переменная}
i : integer;
f : text;
Stroka : string;
c : char;
Procedure writeStack(Var u : EXST; Simvol : char);
Var
x : EXST;
Begin
new(x);
x^.Data := Simvol;
x^.Next := u;
u := x;
End;
Procedure Print(Var u : EXST);
Begin
while u <> Nil do
Begin
write (u^.Data);
u := u^.Next;
End;
End;
Begin
Stack := Nil;
Assign(f, 'c:\autoexec.bat');
Reset(f);
while Not Eof(f) do
Begin
readln (f, Stroka);
For i := 1 to Length(Stroka) do
writeStack(Stack, Stroka[i]);
Print(Stack);
writeln;
End;
close(f);
End. |
Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов.
Для решения задачи определим стек, элементами которого являются символы:
Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
End; |
Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из открывающих скобок ({, (, [ ), занесем ее в стек. При обнаружении закрывающей скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.
Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:
while (i<>Length(a)) and f do ... |
Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):
{ } 123–125
[ ] 91–93
( ) 40–41, |
причем код открывающей скобки меньше. Таким образом, можно записать следующее условие соответствия:
if (Ord(a[i])–Ord(stack^.Data))<=2
then
. . . |
А теперь просмотрите полный текст программы:
Program Skobki;
Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
end;
Var
a : string;
f : boolean;
i : integer;
Procedure writeStack(Var x1 : EXST; c : char);
Var
u : EXST;
Begin
new(u); {создание нового элемента стека}
u^.Data := c;
u^.Next := x1;
x1 := u; {созданный элемент определить как вершину стека}
End;
Procedure DelStack(Var x1 : EXST); {процедура удаления верхнего элемента стека}
Var
u : EXST;
Begin
u := x1;
x1 := x1^.Next;
dispose(u);
End;
Procedure Solve(a : string); {проверка правильности расстановки скобок}
Var
Stack : EXST;
Begin
Stack := Nil;
i := 1;
while (i<=Length(a)) and f do
begin
if (a[i]='(') or (a[i]='{') or (a[i]='[')
then
writeStack(Stack , a[i])
else
if (a[i]=')') or (a[i]='}') or (a[i]=']')
then
if (Stack <> Nil) And (Ord(a[i]) - Ord(Stack ^.Data) <= 2)
then
DelStack(Stack)
else
f := False;
Inc(i);
end;
end;
Begin
writeln('Введите строку');
readln(a);
f := True;
if a<>''
then
begin
Solve(a);
if f
then
writeln('Все скобки расставлены верно')
else
writeln('Скобка ',a[i-1],' закрыта преждевременно');
end
else
writeln('Строка пуста');
readln;
End. |
|