Создание стека

Стек

Описание односвязной ДСД

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

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

Соответствующее ей объявления будут иметь такой вид:

tуре <имя_типа>=^ <имя_элемента>;

<имя_элемента>=record

<имя_информационной части>: <тип информац. части>;

<имя_указатель>: <имя_типа>

end;

Тип информационной части может быть любым простым типом, массивом, множеством или записью.

Пример: Динамическая структура, содержащая вещественные числа, описывается так:

type ukaz=^element;

element = record

inf: real;

next: ukaz

end;

var sp: ukaz;

Начнем рассмотрение основных принципов построения и работы с ДСД с частных случаев линейного односвязного списка.

Образно стек представляет собой “трубу” с одним запаянным концом, куда помещаются “бочонки” – элементы.

Правило стека:

«первым пришел – последним вышел»

или

«последний пришел – первым уйдешь».

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

Над стеком можно реализовывать следующие операции:

1) создание (инициализация) стека;

2) добавление элемента в стек;

3) удаление элемента из стека;

4) уничтожение стека.

Рассмотрим общую схему формирования стека.

Для создания стека и работы с ним необходимо иметь один основной указатель на вершину стека (возьмем идентификатор Beg).

Для удобства работы часто используют временный (рабочий) указатель (возьмем р).

1. Исходное состояние:

Beg:=nil;

2. Выделение памяти под 1-й элемент стека и занесение информации в первый элемент стека:

new(p);

p^.inf:=5;

p^.uk:=nil;

3. Установка вершины стека Веg на созданный элемент:

Веg:=p;