Фундаментальные алгоритмы и структуры данных в Delphi

Листинг 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;

ChSP : integer;

IsNeg : boolean;

i : integer;

begin

{установить нулевую длину стека}

ChSP := 0;