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

В этой части я хочу предложить пример, который позволит нам посмотреть как можно организовать взаимодействие объектов для реализации достаточно распространенной структуры данных — очереди. Т.е. я хочу создать класс, который позволит мне «складывать» туда объекты в заранее неизвестном количестве и «вынимать» объекты из этой очереди. Такая функциональность часто называется 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). В этом случае вам надо вставить элемент не в самый конец, а после элемента с таким же приоритетом (или с большим — если элементов с таким же приоритетом нет)

Удачи.

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

  • Алекс  says:

    Уважаемый автор, мне также почему-то тяжело въехать в реализацию механизма «//Перемещаем «голову» на следующий элемент».
    Насколько я понимаю, в данном участке кода метода pull() два указанных метода выполняются одним и тем же объектом класса ObjectBox (например, объектом ob1).
    // Получаем наш объект из вспомогательного класса из «головы»
    Object obj = head.getObject();
    // Перемещаем «голову» на следующий элемент
    head = head.getNext();
    // Если это был единственный элемент, то head станет равен null
    // и тогда tail (хвост) тоже дожен указать на null.
    Но тогда каким образом указатель head перемещается на следующий объект (например, ob2)? Это связано со спецификой хранения и обработки данных в памяти (типа после выполнения метода head.getObject() этот объект стирается?) или может быть next это какой-то оператор?
    И могли бы Вы прояснить еще один вопрос: каким образом заполняется поле next для первого объекта класса ObjectBox в методе push()(если объектов больше одного), когда участок кода
    else {
    // Если это не первый элемент, то надо, чтобы последний элемент в очереди
    // указывал на вновь прибывший элемент
    tail.setNext(ob);
    }
    для первого объекта не выполняется, т.к. правдиво условие if (head == null) ?

    • admin  says:

      По вопросу: «Но тогда каким образом указатель head перемещается на следующий объект»
      Так вот же код:
      head = head.getNext();
      Голова теперь «переехала» на следующий элемент. А бывший головной элемент теперь уже недоступен — он находится только в переменной obj, которую мы и отдаем.

      По вопросу: «каким образом заполняется поле next для первого объекта класса ObjectBox в методе push()»
      Она равна null — если элемент первый и единственный — значит за ним никого нет. И это обозначается null. И tail тогда указывает на тот же элемент, что и head. Когда же мы добавляем еще один элемент (их становится больше одного), тогда tail будет сдвигаться к последнему пришедшему элементу — это решается кодом:
      tail.setNext(obj); // Теперь последний элемент будет указывать на вновь пришедший и он станет не последним, последним будет вновь прибывший элемент.
      tail = obj; // И теперь и tail указывает на последний элемент (который только что пришел)

      А head никуда не сдвигается — он так и указывает на первый элемент.

      Таким образом получаем — head всегда указывает на первый элемент, а tail — на последний.

    • Артем  says:

      По вопросу: «каким образом заполняется поле next для первого объекта класса ObjectBox в методе push()» как и сказал уважаемый admin поле next равно null — если элемент первый и единственный, кроме того ссылки head и tail указывют на один и тот же объект — ob. При дальнейшем добавлении объектов в очередь происходит создание нового объекта, ob(но это уже не тот объект ob, который создавался для первого элемента, мысленно назовем его ob1), идет запись в него новой строки, а затем после выполнения tail.setNext(ob); этот новый объект ob1 записывается в поле next объекта ob на который ссылается как tail так и head. Следующей строкой tail = ob; ссылка tail обновляется (в ней теперь находится только ob1). По ссылке head имеем теперь первый объект ob в поле next которого находится новый объект ob1. При дальнейшем добавлении объектов в очередь создается новый объект ob2 с новой строкой, после выполнения tail.setNext(ob); идет его запись в поле next объекта ob1, а затем ссылка tail снова обновляется и указывает лишь на последний объект ob2. Таким образом по ссылке head теперь находится первый объект ob в поле next которого находится новый объект ob1 в поле next которого находится ob2. При дальнейшем добавлении объектов в очередь по ссылке head будут доступны все элементы очереди объектов (как матрешки), а tail всегда будет указывать на последний. Прошу прощения за сумбурное изложение, пытался объяснить как сам понял.

  • Ilya  says:

    Спасибо автору за очередную прекрасную статью.
    Есть 1 пожелание. Вы можете выложить правильный текст классов для «вариантов для самостоятельной работы»? Чтобы мы смогли проверить себя/найти ошибку или на худой конец, если ничего не получается, то прочитать, запомнить и осознать и эти варианты.

  • Артем  says:

    tail.setNext(ob); /* Можно ли сказать, что в этой строке в поле next объекта tail идет запись объекта ob? Или tail здесь не объект, а переменная типа
    ObjectBox? */

  • Артем  says:

    Мой вариант решения первой задачи(двунаправленный список). Основная сложность заключалась в строчке ob.setPrev(tail); метода push().

    public void push(Object obj){
    ObjectBox ob = new ObjectBox();
    ob.setObject(obj);

    if(head==null)
    {
    head = ob;
    }
    else
    {
    tail.setNext(ob);
    }

    ob.setPrev(tail);
    tail=ob;

    size++;

    }
    public Object getIndex(int index){

    if(size==0||size<=index||index<0)
    return null;

    if(index<size/2)
    {
    ObjectBox current = head;
    int pos = 0;
    while(posindex)
    {
    current = current.getPrev();
    pos—;
    }
    Object obj = current.getObject();
    return obj;
    }
    }

  • Артем  says:

    Почему то весь код не скопировался((

    • admin  says:

      Заключайте весь код в тэг <pre> … </pre>

  • Артем  says:

  • Артем  says:

    Все равно метод getIndex скопировался не полностью, даю его в отдельном сообщении:

  • Артем  says:

    Все равно не копирует!!

    • admin  says:

      А что не видно ?

  • Артем  says:

    Не видно конца условия if и начала второго условия else. Попробую дать по частям, и попрошу убрать не удавшиеся коментарии.

  • Артем  says:

  • Артем  says:

  • Артем  says:

    По частям получилось!

  • Артем  says:

    По второму заданию — «Реализовать не очередь, а стек — LIFO — Last In First Out (последний пришел, первый ушел)». Если получилось сделать первое, то второе — «the peace of cake»))

  • Артем  says:

    В смысле piece конечно))))

    • admin  says:

      Лучше такого рода вопросы на почту отправлять — комментировать код здесь достаточно неудобно.

  • Nibbler  says:

    Прошу прощения, но я никак не могу осознать конструкцию:

    Как я понял — tail — переменная с типом ObjectBox, которая, по идее, должна бы ссылаться на новый объект класса ObjectBox, если бы мы его создали: ObjectBox tail = new ObjectBox(). Каким образом мы применяем к этой переменной, которая инициализирована null-ом в самом начале, метод без создания объекта? Затем, методу отдаем только что созданный объект ObjectBox.
    До этого в курсе я подобных «фишек» не видел. Или, может быть, я где-то что-то по невнимательности пропустил… 🙁

  • Nibbler  says:

    Предыдущий вопрос снимаю. Осознал, пока ехал в электричке — к тому времени, когда мы вызываем метод setNext переменная tail уже содержит указатель на объект. Это — предыдущий объект ob, переданный ей присвоением tail = ob; которое я поначалу не заметил.

  • Nibbler  says:

    Следуя подсказке (спасибо!), в класс ObjectBox добавил новую переменную private ObjectBox prev, и соответственно — геттер и сеттер для нее. Сложнее всего было сцепить «вагончики» второй сцепкой 🙂 В методе push добавил строчку:

    Дальше — все, вроде бы, просто — от противного. В классе ObjectQueue появился дополнительный метод, с помощью которого реализуется выборка «с хвоста»:

    Метод get разбил по условию if(index < size/2) на 2 половинки: Если true — то поиск нужного индекса идет с головы, если false — с хвоста.
    Спасибо за это занятие — очень "сдвигает парадигму".
    Можно вопрос?
    Насколько я себе это могу представить, в каждый отдельный момент времени существует только одна ссылка по которой мы сослаться на конкретный объект, в зависимости от состояния, куда мы ее сдвинули. Тем не менее, остальные 9 объектов (в нашем случае их 10 всего), никуда не исчезают и размещены по зарезервированным для них ранее адресам памяти. Может ли случиться такое, что какие-то из этих объектов будут удалены garbage-коллектором, если к ним долгое время не будет обращений? Допустим мы выбираем всегда элементы перед 5-м или после 5-го (с головы или с хвоста) — в результате этого перебора указатель ни разу не попадает на 5 элемент — программа его "не дергает" и он спокойно может исчезнуть.

    • admin  says:

      Если на объект есть хоть одна ссылка, то он не удаляется. В нашем случае эти ссылки есть в нашем списке. Так что не удаляется.

  • Nibbler  says:

    Отрисовка перемещений робота с помощью очереди: Изменения в 2-х классах.
    Robot.java: 1) вместо ArrayList создаем объект — очередь 2) в методе forward проталкиваем новую линию в очередь: queue.push(…) 3) добавляем геттер getQueue()
    RobotPathComponent.java: 1) получаем очередь из робота ObjectQueue oq = robot.getQueue(); 2) в цикле «тянем» линии из очереди: RobotLine rl = (RobotLine)oq.pull();
    По субъективным ощущениям рисует быстрее, чем раньше (с реализацией в виде списка).

    • admin  says:

      Ощущения не самый лучший способ определить скорость — для измерения производительности надо использовать специальный софт.

  • Firefly  says:

    Добрый день! Изложение и задания доступны и понятны! Спасибо!
    Вопросик у меня: если мы приписываем классу ObjectBox модификатор private , то не возникнет ли ошибка доступа к нему из класса ObjectQueue?

    • admin  says:

      Код работает — значит класс доступен. Но только в классе ObjectQueue. Можете проверить.

      • Firefly  says:

        Наверно дошло: класс ObjectBox является внутренним для класса ObjectQueue?
        Не помню, говорилось ли о таком варианте в ваших уроках, или где-то когда-то уже успела почитать и почти забыть… Я эти классы устраивала в разных файлах!

  • Сергей  says:

    Опечатка в фразе «При добавлении новjго элемента нам надо создать такую структуру»

    • admin  says:

      Спасибо, исправил

  • Сергей  says:

    Антон, а есть ли практический смысл для экономии системных ресурсов (например для систем с большим количеством пользователей) не ждать, когда «чистильщик» уберет объекты, на которые никто не ссылается поле отработки метода pull(), а в программном коде прописывать «обнуление» объектов очереди командой типа =null ?

    • admin  says:

      В том виде, который предлагается — это бессмысленно. Память под объект все равно выделена в куче и ее все равно будет чистить GC. В чем тогда смысл присваивания null ?
      Можно вызывать GC самому, но это как раз будет невыгодно — GC требует ресурсов. Настройка работы самого GC — то достаточно деликатная и кропотливая работа.

  • Антон  says:

    Мне пока что в корне не понятна конструкция Object object.
    Это что значит? Мы вызываем класс Object (как вы упомянули, являющийся прородителем для всех), называем это типом переменной и далее имя переменной object. В результате получается поле, которое может принять абсолютно любые значения? Зачем вообще это делать?

    • admin  says:

      Чтобы принять объект ЛЮБОГО класса. Потому как все классы в конечном итоге наследники класса Object. Значит эта ссылка становится по сути универсальным указателем — она может указывать на любой объект. Что нам и нужно.

  • Антонио  says:

    Здравствуйте, опишите пожалуйста немного подробнее суть третьего задания, если не трудно!)

    • admin  says:

      Мы сделали хранение списка точек движения робота с помощью стандартного компонента. Я предлагаю сделать это с помощью нашего самописного.

  • Антонио  says:

    А так вообще круто, с Вашими лекциями за 3 недели уже до этого места дошёл, метод спирали очень действенный)

    • admin  says:

      Спасибо.

  • Антонио  says:

    public void push(Object obj, int a) {
    ObjectBox ob = new ObjectBox();

    ob.setPrioritet(a);
    ob.setObject(obj);

    if (head == null) {
    head = ob;
    tail=ob;
    }
    else {
    for (int i=0;i<size;i++){
    if(ob.getPrioritet()<=tail.getPrioritet()){
    tail.setNext(ob);
    ob.setPrev(tail);
    tail=ob;
    break;
    }
    else {
    ObjectBox b= tail.getPrev();
    b.setNext(ob);
    ob.setPrev(b);
    ob.setNext(tail);
    tail.setPrev(ob);

    }
    }

    }

    size++;

    }

  • Антонио  says:

    Помогите пожалуйста, сижу над последнием заданием этой темы уже несколько дней, ругается начиная со строки b.setNext(ob). По-другому не могу придумать, как всунуть в очередь элемент с большим приоритетом перед существующим

  • Антонио  says:

    В компиляторе
    Exception in thread «main» java.lang.NullPointerException
    at edu.javacourse.queue.ObjectQueue.push(ObjectQueue.java:51)
    at edu.javacourse.queue.TestQueue.main(TestQueue.java:22)
    Java Result: 1
    СБОРКА УСПЕШНО ЗАВЕР

  • Антонио  says:

    а как вы переносите красивый код в коменты?

    • admin  says:

      Если нужна помощь с кодом, то лучше присылать на почту — course@java-course.ru

  • Антонио  says:

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

    • admin  says:

      Я пока не в состоянии ответить — наберитесь терпения.

  • v  says:

    зачем делать жесткую привязку к строке?

  • v  says:

    по своей сути метод size() с возвратом является геттером getSize().

  • Юрий  says:

    Я не постесняюсь и задам самый глупый вопрос. Что нужно сделать в этом задании?)
    Хотя бы первый пункт можно разъяснить, что надо сделать?
    Второй день сижу медитирую на этот код. Все что я вижу, это то, что в консоли выдается вот такой результат:
    Строка: 0
    Размер очереди: 9
    Строка: 1
    Размер очереди: 8
    Строка: 2
    Размер очереди: 7
    Строка: 3
    Размер очереди: 6
    Строка: 4
    Размер очереди: 5
    Строка: 5
    Размер очереди: 4
    Строка: 6
    Размер очереди: 3
    Строка: 7
    Размер очереди: 2
    Строка: 8
    Размер очереди: 1
    Строка: 9
    Размер очереди: 0

    надо сделать, чтобы цифры не с нуля до девяти а с девяти до нуля, так что ли?
    Так это делается просто вот в этой строчке for (int i = 0 ; i < 10; i++)
    Для чего такой огород нагородили из разных классов?
    Может быть действительно пора бы уже выложить правильный код с ответом? А то реально вообще не понятно что надо сделать. Я наверное самый тупой ученик здесь)

    • admin  says:

      Вы не могли бы более точно сформулировать — а что Вы делаете (пытаетесь сделать) ?
      Кода нет, постановки задачи нет — я не экстрасенс, чтобы догадываться, что за задачу Вы решаете и почему она у Вас не получается 🙂

  • Юрий  says:

    Я пытаюсь понять что нужно сделать в первом задании:) Я более-менее разобрался, как работает та программа, что дана в примере. Но что требуется вот здесь я не могу понять:
    «Домашнее задание
    Теперь можно (и нужно) поработать самим — предлагаю несколько вариантов самостоятельной работы:

    Реализовать двунаправленный список — можно двигаться не только от головы к хвосту, но и от хвоста к голове. Это позволит ускорить выполнение функции get. В качестве подсказки — теперь класс ObjectBox должен иметь не только поле next, но и поле prev, которое должно указывать на предыдущий элемент в списке
    »

    Что значит двунаправленный список? Как мне понять, что я реализовал эту задачу? Что я должен увидеть на выходе в консоли?

    Заранее спасибо

    • admin  says:

      В статье вы можете двигаться только в одну сторону — от первого элемента ко второму, от второго — к третьему и т.д. Вы не можете двигаться от конца к началу — только от начала к концу. Это однонаправленный список — список в одном направлении. Т.е. для вывода последнего элемента надо пройти от начала и до самого конца. При количестве элементов 1 млн. — это долго.
      А что увидеть на экране — это уже решайте сами. Или Вы предлагаете мне заниматься Вашим обучением в индивидуальном порядке ? 🙂

  • Сергей  says:

    Юрий, надо добавить поле «private ObjectBox prev» классу ObjectBox и реализовать метод push таким образом, чтобы при добавлении экземпляра в очередь, ссылка next предыдущего экземпляра указывала на вновь добавленный, и ссылка prev у вновь добавленного указывала на предыдущий.

    Затем, лично я, изменил метод get в классе ObjectQueue так, чтобы в случае, когда мы передаем методу index больше, size / 2 (то есть нам нужен элемент со второй половины ArrayList), то поиск элемента начинается с конца

    Не претендую на правильность и уж тем более качество кода, так как сам три недели, как начал изучать джаву. Но я сделал это задание вот таким вот способом.

  • Сергей  says:

    Почему-то неправильно вставился код метода get. Попробую еще раз

  • Сергей  says:

    Просьба к админу — удалить код метода get из первого моего сообщения и из второго. Почему-то они криво вставляются. То ли по длине сообщения не проходит, то ли еще какие-то проблемы.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.