Пример — очередь объектов

В этой части я хочу предложить пример, который позволит нам посмотреть как можно организовать взаимодействие объектов для реализации достаточно распространенной структуры данных — очереди. Т.е. я хочу создать класс, который позволит мне «складывать» туда объекты в заранее неизвестном количестве и «вынимать» объекты из этой очереди. Такая функциональность часто называется FIFO — First In First Out — первый пришел, первый ушел. По сути наш класс должен иметь три метода:

  1. Положить объект (произвольного класса) в очередь — назовем метод push
  2. Вытащить объект (произвольного класса) из очереди — назовем метод pull
  3. Получить количество объектов в очереди — назовем его size

Итак, наш класс ObjectQueue будет выглядеть (без реализации, только с методами) вот так:

Как видите, мы может положить в очередь объект типа Object, что означает, что мы можем положить туда все, что угодно — как вы должны помнить, класс Object является «проматерью» всех классов — все классы наследуются в конечном итоге от него (если не прямо от него, то он будет их дедушкой, прадедушкой и т.д.).
Предлагаю сразу написать маленький класс для тестирования нашей очереди

Можно видеть, что сначала мы помещаем в очередь объект класса String (первый цикл от 0 до 10 и потом выбираем все объекты до тех пор, пока размер очереди не станет нулевым. Обратите внимание на то, что мы делаем приведение типа объекта при его получении. Когда мы начнем говорить о коллекциях, мы об этом вспомним.
Теперь давайте подумаем над реализацией нашей очереди. Большинство книг по структурам данных содержит такое понятие как связный список. Если быть точнее — однонаправленный связный список. Сама идея списка достаточно простая — ее можно посмотреть на рисунке.

Как видите, все достаточно несложно. У нас есть структура, которая содержит два элемента:

  1. Хранилище для данных
  2. Указатель на следующий элемент

При добавлении нового элемента нам надо создать такую структуру (по сути это объект с двумя полями), поместить в хранилище данных переданный объект и указатель у последнего элемента в списке «указать» на добавляемый объект. Мы как бы «прикрепляем» новый объект к существующей цепочке объектов. Однонаправленная очередь потому, что двигаться по ней можно только в одном направлении — от «головы» к «хвосту».
Как мы только что говорили, нам потребуется вспомогательный объект — назовем его OjectBox и т.к. он в общем-то никому не нужен, мы можем объявить его внутри нашего класса ObjectQueue. Смотрим:

Как видите — все просто. В поле object мы будем помещать сам добавляемый объект, а поле next будет указывать на следующий элемент в цепочке.
Теперь поговорим о классе ObjectQueue. Ему необходимо иметь поле, которое указывает на самый первый элемент — нам же надо с чего-то начинать и брать элементы из очереди мы будем как раз с «головы». В принципе одного этого элемента достаточно, но это будет крайне не эффективно. Потому что при добавлении вам придется каждый раз пробегать от «головы» до «хвоста» и уже только после нахождения «хвоста» можно будет добавлять новый элемент. В качестве тренировки вы можете реализовать сами такой вариант. Но мы все-таки сделаем более корректно — введем еще одно поле, которое будет всегда указывать на «хвост» — на последний элемент в очереди. Наличие этого элемента позволяет создавать очень эффективную структуру с очень важной характеристикой — время добавления нового элемента не зависит от размера списка. Очередь может содержать 100 элементов или 100000 — время добавления будет всегда одинаковое. Но у такой структуры есть минус — если вы хотите найти элемент на определенной позиции — например 184-й — то эта операция будет исполняться долго для больших списков. Но вернемся к задаче — как обычно, я предлагаю сразу смотреть код и комментарии к нему.

Класс для тестирования нашей очереди

Пример — очередь объектов. Добавляем функциональность

Теперь мы добавим удобную функцию — получение элемента по индексу (по номеру в очереди. Эта функция не будет удалять элемент из очереди — она просто вернет элемент. В этом коде мы увидим, что скорость исполнения здесь зависит от размера очереди — чем он больше, тем функция будет работать дольше. И как говорил герой из фильма «В бой идут одни старики» — «Серега, не надо слов». Смотрим код.

Полный код проекта можно скачать отсюда: ObjectQueue.zip.

Домашнее задание

Теперь можно (и нужно) поработать самим — предлагаю несколько вариантов самостоятельной работы:

  1. Реализовать двунаправленный список — можно двигаться не только от головы к хвосту, но и от хвоста к голове. Это позволит ускорить выполнение функции get. В качестве подсказки — теперь класс ObjectBox должен иметь не только поле next, но и поле prev, которое должно указывать на предыдущий элемент в списке
  2. Реализовать не очередь, а стек — LIFO — Last In First Out (последний пришел, первый ушел). Что-то вроде нанизывания колец на столб — можно снять только последнее
  3. Реализовать раздел Визуализация робота с помощью нашей очереди
  4. Реализовать очередь с приоритетами — при добавлении элемента вы можете указать его приоритетность (от 1 до 10). В этом случае вам надо вставить элемент не в самый конец, а после элемента с таким же приоритетом (или с большим — если элементов с таким же приоритетом нет)

Удачи.

И теперь нас ждет следующая статья: Массивы — знакомство.