Уроки 74 - 76
Стек, очередь, дек
(§42. Стек, очередь, дек)

Содержание урока

Что такое стек?

Использование динамического массива

Вычисление арифметических выражений

Скобочные выражения

Очереди, деки

Вопросы и задания

Задачи

Использование динамического массива

Поскольку стек — это линейная структура данных с переменным количеством элементов, для создания стека в программе мы можем использовать динамический массив. Конечно, можно организовать стек из обычного (статического) массива, но его будет невозможно расширить сверх размера, выделенного при трансляции.

Для рассмотренной выше задачи 1 структура-стек содержит динамический целочисленный массив и количество используемых в нём элементов:

type TStack = record
data: array of integer;
size: integer; 
end;

Будем считать, что стек «растёт» от начала к концу массива, т. е. вершина стека — это последний элемент.

Для работы со стеком нужны две подпрограммы:

• процедура Push, которая добавляет новый элемент на вершину стека;
• функция Pop, которая возвращает верхний элемент стека и убирает его из стека.

Приведём эти подпрограммы:

procedure Push(var S: TStack; x: integer);
begin
if S.size>High(S.data) then
SetLength(S.data, Length(S.data)+10);
S.data(S.size]:= x;
S.size:=S.size+1;
end;
function Pop(var S:TStack): integer; 
begin
S.size:=S.size-1;
Pop:=S.data[S.size]; 
end;

Обратите внимание, что здесь структура типа TStack изменяется внутри подпрограмм, поэтому этот параметр должен быть изменяемым (описан с помощью var).

Заметим, что если нам понадобится стек, который хранит данные другого типа (например, символы, символьные строки или структуры), в объявлении типа и в приведённых подпрограммах нужно просто заменить integer на нужный тип.

Кроме того, введём процедуру Initstack, которая заполняет поля структуры начальными значениями (выполняет инициализацию стека):

procedure InitStack(var S: TStack); 
begin
SetLength(S.data,0);
S.size:=0;
end;

Теперь несложно написать цикл ввода данных в стек из файла:

Initstack(S);
while not eof(F) do begin
read(F,x);
Push(S, x) ;
end;

Здесь S — переменная типа TStack; F — файловая переменная, связанная с файлом, открытым на чтение; х — целая переменная. Вывод результата в файл выполняется так:

for i:=0 to S.size-1 do begin 
x: = Pop(S); 
writeln(F, x); 
end;

Здесь i — целая переменная, a F — файловая переменная, связанная с файлом, открытым на запись.

Следующая страница Вычисление арифметических выражений

Cкачать материалы урока