Перейти к содержимому

Welcome to La2base.ru
Register now to gain access to all of our features. Once registered and logged in, you will be able to create topics, post replies to existing threads, give reputation to your fellow members, get your own private messenger, post status updates, manage your profile and so much more. If you already have an account, login here - otherwise create an account for free today!

Информация

  • Добавлена: окт 31 2016 01:05
  • Просмотров: 486
 


* * * * *
0 Рейтинг

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

Написано alexiali окт 31 2016 01:05
очередь объектов java
9c2562fe2106.jpg
 
 
 
Пример — очередь объектов
 
В этой части я хочу предложить пример, который позволит нам посмотреть как можно организовать взаимодействие объектов для реализации
 
достаточно распространенной структуры данных — очереди. Т.е. я хочу создать класс, который позволит мне «складывать» туда объекты в
 
заранее неизвестном количестве и «вынимать» объекты из этой очереди. Такая функциональность часто называется FIFO — First In First Out —
 
первый пришел, первый ушел. По сути наш класс должен иметь три метода:
 
 
1. Положить объект (произвольного класса) в очередь — назовем метод push
 
2. Вытащить объект (произвольного класса) из очереди — назовем метод pull
 
3. Получить количество объектов в очереди — назовем его size
 
 
Итак, наш класс ObjectQueue будет выглядеть (без реализации, только с методами) вот так:
 

public class ObjectQueue
{
    public void push(Object obj) {
        // Пока реализации нет
    }

    public Object pull() {
        // Пока реализации нет
    }

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

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 и потом выбираем все объекты до тех пор,
 
пока размер очереди не станет нулевым. Обратите внимание на то, что мы делаем приведение типа объекта при его получении. Когда мы
 
начнем говорить о коллекциях, мы об этом вспомним.
 
 
   Теперь давайте подумаем над реализацией нашей очереди. Большинство книг по структурам данных содержит такое понятие как связный
 
список. Если быть точнее — однонаправленный связный список. Сама идея списка достаточно простая — ее можно посмотреть на рисунке.
 
e90a855ea5ec.jpg
 

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

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-й — то эта операция будет исполняться долго для
 
больших списков. Но вернемся к задаче — как обычно, я предлагаю сразу смотреть код и комментарии к нему.
 

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;
        }
    }
}

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

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

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.
 
 
Домашнее задание 
 
   Теперь можно (и нужно) поработать самим — предлагаю несколько вариантов самостоятельной работы:
 
1. Реализовать двунаправленный список — можно двигаться не только от головы к хвосту, но и от хвоста к голове. Это позволит
 
ускорить выполнение функции get. В качестве подсказки — теперь класс ObjectBox должен иметь не только поле next, но и поле prev,
 
которое должно указывать на предыдущий элемент в списке
 
 
 
2. Реализовать не очередь, а стек — LIFO — Last In First Out (последний пришел, первый ушел). Что-то вроде нанизывания колец на
 
столб — можно снять только последнее
 
 
 
3. Реализовать раздел Визуализация робота с помощью нашей очереди
 
 
4. Реализовать очередь с приоритетами — при добавлении элемента вы можете указать его приоритетность (от 1 до 10). В этом случае
 
вам надо вставить элемент не в самый конец, а после элемента с таким же приоритетом (или с большим — если элементов с таким же
 
приоритетом нет)
 
 
 
Удачи.
 
 
Источник: java-course.ru
 
 
Всем хорошего настроения! : )

 

0 Комментариев
или Войти


Powered by Tutorials 1.5.0 © 2017, by Michael McCune