Queue в Java

2 июня, 201818 июля, 2018 Vertex Academy queue java пример,коллекция queue java,очередь java

Данная статья:

написана командой Vertex Academy.
это одна из статей из нашего "Самоучителя по Java"

Привет! В нашем самоучителе мы рассматриваем следующие коллекции:

Список (List) - см. статью "List в Java", а также статью "Что такое ArrayList"
Множество (Set) - см. статью "Set в Java"
Очередь (Queue)

Это статья про структуру данных очередь (Queue) - один из способов хранения данных в Java.

Что такое очередь (Queue) в Java

Очередь - это очень интересный тип хранения данных. Мы можем проводить с ней ограниченное количество операций - обычно только с верхним элементом, и не имеем доступа к "середине" очереди.

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

Во-первых... Очередь!

В идеале, мы не можем встать в середину очереди - только в конец. А тот, кто приходит первым, первый получает мороженное 🙂 Или справку. Или что там еще. Точно так же работает и Queue. Мы не можем ничего вставить в середину очереди - только в конец.
Тем не менее, убирать элемент можно и из середины очереди - так, например, человек в любой момент может махнуть рукой и сказать: "А, я уже три часа тут стою - пойду домой!"
Более того, элемент не всегда может влезть в очередь (в смысле в Queue). Например, не сталкивались с тем, что доходит очередь до Вас - и как раз начинается обед? 🙁 Или касса закрывается?

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

Какие есть виды очередей (Queue)

Для начала Вам хватит знания одного типа - PriorityQueue.

Что интересного в PriorityQueue? Дело в том, что элементы в ней располагаются не только по порядку, но и по приоритету. Этот приоритет можно задавать самостоятельно, но для начинающих это может быть пока немного сложная тема. Пока Вам стоит знать, что если создавать очередь из стандартных типов данных (Integer, Float, String), у нее будет стандартный приоритет:

для чисел по возрастанию
для строк по алфавиту

FIFO и LIFO в Java

Кстати, "принцип очереди" - то, что первый, кто пришел, первым получает мороженое - обозначается английской аббревиатурой FIFO ("First in first out"). Переводится как "первый пришел первый вышел". Кроме очереди можно привести пример с конвейером - то, что ты положил раньше на конвейерную ленту, первым станет готовым продуктом и поедет в магазин.

Также в Java есть структуры, которые работают чуть-чуть по-другому. В таких структурах тот элемент, который поступил первым, первым вынимается. Можно провести аналогию со стопкой тарелок - та тарелка, которую ты поставил первой, оказывается в самом низу. Очень неудобно доставать, правда?

Поэтому мы моем тарелки, начиная с самой верхней - т.е. той, которую мы поставили последней. Этот принцип называется LIFO ("Last in first out", "последний пришел первый вышел"). По такому принципу работает еще одна структура данных, очень похожая на очередь - стэк. Тот что overflow 🙂 Но это так, на будущее.

Операции с Queue

1. add() - добавляет элемент в конец очереди.

Поправка: если очередь с приоритетом - т.е. PriorityQueue - элемент ставится не обязательно в конец, а в соответствии со своим приоритетом

2. remove() и poll() - удаляет верхний элемент из очереди.

3. offer() - пытается вставить элемент в конец очереди.

4. peek() и element() - показывают верхний элемент очереди

Пример 1

add() - добавляем элемент в конец очереди. (Поправка: если очередь с приоритетом - т.е. PriorityQueue - элемент ставится не обязательно в конец, а в соответствии со своим приоритетом):

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);
        for(int pq : myPriorityQueue) {
            System.out.println(pq);
        }
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

for(int pq : myPriorityQueue) {

System.out.println(pq);

}

Тут мы добавили три Integer-а: 1, 2 и 3. Потом мы вывели нашу очередь в консоль - получили:

Пример 2

