Вместо этого мы предлагаем пример модуля, реализующего процедуры работы со стеком. Стек, или магазин, иногда называется списком LIFO (последним вошел — первым вышел). Это структура данных, при которой элемент, первым помещенный в стек, будет извлечен оттуда последним. И наоборот, доступнее всех последний положенный в стек элемент. Аналог стека — детская разборная пирамидка из дисков на штырьках. Надеть диск сверху — значит поместить в стек очередное значение. Снять диск (а снять можно только верхний диск) — значит вытолкнуть значение из стека. Доступ к содержимому стека всегда последователен, причем порядок выгрузки элементов из стека обратен порядку их загрузки в стек.
Организация стека основана на связном списке, и поэтому стек занимает в памяти только необходимый на данный момент объем. Наглядно структура стека представлена на рис. 11.9.
Рис. 11.9
- 215 -
Сумма размеров всех хранимых в стеке данных ограничена только размером свободной памяти в куче, хотя элемент данных по-прежнему не должен превышать 64K. Стек оптимален для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке (в других случаях он мало полезен). К недостатку стека и списков, вообще, надо отнести расход памяти под узлы (здесь — 2x4 байта на каждый узел). Но если элемент хранимых данных имеет размер, например, 16K, с восемью байтами можно примириться.
Ниже приведен текст модуля StackManager (рис. 11.10), реализующего операции со стеком и пример программы, использующей его (рис. 11.11). Все тексты написаны и любезно предоставлены Г.П. Шушпановым.
| UNIT StackManager; {БИБЛИОТЕКА СРЕДСТВ РАБОТЫ СО СТЕКОМ }
| INTERFACE
| CONST { коды ошибок, возникающих при работе со стеком }
| StackOk =0; { успешное завершение }
| StackOverflow =1; { переполнение стека }
| StackUnderflow =2; { стек был пуст }
| VAR
| StackError : Byte; { результат операции со стеком }
| TYPE
| NodePtr = ^Node; { ссылка на узел }
| Node = RECORD { Узел, состоящий из }
| Info : Pointer; { ссылки на значение и }
| Next : NodePtr; { ссылки на следующий }
| END; { узел. }
| Stack = RECORD { тип стека - запись }
| Head : NodePtr; { ссылка на голову списка }
| Size : Word; { размер элемента данных в }
| END; { стеке }
| PROCEDURE InitStack( VAR S : Stack; Size : Word );
| { формирует стек с элементами размера Size }
| PROCEDURE ReInitStack(VAR S : Stack; Size : Word);
| { переопределяет стек для элементов другого размера }
| PROCEDURE ClearStack( VAR S : Stack );
| { очищает стек }
| PROCEDURE Push( VAR S : Stack; VAR E );
| { помещает значение переменной E в стек S }
Рис. 11.10
- 216 -
| PROCEDURE Pop( VAR S : Stack; VAR E );
| { выталкивает значение из стека в переменную E }
| PROCEDURE Top( VAR S : Stack; VAR Е );
| { копирует значение на вершине стека в переменную E }
| FUNCTION Empty( VAR S : Stack ) : Boolean;
| { возвращает True, если стек пуст }
| IMPLEMENTATION
| VAR { переменная для хранения }
| SaveHeapError : Pointer; { адреса старой функции }
| { обработки ошибок кучи }
| {$F+}
| FUNCTION HeapFunc( Size : Word ) : Integer;
| BEGIN
| HeapFunc := 1;
| {вернуть nil, если нельзя разместить переменную в куче}
| END;
| {$F-}
| PROCEDURE InitStack( VAR S : Stack; Size : Word );
| BEGIN { сохранение стандартного }
| SaveHeapError := HeapError; { обработчика ошибок кучи }
| S.Head := nil; { установка вершины }
| S.Size := Size; { размер значения }
| StackError := StackOk; { все в порядке }
| END;
| PROCEDURE ReInitStack(VAR S : Stack; Size : Word );
| BEGIN
| if S.Head <> nil then
| ClearStack(S); { очистка стека }
| S.Size := Size; { установка нового размера значения }
