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

Бакнелл Джулиан М.

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.