Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
Листинг 3.18. Класс TtdStack
TtdStack = class private
FCount : longint;
FDispose : TtdDisposeProc;
FHead : PslNode;
FName : TtdNameString;
protected
procedure sError(aErrorCode : integer;
const aMethodName : TtdNameString);
class procedure sGetNodeManager;
public
constructor Create(aDispose : TtdDisposeProc);
destructor Destroy; override;
procedure Clear;
function Examine : pointer;
function IsEmpty : boolean;
function Pop : pointer;
procedure Push(aItem : pointer);
property Count : longint read FCount;
property Name : TtdNameString read FName write FName;
end;
Метод Examine возвращает первый элемент стека, не выталкивая его из стека. Он бывает очень удобным в использовании, поскольку не требует выталкивания элемента с последующим заталкиванием. Метод IsEmpty возвращает значение true, если стек пуст, что эквивалентно проверке равенства нулю свойства Count.
Листинг 3.19. Методы Examine и Is Empty для класса TtdStack
function TtdStack.Examine : pointer;
begin
if (Count = 0) then
sError(tdeStackIsEmpty, 'Examine');
Result := FHead^.slnNext^.slnData;
end;
function TtdStack.IsEmpty : boolean;
begin
Result := (Count = 0);
end;
Конструктор Create работает аналогично конструктору класса односвязного списка. Он проверяет, существует ли диспетчер узлов, а затем с помощью диспетчера распределяет фиктивный начальный узел, который, естественно, ни на что не указывает. Деструктор Destroy очищает стек и освобождает фиктивный начальный узел, FHead, возвращая его диспетчеру узлов.
Листинг 3.20. Конструктор и деструктор класса TtdStack
constructor TtdStack.Create(aDispose : TtdDisposeProc);
begin
inherited Create;
{сохранить процедуру удаления}
FDispose := aDispose;
{получить диспетчер узлов}
sGetNodeManager;
{распределить начальный узел}
FHead := PslNode (SLNodeManager.AllocNode);
FHead^.slnNext := nil;
FHead^.slnData := nil;
end;
destructor TtdStack.Destroy;
begin
{удалить все оставшиеся узлы; очистить начальный фиктивный узел}
if (Count <> 0) then
Clear;
SLNodeManager.FreeNode(FHead);
inherited Destroy;
end;
Заталкивание элемента в стек и выталкивание его из стека представляют собой короткие процедуры. Push распределяет новый узел при помощи диспетчера узлов и вставляет его после фиктивного начального узла. Метод Pop перед удалением связей узла с фиктивным узлом с помощью алгоритма "удалить после" проверяет, существует ли в стеке хотя бы один узел. Затем он возвращает элемент и освобождает узел, возвращая его диспетчеру узлов.
Листинг 3.21. Методы Push и Pop класса TtdStack
procedure TtdStack.Push(aItem : pointer);
var
Temp : PslNode;
begin
{распределить новый узел и поместить его в начало стека}
Temp := PslNode(SLNodeManager.AllocNode);
Temp^.slnData := aItem;
Temp^.slnNext := FHead^.slnNext;
FHead^.slnNext := Temp;
inc(FCount);
end;
function TtdStack.Pop : pointer;
var
Temp : PslNode;
begin
if (Count = 0) then
sError(tdeStackIsEmpty, 'Pop');
{обратите внимание, что даже если это возможно, мы не удаляем данные узла; этот метод должен возвращать данные}
Temp := FHead^.slnNext;
Result := Temp^.slnData;
FHead^.slnNext := Temp^.slnNext;
SLNodeManager.FreeNode(Temp);
dec(FCount);
end;
Полный код класса TtdStack можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStkQue.pas.
Стеки на основе массивов
После написания класса стека, основанного на связном списке, давайте перейдем к исследованию стеков, реализованных на базе массивов. Причина для организации такого класса заключается в том, что во многих случаях реализация стека на одном из простых типов (например, char или double) гораздо проще в случае применения массивов.
Ради простоты, в качестве базового массива возьмем класс TList. Другими словами, мы создадим класс стека указателей. В предыдущей версии стека операция Push вставляла узел в начало списка, а операция Pop выбирала узел из начала списка. Это не самый эффективный метод работы с массивами. Вставка в начало списка принадлежит к классу операций О(n), а нам желательно разработать операцию класса O(1), как в ситуации со связными списками, Поэтому при заталкивании и выталкивании элемента мы будем вставлять и удалять элемент в конце списка.
Рисунок 3.8.
Использование массива для организации стека
Рассмотрим интерфейс класса TtdArrayStack. Как видите, его раздел public полностью соответствует разделу public класса TtdStack.
Листинг 3.22. Класс TtdArrayStack
TtdArrayStack = class private
FCount : longint;
FDispose : TtdDisposeProc;
FList : TList;
FName : TtdNameString;
protected
procedure asError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure asGrow;
public
constructor Create(aDispose : TtdDisposeProc;
aCapacity : integer);
destructor Destroy; override;
procedure Clear;
function Examine : pointer;
function IsEmpty : boolean;
function Pop : pointer;
procedure Push(aItem : pointer);
property Count : longint read FCount;
property Name : TtdNameString read FName write FName;
end;
Конструктор и деструктор, соответственно, создает и удаляет экземпляр класса TList. Конструктор в качестве входного параметра принимает емкость стека. Это только начальное значение для количества элементов в экземпляре массива, предназначенное только для повышения эффективности класса, а не для установки каких-либо ограничений.
Листинг 3.23. Конструктор и деструктор класса TtdArrayStack
constructor TtdArrayStack.Create(aDispose : TtdDisposeProc;
aCapacity : integer);
begin
inherited Create;
{сохранить процедуру удаления}
FDispose := aDispose;
{создать внутренний экземпляр класса TList и установить его емкость равной aCapacity}
FList := TList.Create;
if (aCapacity <= 1) then
aCapacity 16;
FList.Count := aCapacity;
end;
destructor TtdArrayStack.Destroy;
begin
FList.Free;
inherited Destroy;
end;
Методы Push и Pep содержат довольно-таки интересный код. Внутреннее поле FCount используется для двух целей. Первая цель связана с хранением количества элементов в стеке, а вторая предполагает его использование в качестве указателя стека. Для заталкивания элемента в стек мы записываем его в позицию с индексом FCount и увеличивает FCount на единицу. Для выталкивания элемента из стека мы выполняем обратную операцию: уменьшаем значение FCount на единицу и возвращаем элемент с индексом FCount.
Листинг 3.24. Методы Push и Pop класса TtdArrayStack
procedure TtdArrayStack.asGrow;
begin
FList.Count := (FList.Count * 3) div 2;
end;
function TtdArrayStack.Pop : pointer;
begin
{убедиться, что стек не пуст}
if (Count = 0) then
asError(tdeStackIsEmpty, 'Pop');
{уменьшить значение счетчика на единицу}
dec(FCount);
{выталкиваемый элемент находиться в конце списка}
Result := FList[FCount];
end;
procedure TtdArrayStack.Push(aItem : pointer);
begin
{проверить, полон ли стек; если стек полон, увеличить емкость списка}
if (FCount = FList.Count) then
asGrow;
{добавить элемент в конец стека}
FList[FCount] := aItem;
{увеличить значение счетчика на единицу}
inc(FCount);
end;
Полный код класса TtdArrayStack можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStkQue.pae.
Пример использования стека
Стеки используются в случае, когда требуется вычислить элементы в обратном порядке, а затем перестроить их в прямой порядок. Одним из самых простых примеров может служить изменение порядка символов в строке. При наличии стека символов задание становится очень простым: затолкнуть символы из строки в стек, а затем вытолкнуть их в обратном порядке. (Разумеется, существуют и другие методы изменения порядка символов в строке.)
Интересной вариацией этой темы является преобразование целого значения в строку. В языке Object Pascal имеются функции str и intToStr, которые позволяют решать поставленную задачу далеко не с нуля, но, тем не менее, задача остается достаточно интересной.
Давайте четко запишем условия задачи. Необходимо написать функцию, которая в качестве параметра принимала бы значение типа longint и возвращала бы значение в форме строки.
Внутри функции нужно будет вычислять цифры, соответствующие целочисленному значению. Простейший метод таких вычислений - вычислить остаток от деления значения на 10 (это будут числа от 0 до 9 включительно), сохранить его где-нибудь, поделить значение на 10 (чтобы избавиться от только что вычисленного нами значения) и повторить процесс. Цикл вычислений продолжается до тех пор, пока не будет получено значение 0.
Давайте применим описанный алгоритм (да-да, это алгоритм!) к числу 123. Остаток от деления 123 на 10 равен 3. Записываем остаток. Делим 123 на 10. Получаем 12. Остаток от деления 12 на 10 равен 2. Записываем остаток. Делим 12 на 10. Получаем 1. Остаток от деления 1 на 10 равен 1. Записываем остаток. Делим 1 на 10. Получаем 0. Завершаем вычисления. Цифры были вычислены в следующем порядке: 3, 2, 1. Однако в строке они должны находиться в обратном порядке. Мы не можем записывать цифры в строку по мере их вычисления (какой длины должна быть строка?).
Можно предложить заталкивать цифры в стек по мере их вычисления, а после выполнения вычислений определить количество элементов в стеке (т.е. длину строки) и постепенно выталкивать их в строку. Соответствующий код приведен в листинге 3.25.
Листинг 3.25. Преобразование целочисленного значения в строку
function tdlntToStr(aValue : longint): string;
var
ChStack : array [0..10] of char;
