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

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

· информационная составляющая с полезной смысловой информацией

· связующая составляющая для хранения адреса соседнего элемента

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

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

элем. N-3	элем. N-1		элем. N			элем. N-2	элем. N-4
адрес N-4	адрес N-2		адрес N-1			адрес N-3	адрес N-5

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

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

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

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

type pStackItem = ^ TStackItem;

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

TStackItem = record

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

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

next : pStackItem;

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

end;

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

varsp : pStackItem;

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

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

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

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

WhilepCurrent <> 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 используется для установки правильного адреса в ссылочной части нового элемента.

	эл-т 1 nil		эл-т 2 next		эл-т 3 next		новый эл-т pTemp^.next : = sp

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

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

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

рTemp:= sp;

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

sp : = sp^.next;

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

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