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

Конечно, реализация описанной организации требует большего объема в плане принятия решений. Класс стека можно реализовать как дочерний класса односвяз-ного списка или делегировать операции заталкивания и выталкивания внутреннему экземпляру класса связного списка. Первый вариант не особенно эффективен: мы придем к реализации класса с методами 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 (altem : 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(tdeStacklsEmpty, 1Examine1);
Result : = FHeadA.slnNextA.slnData;
ends-function TtdStack. I sEmpt у : 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) ;
FHeadA. slnNext :«= nil;
FHeadA.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(altem : pointer); var
Temp : PslNode;
begin
{распределить новый узел и поместить его в начало стека] Temp : = PslNode (SLNodeManager. AllocNode) ; Temp*.slnData : = altem;
TempA.slnNext : = FHeadA.slnNext;
FHeadA. slnNext: = Temp;
inc(FCount);
end;
function TtdStack. Pop : pointer;
var
Temp : PslNode;
begin
if (Count - 0) then sError(tdeStacklsEmpty, 1 Pop');

{обратите внимание, что даже если это возможно, мы не удаляем данные узла; этот метод должен возвращать данные]

Temp : = FHeadA.slnNext;
Result : = TempA.slnData;
FHeadA. slnNext : = TempA. slnNext;
SLNodeManager.FreeNode(Temp);
dec(FCount);
end;

Полный код класса TtdStack можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStkQue.pas.

Стеки || Оглавление || Стеки на основе массивов


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



Новости за месяц

  • Октябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс