Очередь и стек в Delphi

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

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

Очередь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стек

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

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии 15

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *