Пример — очередь объектов
В этой части я хочу предложить пример, который позволит нам посмотреть как можно организовать взаимодействие объектов для реализации достаточно распространенной структуры данных — очереди. Т.е. я хочу создать класс, который позволит мне «складывать» туда объекты в заранее неизвестном количестве и «вынимать» объекты из этой очереди. Такая функциональность часто называется FIFO — First In First Out — первый пришел, первый ушел. По сути наш класс должен иметь три метода:
- Положить объект (произвольного класса) в очередь — назовем метод push
- Вытащить объект (произвольного класса) из очереди — назовем метод pull
- Получить количество объектов в очереди — назовем его size
Итак, наш класс ObjectQueue будет выглядеть (без реализации, только с методами) вот так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class ObjectQueue { public void push(Object obj) { // Пока реализации нет } public Object pull() { // Пока реализации нет } public int size() { // Пока реализации нет } } |
Как видите, мы может положить в очередь объект типа Object, что означает, что мы можем положить туда все, что угодно — как вы должны помнить, класс Object является «проматерью» всех классов — все классы наследуются в конечном итоге от него (если не прямо от него, то он будет их дедушкой, прадедушкой и т.д.).
Предлагаю сразу написать маленький класс для тестирования нашей очереди
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class QueueTest { public static void main(String[] arg) { ObjectQueue queue = new ObjectQueue(); for(int i=0; i<10; i++) { // В данном случае мы складываем в очередь строки queue.push("Строка:" + i); } while(queue.size() > 0) { // Мы делаем жесткое приведение типа, т.к. знаем, что там лежат строки String s = (String)queue.pull(); System.out.println(s); System.out.println("Размер очереди:" + queue.size()); } } } |
Можно видеть, что сначала мы помещаем в очередь объект класса String (первый цикл от 0 до 10 и потом выбираем все объекты до тех пор, пока размер очереди не станет нулевым. Обратите внимание на то, что мы делаем приведение типа объекта при его получении. Когда мы начнем говорить о коллекциях, мы об этом вспомним.
Теперь давайте подумаем над реализацией нашей очереди. Большинство книг по структурам данных содержит такое понятие как связный список. Если быть точнее — однонаправленный связный список. Сама идея списка достаточно простая — ее можно посмотреть на рисунке.
Как видите, все достаточно несложно. У нас есть структура, которая содержит два элемента:
- Хранилище для данных
- Указатель на следующий элемент
При добавлении нового элемента нам надо создать такую структуру (по сути это объект с двумя полями), поместить в хранилище данных переданный объект и указатель у последнего элемента в списке «указать» на добавляемый объект. Мы как бы «прикрепляем» новый объект к существующей цепочке объектов. Однонаправленная очередь потому, что двигаться по ней можно только в одном направлении — от «головы» к «хвосту».
Как мы только что говорили, нам потребуется вспомогательный объект — назовем его OjectBox и т.к. он в общем-то никому не нужен, мы можем объявить его внутри нашего класса ObjectQueue. Смотрим:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
private class ObjectBox { private Object object; private ObjectBox next; public Object getObject() { return object; } public void setObject(Object object) { this.object = object; } public ObjectBox getNext() { return next; } public void setNext(ObjectBox next) { this.next = next; } } |
Как видите — все просто. В поле object мы будем помещать сам добавляемый объект, а поле next будет указывать на следующий элемент в цепочке.
Теперь поговорим о классе ObjectQueue. Ему необходимо иметь поле, которое указывает на самый первый элемент — нам же надо с чего-то начинать и брать элементы из очереди мы будем как раз с «головы». В принципе одного этого элемента достаточно, но это будет крайне не эффективно. Потому что при добавлении вам придется каждый раз пробегать от «головы» до «хвоста» и уже только после нахождения «хвоста» можно будет добавлять новый элемент. В качестве тренировки вы можете реализовать сами такой вариант. Но мы все-таки сделаем более корректно — введем еще одно поле, которое будет всегда указывать на «хвост» — на последний элемент в очереди. Наличие этого элемента позволяет создавать очень эффективную структуру с очень важной характеристикой — время добавления нового элемента не зависит от размера списка. Очередь может содержать 100 элементов или 100000 — время добавления будет всегда одинаковое. Но у такой структуры есть минус — если вы хотите найти элемент на определенной позиции — например 184-й — то эта операция будет исполняться долго для больших списков. Но вернемся к задаче — как обычно, я предлагаю сразу смотреть код и комментарии к нему.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
package edu.javacourse.queue; public class ObjectQueue { // Указатель на первый элемент private ObjectBox head = null; // Указатель на последний элемент private ObjectBox tail = null; // Поле для хранения размера очереди private int size = 0; public void push(Object obj) { // Сразу создаем вспомогательный объект и помещаем новый элемент в него ObjectBox ob = new ObjectBox(); ob.setObject(obj); // Если очередь пустая - в ней еще нет элементов if (head == null) { // Теперь наша голова указывает на наш первый элемент head = ob; } else { // Если это не первый элемент, то надо, чтобы последний элемент в очереди // указывал на вновь прибывший элемент tail.setNext(ob); } // И в любом случае нам надо наш "хвост" переместить на новый элемент // Если это первый элемент, то "голова" и "хвост" будут указывать на один и тот же элемент tail = ob; // Увеличиваем размер нашей очереди size++; } public Object pull() { // Если у нас нет элементов, то возвращаем null if (size == 0) { return null; } // Получаем наш объект из вспомогательного класса из "головы" Object obj = head.getObject(); // Перемещаем "голову" на следующий элемент head = head.getNext(); // Если это был единственный элемент, то head станет равен null // и тогда tail (хвост) тоже дожен указать на null. if (head == null) { tail = null; } // Уменьшаем размер очереди size--; // Возвращаем значение return obj; } public int size() { return size; } // Наш вспомогательный класс будет закрыт от посторонних глаз private class ObjectBox { // Поле для хранения объекта private Object object; // Поле для указания на следующий элемент в цепочке. // Если оно равно NULL - значит это последний элемент private ObjectBox next; public Object getObject() { return object; } public void setObject(Object object) { this.object = object; } public ObjectBox getNext() { return next; } public void setNext(ObjectBox next) { this.next = next; } } } |
Класс для тестирования нашей очереди
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
package edu.javacourse.queue; public class QueueTest { public static void main(String[] arg) { ObjectQueue queue = new ObjectQueue(); for(int i=0; i<10; i++) { // В данном случае мы складываем в очередь строки queue.push("Строка:" + i); } while(queue.size() > 0) { // Мы делаем жесткое приведение типа, т.к. знаем, что там лежат строки String s = (String)queue.pull(); System.out.println(s); System.out.println("Размер очереди:" + queue.size()); } } } |
Пример — очередь объектов. Добавляем функциональность
Теперь мы добавим удобную функцию — получение элемента по индексу (по номеру в очереди. Эта функция не будет удалять элемент из очереди — она просто вернет элемент. В этом коде мы увидим, что скорость исполнения здесь зависит от размера очереди — чем он больше, тем функция будет работать дольше. И как говорил герой из фильма «В бой идут одни старики» — «Серега, не надо слов». Смотрим код.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
package edu.javacourse.queue; public class ObjectQueue { // Указатель на первый элемент private ObjectBox head = null; // Указатель на последний элемент private ObjectBox tail = null; // Поле для хранения размера очереди private int size = 0; public void push(Object obj) { // Сразу создаем вспомогательный объект и помещаем новый элемент в него ObjectBox ob = new ObjectBox(); ob.setObject(obj); // Если очередь пустая - в ней еще нет элементов if (head == null) { // Теперь наша голова указывает на наш первый элемент head = ob; } else { // Если это не первый элемент, то надо, чтобы последний элемент в очереди // указывал на вновь прибывший элемент tail.setNext(ob); } // И в любом случае нам надо наш "хвост" переместить на новый элемент // Если это первый элемент, то "голова" и "хвост" будут указывать на один и тот же элемент tail = ob; // Увеличиваем размер нашей очереди size++; } public Object pull() { // Если у нас нет элементов, то возвращаем null if (size == 0) { return null; } // Получаем наш объект из вспомогательного класса из "головы" Object obj = head.getObject(); // Перемещаем "голову" на следующий элемент head = head.getNext(); // Если это был единственный элемент, то head станет равен null // и тогда tail (хвост) тоже дожен указать на null. if (head == null) { tail = null; } // Уменьшаем размер очереди size--; // Возвращаем значение return obj; } public Object get(int index) { // Если нет элементов или индекс больше размера или индекс меньше 0 if(size == 0 || index >= size || index < 0) { return null; } // Устанавлваем указатель, который будем перемещать на "голову" ObjectBox current = head; // В этом случае позиция равну 0 int pos = 0; // Пока позиция не достигла нужного индекса while(pos < index) { // Перемещаемся на следующий элемент current = current.getNext(); // И увеличиваем позицию pos++; } // Мы дошли до нужной позиции и теперь можем вернуть элемент Object obj = current.getObject(); return obj; } public int size() { return size; } // Наш вспомогательный класс будет закрыт от посторонних глаз private class ObjectBox { // Поле для хранения объекта private Object object; // Поле для указания на следующий элемент в цепочке. // Если оно равно NULL - значит это последний элемент private ObjectBox next; public Object getObject() { return object; } public void setObject(Object object) { this.object = object; } public ObjectBox getNext() { return next; } public void setNext(ObjectBox next) { this.next = next; } } } |
Полный код проекта можно скачать отсюда: ObjectQueue.zip.
Домашнее задание
Теперь можно (и нужно) поработать самим — предлагаю несколько вариантов самостоятельной работы:
- Реализовать двунаправленный список — можно двигаться не только от головы к хвосту, но и от хвоста к голове. Это позволит ускорить выполнение функции get. В качестве подсказки — теперь класс ObjectBox должен иметь не только поле next, но и поле prev, которое должно указывать на предыдущий элемент в списке
- Реализовать не очередь, а стек — LIFO — Last In First Out (последний пришел, первый ушел). Что-то вроде нанизывания колец на столб — можно снять только последнее
- Реализовать раздел Визуализация робота с помощью нашей очереди
- Реализовать очередь с приоритетами — при добавлении элемента вы можете указать его приоритетность (от 1 до 10). В этом случае вам надо вставить элемент не в самый конец, а после элемента с таким же приоритетом (или с большим — если элементов с таким же приоритетом нет)
Удачи.
И теперь нас ждет следующая статья: Массивы — знакомство.
