Структура данных — абстрактное понятие, представляет собой совокупность однотипных элементов, размещенных в памяти компьютера. Добавление, удаление, изменение, поиск реализуются функциями структуры данных, которые называются ее интерфейсом. Сегодня мы рассмотрим две самые простые структуры данных, это очередь и стек. Для их реализации используем ООП подход и создадим отдельные классы, с соответствующими методами. Язык и среда разработки — Delphi.

Подробнее под катом.

Очередь

Очередь — структура данных, у которой дисциплина элементов организована по принципу, который называется «первый вошел — первый вышел» или FIFO(First In — First Out). В интерфейсе очереди присутствуют зачастую две функции: enqueue и dequeue. Enqueue — добавляет элемент в очередь. Dequeue — извлекает элемент из очереди.

Теперь будем реализовывать. Для начала я решил изобразить схему очереди. Вышло вот так:

Element #1(2,N) — это элементы очереди. Каждый элемент состоит из значения и указателя на следующий элемент. Значением может выступать все что угодно. Грубо говоря значение элемента — это просто область памяти хранящая какие-либо данные. Указатель — это просто адрес памяти, где храниться следующий элемент.

Сама очередь будет хранить указатели только на первый и последний элемент. Первый элемент очереди обычно называется «голова», а последний «хвост». Доступ к хвосту, путем перебора позволяет получить любой элемент из очереди.

Что бы конкретно понять, как работает очередь, приведу элементарный пример из жизни: очередь в магазине:

Вы вошли в магазин. В данный момент — вы новый элемент очереди, уже созданный, но не принадлежите очереди. Выбрав товар — подходите к кассе. Становитесь в конец очереди. В этот момент вы — хвост очереди, а тот, кто спереди вас — знает, что за ним стоите вы. Очередь постепенно уменьшается. За вами становится еще человек. Теперь он хвост, а вы теперь не крайний. Когда подходит ваша очередь рассчитываться на кассе — вы голова очереди, так как впереди вас никого нет. Если в этот момент сзади вас тоже никого, то вы являетесь и головой, и хвостом очереди. Вы рассчитались и покинули очередь. Если за вами кто-то был, теперь он голова очереди. Если нет — очередь пуста.

Теперь приступим к написанию кода. Я буду использовать Delphi 7 Lite. Обзор этой IDE можно найти здесь. Создадим пустой Unit для удобства, который будет содержать код нашей очереди. Сначала в разделе interface, подразделе type определим структуру очереди:

  TElement = integer;
  TNodePointer = ^TNode;
  TNode = record
    value: TElement;
    next: TNodePointer;
  end;

Первая строка определяет новый тип TElement. Он равен integer. Зачем это? Очередь лишь структура, она может содержать любой тип данных. Поэтому я далее в коде буду использовать TElement. Если мне понадобится создать очередь из строк(string), не нужно будет менять весь код, я просто поменяю TElement = integer на TElement = string. Следующая строка TNodePointer = ^TNode объявляет тип TNodePointer, который является указателем на TNode. А TNode объявляется в следующей строке как структура(запись), состоящая из двух полей value и next. Собственно TNode и есть наш элемент очереди. Поле value, типа TElement, хранит значение элемента, а next, типа TNodePointer, указатель на следующий элемент.

С элементом разобрались. Теперь напишем класс для очереди.

  TMyQueue = class(TObject)
  private
    fHead: TNodePointer;
    fTail: TNodePointer;
  public
    constructor Create;
    destructor Destroy;
    procedure Enqueue(item: TElement);
    function Dequeue: TElement;
    function isEmpty: boolean;
  end;

Класс очереди содержит два private поля, это fHead — голова очереди, и fTail — хвост очереди. В public класса есть конструктор/деструктор, методы добавления/удаления (Enqueue/Dequeue) элементов из очереди, и функция isEmpty, которая проверяет «не пуста ли очередь?».

Теперь в разделе implementation будем описывать все методы класс. Начнем с конструктора.

  constructor TMyQueue.Create;
  begin
    fHead:= nil;
    fTail:= nil;
  end;

Все очень просто. При создании очереди, ее поля fHead и fTail инициализируются nil‘ом для избегания ошибок.

Деструктор ненамного сложнее.

  destructor TMyQueue.Destroy;
  begin
    while not isEmpty do
      Dequeue;
    fHead:= nil;
    fTail:= nil;
  end;

Алгоритм простой. Пока очередь не пуста, мы извлекаем элементы. По окончанию цикла, голову и хвост устанавливаем в nil. Проверка на условие «пуста ли очередь?» осуществляется функцией isEmpty, но реализуем ее позже. Приступим к реализации процедуры Enqueue, которая добавляет элемент в очередь.

  procedure TMyQueue.Enqueue(item: TElement);
  var
    temp: TNodePointer;
  begin
    New(temp);
    temp^.value:= item;
    temp^.next:= nil;
    if (isEmpty) then
    begin
      fHead:= temp;
      fTail:= temp;
    end
    else
    begin
      fTail^.next:= temp;
      fTail:= temp;
    end;
  end;

Как это работает? Мы объявляем указатель на элемент очередь, то есть просто переменную, которая может содержать адрес элемента. Выделяем ему память с помощью New(temp). При выделении памяти, процессор сначала размещает в памяти пустой элемент TNode, а его адрес копирует в temp. В следующих строках, мы присваиваем полям элемента, который только что создался, значения. Поле value = item, то есть value равно значению, которое передалось в функцию Enqueue. Поле next должно содержать указатель на следующий элемент. Но следующего элемента нет, поскольку это конец очереди. Поэтому temp^.next = nil. Далее идет проверка «пуста ли очередь?». Если пуста — голова и хвост очереди будут указывать на один и тот же элемент. А если очередь содержит элементы, то новый необходимо добавить в конец очереди, то есть в хвост. Это означает, что текущий хвост очереди должен стать рядовым элементом и указывать на новый элемент, а новый элемент станет хвостом очереди. Реализуется это не сложно. Поскольку у нас есть указатель на текущий хвост, мы можем его полю next присвоить адрес памяти нового элемента, то есть temp, что и происходит в строке fTail^.next:= temp. После этого необходимо, что бы указатель очереди fTail указывал на новый элемент, поэтому мы делаем fTail:= temp.

Теперь напишем функцию извлекающую элемент.

  function TMyQueue.Dequeue: TElement;
  var
    temp: TNodePointer;
  begin
    if not isEmpty then
    begin
      temp:= fHead;
      fHead:= fHead^.next;
      result:= temp^.value;
      Dispose(temp);
    end
    else
      result:= 0;
  end;

Все очень просто. Создаем временный указатель. Присваиваем ему адрес головы очереди. После этого сдвигаем голову на один элемент. Каким образом? fHead^.next указывает на второй элемент очереди — сразу за головой, так как сейчас голова покинет очередь, то второй — должен стать головой, поэтому я написал fHead:= fHead^.next. Результатом функции будем значение, которое хранила голова очереди. Это определяет строка result:= temp^.value. Далее мы освобождаем память, выделенную для бывшей головы очереди(temp). Если очередь пуста — возвращаем 0.

Ну и осталась функция isEmpty. Все очень просто: если голова очереди равна nil – значит в ней нет элементов, а это значит что она пуста.

  function TMyQueue.isEmpty: boolean;
  begin
    result:= fHead = nil;
  end;

Выражение (fHead = nil) булевое. Как вы уже догадались, если fHead = nil, функция isEmpty вернет true — то есть очередь пуста.

Вот и завершен наш класс. Необходимо его протестировать. Я создал простую форму с двумя кнопками. В разделе var объявил переменную своего класса TMyQueue.

var
  Form1: TForm1;
  queue: TMyQueue;

Далее я выделил память своей переменной в событии формы OnCreate.

procedure TForm1.FormCreate(Sender: TObject);
begin
  queue:= TMyQueue.Create;
end;

Потом я бросил две кнопки на форму btnEnqueue, btnDequeue. Первая btnEnqueue добавляет немного элементов в очередь.

