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

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

Стеки

Еще одной известной и широко используемой структурой данных является стек. Стек представляет собой структуру, которая позволяет выполнять две основных операции: заталкивание для вставки элемента в стек и выталкивание с целью считывания данных из стека. Структура устроена таким образом, что операция выталкивания всегда возвращает элемент, вставленный в стек последним (самый "новый" элемент в стеке). Другими словами, элементы в стеке считываются в порядке, обратном порядку их записи в стек. Благодаря такому устройству стек известен как контейнер магазинного

типа.

Рисунок 3.7. Операции заталкивания и выталкивания для стека

Написание кода стека не представляет никаких трудностей. Причем существуют два варианта реализации: первый - на основе односвязного списка, второй -на основе массива. Как и в случае со списками, будем считать, что записываться и считываться из стека будут указатели на элементы. Сначала рассмотрим организацию стека на базе связного списка.

Стеки на основе односвязных списков

В реализации стеков на основе односвязных списков операция заталкивания представляет собой вставку элемента в начало списка, а операция выталкивания - удаление элемента из начала списка и считывание его данных. Обе операции не зависят от количества элементов в списке, следовательно, их можно отнести к классу O(1). Вот и все, что касается организации стека.

Конечно, реализация описанной организации требует большего объема в плане принятия решений. Класс стека можно реализовать как дочерний класса односвязного списка или делегировать операции заталкивания и выталкивания внутреннему экземпляру класса связного списка. Первый вариант не особенно эффективен: мы придем к реализации класса с методами Push и Pop, но при этом у нас останутся и другие методы связного списка (Insert, Delete и т.д.). Понятно, что это не самое лучшее решение.

Второй вариант реализации, делегирование, - чисто в духе Delphi. Класс стека можно организовать именно таким образом. Конструктор Create будет создавать новый экземпляр класса TtdSingleLinkList и устанавливать курсор после начального узла, деструктор Destroy будет уничтожать созданный конструктором экземпляр. Метод Push будет пользоваться экземпляром класса для вставки элемента в позицию курсора, а метод Pop будет удалять элемент в позиции курсора, предварительно сохранив его значение. Вполне реализуемое решение.

Тем не менее, мы будем писать класс TtdStack, исходя из первых принципов. TtdStack - простой класс, и за счет этого мы попытаемся увеличить его быстродействие и эффективность.

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