После написания класса стека, основанного на связном списке, давайте перейдем к исследованию стеков, реализованных на базе массивов. Причина для организации такого класса заключается в том, что во многих случаях реализация стека на одном из простых типов (например, char или double) гораздо проще в случае применения массивов.

Ради простоты, в качестве базового массива возьмем класс TList. Другими словами, мы создадим класс стека указателей. В предыдущей версии стека операция Push вставляла узел в начало списка, а операция ррр выбирала узел из начала списка. Это не самый эффектив-щлй метод работы с массивами. Вставка в начало списка принадлежит к классу операций О(л), а нам желательно разработать операцию класса O(l), как в ситуации со связными списками, Поэтому при заталкивании и выталкивании элемента мы будем вставлять и удалять элемент в коцце списка.

Рисунок 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(altem : 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) div2;
end;
function TtdArrayStack. Pop : pointer;
begin
{убедиться, что стек не пуст) if (Count - 0) then
asError(tdeStacklsEmpty, 1 Pop'); {уменьшить значение счетчика на единицу} dec(FCount);
{выталкиваемый элемент находиться в конце списка) Result := FList[FCount];
end;
procedure TtdArrayStack. Push (altem : pointer);
begin
{проверить, полон ли стек; если стек полон, увеличить емкость списка) if (FCount = FList.Count) then asGrow;
{добавить элемент в конец стека) FList[FCount] := altem; {увеличить значение счетчика на единицу} inc(FCount);
end;

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

Стеки на основе односвязных списков || Оглавление || Пример использования стека


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



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

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