Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 46

Заталкивание элемента в стек и выталкивание его из стека представляют собой короткие процедуры. 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;