Динамическая реализация стека

В отличие от статической реализации на основе массива, при использовании механизма динамического выделения памяти в стек можно занести любое число элементов. Ограничением является только размер области памяти, выделяемой для размещения динамически создаваемых переменных. При динамической реализации элементы стека могут располагаться в ЛЮБЫХ свободных областях памяти, но при этом необходимо как-то связывать соседние элементы друг с другом. Это приводит к необходимости добавления в каждый элемент стека нового связующего поля для хранения адреса соседнего элемента. Тем самым, каждый элемент стека должен представлять собой запись, состоящую из двух компонент:

• · информационная составляющая с полезной смысловой информацией
• · связующая составляющая для хранения адреса соседнего элемента

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

В этом случае физическое размещение элементов в памяти НЕ обязано всегда соответствовать логическому порядку следования элементов. Логический порядок элементов определяется адресными частями при проходе от последнего элемента к первому. Структура оперативной памяти в этом случае может выглядеть следующим образом:

Для построения логического порядка следования элементов достаточно знать вершинный элемент, все остальное восстанавливается по адресным частям элементов независимо от их реального размещения в памяти.

Для программной реализации элемент стека надо объявить, как запись, содержащую по крайней мере два поля — информационное и связующее. Для простоты будем считать, что информационное поле каждого элемента содержит только одно целое число.

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

Что должны адресовать эти переменные? Элементы стека, т. е. записи определенного типа. Следовательно, прежде всего надо ввести ссылочный тип, связанный с базовым типом-записью, а затем — описать базовый тип как запись с необходимыми полями, одно из которых должно быть ссылочного типа:

type pStackItem = ^ TStackItem;

{ссылочный тип для адресации элементов стека}.

TStackItem = record

{базовый тип, определяющий структуру элементов стека}.

inf: integer; {информационная часть}.

next: pStackItem;

{ссылочная часть: поле для адреса следующего элемента}.

end;

Какие ссылочные переменные необходимы для поддержки работы стека? Во-первых, всегда необходимо знать адрес элемента, находящегося на вершине стека, т. е. помещенного в стек самым последним:

var sp: pStackItem;

Тогда конструкция sp^.inf будет представлять саму информационную часть, а конструкция sp^.next — адрес предыдущего элемента, который был помещен в стек непосредственно перед текущим.

Кроме того, для прохода по стеку от вершинного элемента к самому первому элементу необходима вспомогательная ссылочная переменная (например — с именем pCurrent). Она на каждом шаге прохода по стеку должна определять адрес текущего элемента. В самом начале прохода надо установить значение pCurrent = sp, а затем циклически менять его на значение pCurrent^.next до тех пор, пока не будет достигнут первый элемент стека. Очевидно, что для прохода надо использовать цикл с неизвестным числом повторений, а признаком его завершения должно быть получение в поле pCurrent^.next пустой ссылки nil. Отсюда следует, что ссылочное поле самого первого элемента стека должно содержать значение nil.

Тогда схематично проход по стеку можно представить следующим образом:

pCurrent: = sp; {начинаем проход с вершины стека}.

While pCurrent nil do.

begin.

Writeln (pCurrent^. Inf); {вывод инф. части текущего элемента}.

pCurrent: = pCurrent^.next; {переход к следующему элементу}.

end;

Как выполняется добавление нового элемента в вершину стека?

Необходимые шаги:

• · выделить память для размещения нового элемента с помощью вспомогательной ссылочной переменной pTemp и стандартной программы new(pTemp); адрес этой области памяти сохраняется как значение переменной pTemp
• · заполнить информационную часть нового элемента (например: ReadLn(pTemp^.inf))
• · установить адресную часть нового элемента таким образом, чтобы она определяла адрес бывшего вершинного элемента: pTemp^.next: = sp;
• · изменить адрес вершины стека так, чтобы он определял в качестве вершины новый элемент: sp: = pTemp;

В этой последовательности шагов важен их порядок. Перестановка шагов 3 и 4 приведет к неправильной работе алгоритма вставки, т.к. на шаге 4 происходит изменение указателя sp, который перед этим на шаге 3 используется для установки правильного адреса в ссылочной части нового элемента.

Как выполняется удаление элемента с вершины стека?

Необходимые шаги:

· с помощью вспомогательной переменной рTemp адресуем удаляемый элемент:

рTemp:= sp;

· изменяем значение переменной sp на адрес новой вершины стека:

sp: = sp^.next;

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

Сравнение статической и динамической реализации стека: при статической реализации расходуется меньше памяти, но требуется знание максимального числа элементов в стеке-массиве; динамическая реализация более гибкая, но каждый элемент стека дополнительно расходует память на ссылочную часть (чаще всего — 4 байта), что при большом числе элементов может стать весьма ощутимым.