Стеки
38. С Т Е К И
Стеком называется динамическая структура данных, добавление компо-
ненты в которую и исключение компоненты из которой производится из
одного конца, называемого вершиной стека. Стек работает по принципу
LIFO (Last-In, First-Out) -
поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
-начальное формирование стека (запись первой компоненты);
Рекомендуемые материалы
-добавление компоненты в стек;
-выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две пере-
менные типа указатель, первая из которых определяет вершину стека, а
вторая - вспомогательная. Пусть описание этих переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
г=====¬ г=====¬
New(pTop); ¦ *--¦---¬ ¦ ¦
L=====- ¦ ¦=====¦
pTop L-->¦ ¦
L=====-
г=====¬ г=====¬
pTop^.pNext:=NIL; ¦ *--¦---¬ ¦ ¦
L=====- ¦ ¦=====¦
pTop L-->¦ NIL ¦
L=====-
г=====¬ г=====¬
pTop^.D:=D1; ¦ *--¦---¬ ¦ D1 ¦
L=====- ¦ ¦=====¦
pTop L-->¦ NIL ¦
L=====-
Последний оператор или группа операторов записывает содержимое
поля данных первой компоненты.
Добавление компоненты в стек призводится с использованием вспо-
могательного указателя:
г=====¬ г=====¬ г=====¬
New(pAux); ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
L=====- ¦ ¦=====¦ ¦ L=====-
pTop ¦ ¦ ¦<--- pAux
¦ L=====-
¦
¦ г=====¬
¦ ¦ D1 ¦
¦ ¦=====¦
L-->¦ NIL ¦
L=====-
г=====¬ г=====¬ г=====¬
pAux^.pNext:=pTop; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
L=====- ¦ ¦=====¦<--- L=====-
pTop ¦ ¦ *--¦-¬ pAux
¦ L=====- ¦
¦ ¦
¦ г=====¬ ¦
¦ ¦ D1 ¦ ¦
¦ ¦=====¦ ¦
L-->¦ NIL ¦<-
L=====-
г=====¬ г=====¬ г=====¬
pTop:=pAux; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
L=====- ¦ ¦=====¦<--- L=====-
pTop L-->¦ *--¦-¬ pAux
L=====- ¦
¦
г=====¬ ¦
¦ D1 ¦ ¦
¦=====¦ ¦
¦ NIL ¦<-
L=====-
г=====¬ г=====¬
pTop^.D:=D2; ¦ *--¦---¬ ¦ D2 ¦
L=====- ¦ ¦=====¦
pTop L-->¦ *--¦-¬
L=====- ¦
¦
г=====¬ ¦
¦ D1 ¦ ¦
¦=====¦ ¦
¦ NIL ¦<-
L=====-
Добавление последующих компонент производится аналогично.
Рассмотрим процесс выборки компонент из стека. Пусть к моменту на-
чала выборки стек содержит три компоненты:
г=====¬ г=====¬
¦ *--¦---¬ ¦ D3 ¦
L=====- ¦ ¦=====¦
pTop L-->¦ *--¦-¬
L=====- ¦
¦
г=====¬ ¦
¦ D2 ¦ ¦
¦=====¦ ¦
--¦--* ¦<-
¦ L=====-
¦
¦ г=====¬
¦ ¦ D1 ¦
¦ ¦=====¦
L>¦ NIL ¦
L=====-
Первый оператор или группа операторов осуществляет чтение данных
из компоненты - вершины стека. Второй оператор изменяет значение ука-
зателя вершины стека:
г=====¬ г=====¬
D3:=pTop^.D; ¦ *--¦---¬ ¦ D3 ¦
pTop:=pTop^.pNext; L=====- ¦ ¦=====¦
pTop ¦ ¦ ¦
¦ L=====-
¦
¦ г=====¬
¦ ¦ D2 ¦
¦ ¦=====¦
L-->¦ *--¦-¬
L=====- ¦
¦
г=====¬ ¦
¦ D1 ¦ ¦
¦=====¦ ¦
¦ NIL ¦<-
L=====-
Как видно из рисунка, при чтении компонента удаляется из стека.
Пример. Составить программу, которая формирует стек, добавляет в
него произвольное количество компонент, а затем читает все компоненты
и выводит их на экран дисплея, В качестве данных взять строку симво-
лов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка
символов END.
Program STACK;
uses Crt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= Record
sD: Alfa;
pNext: PComp
end;
var
pTop: PComp;
sC: Alfa;
Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC
end;
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
end;
Procedure DelComp(var pTop: PComp; var sC:ALFA);
begin
sC:=pTop^.sD;
pTop:=pTop^.pNext
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateStack(pTop,sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddComp(pTop,sC)
until sC='END';
writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');
Бесплатная лекция: "23. Бюджет информационного агентства" также доступна.
repeat
DelComp(pTop,sC);
writeln(sC);
until pTop = NIL
end.
