Пример модуля (стек)

Рассмотрим пример построения модуля, объединяющего в себе средства работы со структурой данных "стек". В общем случае стек (магазин) работает по принципу "первым пришел - последним ушел" (LIFO), причем доступ к элементам стека возможен только через одно место - через т.н. голову стека, которая изменяет свое положение после каждой записи/чтения в/из стек/стека. В зависимости от реализации стек м.б. бесконечным (при реализации в виде динамической связанной структуры, где память выделяется и освобождается динамически - при выполнении программы/модуля) и конечным (при реализации в виде статической структуры - массива, для которой память выделяется только один раз - при компиляции программы).

Чаще всего стек используется в 2 случаях:

1) При интерпретации выражений, где до определенного момента операнды заталкиваются в стек.

2) При работе в таких ситуациях, где надо одновременно держать в памяти несколько поколений какого-то объекта, при этом доступен будет лишь самый «молодой» потомок. Пример – текстовые окна.

Пусть в стек надо записать последовательность символов a,b,c,.......

Обобщенный вид стека при выполнении действий:

Реализация стека в виде динамически связанной структуры:

Голова Голова Голова

После записи a После записи b После записи c

Реализация в виде массива из 3-х элементов:

Исходное состояние После записи a После записи b После записи c После чтения c

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

Замечания:

1) Голова стека будет указывать на ту ячейку, в которую должна выполняться текущая запись.

2) Условимся, что голова стека не может перескакивать за границу массива, т.е. значение головы стека должно быть не больше числа элементов массива.

Итак, модель стека пусть имеет следующий вид:

Необходимые переменные

Const

n=10; {размер стека}

Var

j:byte; {голова стека}

s:array[1..10] of byte; {носитель}

FULL : boolean;{стек полон}

EMPTY: boolean; {стек пуст }

elem : byte; { то, что помещается в стек при Записи }

Исходное состояние (надо уставливать в секции инициализ.):

EMPTY:=true; FULL:=false; j:=1;

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

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

Вопрос: Что будет, если описание переменной elem поместить:

1) В секцию реализации

2) В основную программу

Unit stack;

Interface

Var elem:byte; {то, что считывается и записывается в стек}

Implementation

begin { Инициализация }

end.

Приведем программу, которая использует этот модуль. Она добавляет в стек три числа, потом одно удаляет и выводит на экран:

Program P;

uses

stack;

begin

push(1);

push(2);

push(3);

pop(elem);

writeln('Считанный элемент = ', elem);

end.