Стек (stack) - это упорядоченный список, где элементы всегда добавляются
и удаляются с одного конца. Стек можно сравнить со стопкой книг на полу. Вы
можете добавлять книги на вершину стопки и убрать их с вершины, но добавить
или убрать книгу из середины стопки вы не сможете.
Стеки часто называют списками типа последний пришел — первый вышел (Last-
In-First-Out list — LIFO). По историческим причинам добавление элемента в стек
называется проталкиванием (pushing), а удаление - выталкиванием (popping).
Первая реализация простого списка на основе массива, описанное в начале
главы 2, является стеком. Для отслеживания положения вершины списка исполь-
зуется счетчик. Затем с помощью счетчика осуществляется вставка и удаление эле-
ментов из вершины списка.
Единственное незначительное изменение, сделанное в данном случае, - это
введение новой функции Pop, которая удаляет элемент из стека и возвращает его
значение. Это позволяет другим процедурам отыскивать элемент и удалять его из
стека за один шаг.
// Проталкивание элемента в стек.
procedure TArrayStack.Push(value : String);
begin
// Убедиться, что для элемента есть место.
if (NumItems>=NumAllocated) then ResizeStack;
Numltems := Numltems+1;
Stack^[Numltems] := value;
end;
// Выталкивание элемента из стека.
function TArrayStack.Pop : String;
begin
if (Numltems<l) then
raise EInvalidOperation.Create('Стек пустой.');
Result := Stack^[Numltems] ;
NumIterns := NumIterns-1;
if (NumItems<ShrinkWhen) then ResizeStack;
end;
Все предыдущее рассуждения о списках также относятся к этому способу реа-
лизации стека. В частности, вы можете экономить время, если не будете изменять
размеры массива всякий раз при каждом добавлении или выталкивании элемента.
Программа Astack с несколькими стеками на основе массивов позволяет без труда
вставлять и удалять элементы стека.
Программы часто используют стеки для хранения последовательности элемен-
тов, с которыми программа будет работать до тех пор, пока стек не опустеет. Рабо-
та с одним элементом может вызвать проталкивание в стек других элементов, но
в конце концов они все будут удалены. В качестве простого примера можно приве-
сти алгоритм обращения порядка элементов в массиве. Здесь каждый элемент по-
мещается в стек по порядку. Затем каждый элемент выталкивается из стека в об-
ратном порядке и записывается обратно в массив.
procedure ReverseArray;
var
the_stack : TArrayStack;
i : Integer;
begin
// Создание стека.
the_stack := TArrayStack.Create;
// Проталкивание элементов в стек.
for i := 1 to Numltems do
the_stack.Push(the_array[i]);
// Выталкивание элементов из стека и помещение их обратно в массив.
for i := 1 to Numltems do
the_array[i] := the_stack.Pop;
end;
В этом примере длина стека может многократно изменяться до тех пор, пока он
не опустеет. Если вы заранее знаете, каким должен быть размер массива, лучше сра-
зу создать подходящий стек. Тогда вместо изменения размера стека по мере того,
как он растет или уменьшается, достаточно будет выделить под него память в нача-
ле работы и очистить ее после окончания действий.
Следующий код позволяет заранее сформировать стек, если сразу известен его
максимальный размер. Функция Pop не изменяет размер массива. Когда програм-
ма заканчивает работу со стеком, она должна вызвать процедуру FreeStack для
освобождения занятой под стек памяти.
// Создание большого массива, достаточного для размещения всего стека.
procedure TArrayStack.PreallocateStack(entries : Integer);
begin
NumAllocated := entries;
GetMem(Stack,NumAllocated*SizeOf(Longint));
end;
// Освобождение массива стека.
procedure TSimpleStack.FreeStack;.
begin
NumAllocated := 0;
PreeMem(Stack);
end;
// Проталкивание элемента в стек.
procedure TArrayStack.Push(value : String);
begin
// Убедиться, что для элемента есть место
if (NumItems>=NumAllocated) then
raise EInvalidOperation.Create('Стек заполнен.');
Numltems := Numltems+l;
Stack^[NumItems] := value;
end;
// Выталкивание элемента из стека.
function TArrayStack.Pop : String;
begin
if (Numltems<l) then
raise EInvalidOperation.Create('Стек пустой.');
Result := Stack^[Numltems];
NumIt ems : = NumItems-1;
end;
Этот способ реализации стеков весьма эффективен. Стек не расходует пона-
прасну память, и не требуется дополнительное время для частого изменения его
размера, особенно если сразу известно, насколько большим он должен быть. |
Главная
Каталог файлов
