В отличие от статической реализации на основе массива, при использовании механизма динамического выделения памяти в стек можно занести любое число элементов. Ограничением является только размер области памяти, выделяемой для размещения динамически создаваемых переменных. При динамической реализации элементы стека могут располагаться в ЛЮБЫХ свободных областях памяти, но при этом необходимо как-то связывать соседние элементы друг с другом. Это приводит к необходимости добавления в каждый элемент стека нового связующего поля для хранения адреса соседнего элемента. Тем самым, каждый элемент стека должен представлять собой запись, состоящую из двух компонент:
- информационная составляющая с полезной смысловой информацией
- связующая составляющая для хранения адреса соседнего элемента
Учитывая специфику стека, указатели должны следовать от последнего элемента (вершина стека) к первому (дно стека).
В этом случае физическое размещение элементов в памяти НЕ обязано всегда соответствовать логическому порядку следования элементов. Логический порядок элементов определяется адресными частями при проходе от последнего элемента к первому. Структура оперативной памяти в этом случае может выглядеть следующим образом:
| элем. 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 |
Как выполняется удаление элемента с вершины стека?
Необходимые шаги:
- с помощью вспомогательной переменной рTemp адресуем удаляемый элемент:
рTemp:= sp;
- изменяем значение переменной sp на адрес новой вершины стека:
sp : = sp^.next;
- каким-то образом обрабатываем удаленный с вершины элемент, например – просто освобождаем занимаемую им память вызовом Dispose(рTemp), или включаем его во вспомогательную структуру (например – стек удаляемых элементов).
Сравнение статической и динамической реализации стека: при статической реализации расходуется меньше памяти, но требуется знание максимального числа элементов в стеке-массиве; динамическая реализация более гибкая, но каждый элемент стека дополнительно расходует память на ссылочную часть (чаще всего – 4 байта), что при большом числе элементов может стать весьма ощутимым.