procedure TForm1.btnEnqueueClick(Sender: TObject);
begin
  queue.Enqueue(5);
  queue.Enqueue(4);
  queue.Enqueue(3);
  queue.Enqueue(2);
  queue.Enqueue(1);
end;

Вторая вытаскивает по одному, при этом проверяет пуста ли очередь.

procedure TForm1.btnDequeueClick(Sender: TObject);
begin
  if not queue.isEmpty then
    ShowMessage(IntToStr(queue.Dequeue))
  else
    ShowMessage('Queue is Empty!');
end;

Все работает!

Стек

Стек — структура данных организованная по принципу «последний вошел — первый выше», то есть LIFO(Last In First Out). Интерфейс стека похож на интерфейс очереди, но в нем только одно поле, указывающее на голову. Функции аналогичные.

Самый распространенный пример из жизни:

Стопка тарелок. Вы идете на кухню и берете верхнею тарелку из стопки. Обедаете. Потом моете тарелку. Помыли — положили в стопку. Теперь вам снова она понадобилась, вы опять берете верхнею. Если вам нужна все-таки вторая тарелка, то придется извлечь верхнею, а потом взять вторую.

Начнем. Элемент стека выглядит так же, как и у очереди.

type
  TElement = integer;
  TNodePointer = ^TNode;
  TNode = record
    value: TElement;
    next: TNodePointer;
  end;

Интерфейс стека немного отличается.

  TMyStack = class(TObject)
  private
    fHead: TNodePointer;
  public
    constructor Create;
    destructor Destroy;
    procedure Add(item: TElement);
    function Take: TElement;
    function isEmpty: boolean;
  end;

Как видите, в очереди лишь было дополнительное поле и функции назывались по-другому :). Реализация Create и Destroy почти такая же.

  constructor TMyStack.Create;
  begin
    fHead:= nil;
  end;

  destructor TMyStack.Destroy;
  begin
    while not isEmpty do
      Take;
    fHead:= nil;
  end;

Отличия опять-таки же в отсутствии хвоста. Функция добавления в стек отличается от функции добавления в очередь. В очереди мы добавляли элемент в конец, а здесь в начало.

  procedure TMyStack.Add(item: TElement);
  var
    temp: TNodePointer;
  begin
    New(temp);
    temp^.value:= item;
    temp^.next:= nil;
    if (isEmpty) then
      fHead:= temp
    else
      temp^.next:= fHead;
      fHead:= temp;
  end;

Опять-таки, если стек пуст — просто указываем голове наш вновь созданный элемент. Если нет, следуем алгоритму. Голова элемента указывает на следующий элемент. Следующий на следующий и так до конца. Наш новый элемент будет головой, поэтому он должен указывать на следующий элемент, то есть текущую голову. Это делает строчка temp^.next:= fHead. После этого поле fHead должно указывать но новую голову, это делает строка fHead:= temp.

Функция удаления проще чем в очереди.

  function TMyStack.Take: TElement;
  var
    temp: TNodePointer;
  begin
    if not isEmpty then
    begin
      temp:= fHead;
      fHead:= fHead^.next;
      result:= temp^.value;
      Dispose(temp);
    end
    else
      result:= 0;
  end;

Если очередь не пуста, удаляем элемент. Сначала временному указателю «даем» нашу голову. Теперь смещаем голову стека на следующий элемент строчкой fHead:= fHead^.next. Результатом функции будет значение элемента, который мы вытаскиваем. Указатель на него хранится в temp, поэтому я написал result:= temp^.value. Освобождаем память извлеченного элемента строкой Dispose(temp). Если очередь пуста — возвращаем ноль.

Функция isEmpty ничем не отличается от аналогичной в очереди.

  function TMyStack.isEmpty: boolean;
  begin
    result:= fHead = nil;
  end;

Все стек готов. Протестировать его можно точно так же, заменив в коде формы все упоминания про очередь, на аналогичный код стека.

Как видите абсолютно разные структуры данных, не такие уж и разные. Если вы новичок, и не понимаете зачем это нужно, вспомните хотя бы очередь процессов в операционной системе, она реализована подобными механизмами. Задавайте свои ответы, комментируете, пишите пожелания.