remove() и poll() - удаляем верхний элемент из очереди. Так сказать, "Три часа жду - надоело, иду домой!" 🙂

Но в чем между ними разница?

У метода remove() есть две формы - remove() и remove(Object o), а у poll() - только одна. В первой форме оба метода одинаковые - они убирают "голову" (первый элемент) очереди. Обезглавливают так сказать 🙂

Например, тут мы используем метод remove():

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);

        for(int i: myPriorityQueue)
            System.out.println(i);
        myPriorityQueue.remove();
        System.out.println("After removing:");
        for(int i: myPriorityQueue)
            System.out.println(i);
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

for(int i: myPriorityQueue)

System.out.println(i);

myPriorityQueue.remove();

System.out.println("After removing:");

for(int i: myPriorityQueue)

System.out.println(i);

}

Получаем:

Точно то же самое получим, если напишем вместо remove() poll():

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);

        for(int i: myPriorityQueue)
            System.out.println(i);
        myPriorityQueue.poll();
        System.out.println("After removing:");
        for(int i: myPriorityQueue)
            System.out.println(i);
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

for(int i: myPriorityQueue)

System.out.println(i);

myPriorityQueue.poll();

System.out.println("After removing:");

for(int i: myPriorityQueue)

System.out.println(i);

}

Но remove(Object o) позволяет убирать любой элемент, не только сверху. Например, попробуем убрать двойку - она лежит в середине очереди:

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);

        for(int i: myPriorityQueue)
            System.out.println(i);
        myPriorityQueue.remove(2);
        System.out.println("After removing:");
        for(int i: myPriorityQueue)
            System.out.println(i);
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

for(int i: myPriorityQueue)

System.out.println(i);

myPriorityQueue.remove(2);

System.out.println("After removing:");

for(int i: myPriorityQueue)

System.out.println(i);

}

Получаем:

Как видите, двойки нет 🙂

Методы будут действовать по-разному если у нас пустая очередь. Например:

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.remove();
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.remove();

}

Если мы попытаемся вызвать метод remove() на пустом листе, получим Exception:

Если poll() - ничего не произойдет:

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.poll();
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.poll();

}

Получаем:

Вывод:

хотите Exception (т.е. если пустая очередь - недопустимое состояние) - берите remove()
Если нет - берите poll()

Пример 3

offer() - пытается вставить в конец очереди. С английского "offer" переводится как "предложить". Почему "предлагаем"? Потому что в очередях с фиксированным размером у нас может не получится вставить элемент в очередь. Давайте попробуем его использовать:

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);
        myPriorityQueue.offer(22);

        for(int i: myPriorityQueue)
            System.out.println(i);
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

myPriorityQueue.offer(22);

for(int i: myPriorityQueue)

System.out.println(i);

}

Получаем:

Ура! Предложение принято 🙂

Пример 4

peek() (от англ. "подсматривать"), и element() - показывают верхний элемент очереди. Например:

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);

        System.out.println(myPriorityQueue.peek());
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

System.out.println(myPriorityQueue.peek());

}

Получаем:

Все верно, мы получили первый элемент - единицу.

Или, давайте попробуем применить element():

public class Test {

    public static void main(String[] args) {

        PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

        myPriorityQueue.add(1);
        myPriorityQueue.add(2);
        myPriorityQueue.add(3);

        System.out.println(myPriorityQueue.element());
    }
}

public class Test {

public static void main(String[] args) {

PriorityQueue<Integer> myPriorityQueue = new PriorityQueue<Integer>();

myPriorityQueue.add(1);

myPriorityQueue.add(2);

myPriorityQueue.add(3);

System.out.println(myPriorityQueue.element());

}

Получаем то же самое - единицу:

Поздравляем - теперь Вы знаете, что такое очередь и как ей пользоваться! Увидимся в следующих уроках 😉

Надеемся, что наша статья была Вам полезна. Можно записаться к нам на курсы по Java на сайте.