If Sempty(Vstek) Then

Begin

End;

Begin

End;

End;

Exit

Begin

Begin

Структура данных стек. Базовые операции над стеком

Организация структур данных

Статическое и динамическое распределение оперативной памяти

Комбинированный урок №18

Тема:Организация памяти. Стековая память. Директива управления памятью ($M).

Цель: изучить принципы организации памяти, сформировать понятие о структуре данных типа «стек», «очередь», «список».

Все команды и данные программы во время ее выполнения размещаются в определенных ячейках оперативной памяти. При этом часть данных размещается в ячейки памяти еще на этапе компиляции и в процессе работы программы их адреса относительно начала программы не изменяются. Такое размещение данных и команд называется статическим и соответствующие этим данным переменные называются статическими переменными.

Возможна также организация динамического размещения данных, при котором под некоторые данные и программы память выделяется непосредственно во время выполнения по мере надобности, а после решения требуемой задачи память освобождается для других данных. Соответствующие таким данным переменные называются динамическими переменными.

Многие процессы, явления, происходящие в природе и обществе, отображаются с помощью алгоритмов. При этом для целых классов задач используются организованные особым образом связные структуры данных.

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

Каждая структура данных характеризуется: взаимосвязью доступных элементов информации и некоторым множеством основных базовых операций над данными.

К типовым связным структурам данных относятся: стек, очередь, список.

При обработке информации часто используется структура данных стек. Стек – это упорядоченный набор связанных элементов, которые добавляются к нему и удаляются (выбираются) из него только с одного конца.

Принцип построения стека – «последний вошел» и «первый вышел» (last in, first out – англ. яз.) или сокращенно LIFO. В каждый конкретный момент времени элементы добавляются и удаляются из одного конца, который называют вершиной стека. Примером стека может служить стопка книг на полке, вагоны, поставленные электровозом, в тупике.

Основные базовые операции при построении стека:

- добавить (разместить) новый элемент в вершину стека;

- выбрать (удалить) элемент из вершины стека.

Структура данных типа «стек» может быть описана с помощью одномерного массива. Память для элементов стека может так же быть выделена динамически.

Например, дан стек из пяти элементов, содержащий строковые данные.

Const maxs=5;

Type Stek=array[1..maxs] of string;

Var Vstek : integer; {вершина стека}

S : Stek; {массив с элементами стека}

Добавление элементов в стек может быть описано с помощью процедуры AddST. В начале стек пуст, значение переменной Vstek равно 0. Затем, по мере добавления элементов в стек, необходимо проверять условие его возможного переполнения. Добавление нового элемента в стек должно сопровождаться размещением нового элемента в массив и увеличением значения переменной Vstek на единицу.

Procedure AddST(Var S:stek; Var Vstek:integer; Var el:string);

if Vstek=maxs then

writeln('Переполнение стека');

Vstek:=Vstek+1; {увеличить индекс вершины стека на единицу}

S[Vstek]:=el {разместить новый элемент в стеке}

При удалении элементов из стека (процедура EdelSt) необходимо проверить, не является ли стек пустым. Эта проверка может выполняться с помощью функции пользователя Sempty.

Function Sempty(Vstek:integer):boolean;

if Vstek=0 then Sempty:=true {стек является пустым}

else Sempty:=false {стек не является пустым}

При удалении элемента из стека значение индекса массива (индекс вершины стека) уменьшается на единицу. Значение удаляемого элемента присваивается переменной el.

Procedure EdelSt (Var S:stek; Var Vstek:integer;Var el:string);