Queue

У многих людей слово “очередь” вызывает очень мало приятных ассоциаций. Но сегодня мы говорим о других очередях — в Java. Очередью в Java считается все, что наследует интерфейс Queue, который в свою очередь расширяет Collection. Это значит, что с очередями можно работать, как с коллекциями.

Очереди в Java работают по двум принципам: FIFO и LIFO.

FIFO — First In First Out, принцип обычной очереди (конечно, если нет тех кому нужно “только спросить”), в котором первый элемент попадает в очередь и первым выходит из нее.

LIFO — Last In First Out, принцип стека, в котором последний элемент, добавленный в очередь, первым выйдет из нее. Например, как с колодой карт: ты будешь брать все карты с верха по одной, чтобы дойти до конца.

Иерархия Queue в Java выглядит следующим образом:

Здесь видно, что у Queue есть 3 класса реализации: LinkedList, ArrayDeque и PriorityQueue. LinkedList и ArrayDeque наследует напрямую не от Queue, а от Deque.

Deque — это интерфейс, который добавили в 6 версии Java. Он включает в себя ряд полезных для очередей методов и дает возможность очереди функционировать как двунаправленная очередь. То есть работать по принципу FIFO или LIFO.

Одним из двух наследников Deque является ArrayDeque. Он поддерживает двустороннюю структуру данных очереди, что дает возможность вставлять и удалять элементы с обеих сторон. Также он — динамический массив, который может автоматически увеличивать свой размер.

Есть еще класс PriorityQueue, прямой наследник Queue: принцип его работы отличается от наследников Dequeue.

PriorityQueue — это очередь с приоритетом, которая по умолчанию размещает элементы согласно естественному порядку сортировки. Для сортировки здесь используется Comparable и Comparator. Принцип здесь такой же, как и с TreeSet или TreeMap — классов, которые следуют интерфейсу Comparable и имеют свой порядок сортировки.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Запустив этот пример в консоли, ты получишь:

Так как мы работаем с очередями, а не обычными коллекциями, мы должны удалить элемент из списка. Используем эту конструкцию:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Интерфейс Deque наследует методы Queue и добавляет ряд своих интересных методов:

Давай теперь рассмотрим несколько из них на практике.

Добавим сначала элемент в очередь:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Добавляет элемент Apple в конец очереди
        deque.addFirst("Orange"); // Добавляет элемент Orange в начало очереди
        deque.addLast("Pineapple"); // Добавляет элемент Pineapple в конец очереди
  
        System.out.println(deque);
    

Теперь получим значения с очереди:

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The First element is: "+ deque.getFirst());
                          
        System.out.println("The Last element is: " + deque.getLast());
                          
    }
    

Этот код выведет в консоли первый и последний элемент очереди.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // вытащит и удалит верхний элемент очереди
System.out.println(deque.poll()); // вытащит и удалит верхний элемент очереди

System.out.println(deque);
    

Запустив этот код, получим:

Разница между методами pop() и poll() в том, что pop() вызовет исключение NoSuchElementException при пустом списке, а poll() вернет null.

Теперь рассмотрим методы pollFirst() и pollLast().

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // вытащит и удалит первый элемент очереди
System.out.println(deque.pollLast()); // вытащит и удалит последний элемент очереди.
System.out.println(deque);
    

Оба метода возвращают и удаляют значение из очереди.

Пример использования методов peekFirst() и peekLast():

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Оба метода возвращают первый/последний элемент из очереди и не удаляют их. В случае, если очередь пуста, будет возвращено null.

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

19

Задача

Java Syntax Pro, 19 уровень, 1 лекция

Недоступна

Две реализации одного интерфейса

В интерфейсе Runnable объявлен метод run() и есть две его реализации: в классе Car и в классе Plane. В классе Solution есть публичное статическое поле ArrayList<Runnable> list, а также два публичных статических метода: addToList(Runnable), который добавляет в список list элемент, полученный в качест

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 1 лекция

Недоступна

Сортировка по возрасту

В классе Solution есть статическое поле students, которое заполняется студентами (объектами типа Student) в методе main(). У студента (класс Student) есть имя (поле name) и возраст (поле age). Нужно отсортировать в программе студентов по возрасту в убывающем порядке (от старшего к младшему). Для это

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 1 лекция

Недоступна

Наставники JavaRush

В классе Solution есть статическое поле mentors, которое заполняется менторами JavaRush (объектами типа JavaRushMentor) в методе main(). У ментора (класс JavaRushMentor) есть имя (поле name). В программе нужно отсортировать менторов по длине имени в возрастающем порядке (от самого короткого до самог

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 1 лекция

Недоступна

Знакомство с лямбда-выражением

Перед тобой программа, которая сортирует список чисел по возрастанию. Метод sortNumbers(ArrayList<Integer>) принимает список, элементы которого необходимо отсортировать. Для сортировки используется метод Collections.sort(ArrayList<Integer>, Comparator<Integer>), параметрами которого являются список

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 1 лекция

Недоступна

Прощание с лямбда-выражением

Перед тобой программа, которая сортирует список строк по их длине по возрастанию. Это делает метод sortStringsByLength(ArrayList<String>). Для сортировки строк используется метод Collections.sort(ArrayList<String>, Comparator<String>), который принимает список строк и компаратор в виде лямбда-выраже

Открыть