Шаг 75 - Интерфейсы Queue и Deque и их реализации

На этом шаге мы рассмотрим интерфейсы Queue и Deque

Queue - это интерфейс для работы с очередью. В данный интерфейс были добавлены следующие методы:

E element() - Функция для получения элемента из головы очереди. Если очередь пуста, то бросает исключение NoSuchElementException;
boolean offer(E e) - Функция аналогичная функции add(E e);
E peek() - Функция аналогичная функции element(). Разница лишь в том, что функция peek() не бросает исключение на пустой очереди. Вместо этого она возвращает значение null;
E poll() - Функция аналогичная функции peek(), при этом удаляет элемент из головы очереди, если она не пустая.

Интерфейс Deque наследуется от интерфейса Queue. В него добавлены множество новых функций. Ознакомиться с ними мы предлагаем самостоятельно, изучив документацию.

Класс PriorityQueue реализует интерфейс Queue. Данный класс представляет из себя очередь с приоритетами. Реализация данной очереди основана на структуре данных двоичная куча. Вставка и удаление элемента из такой очереди происходит быстро за O(log n), при этом удаляется всегда минимальный элемент. Для того чтобы задать правило сравнивания элементов очереди в конструктор данного класса передается компаратор. Компаратор - это объект, который задает порядок элементов в коллекции (подробнее про компаратор можно посмотреть здесь).

Класс ArrayDeque реализует интерфейс Deque. Данный класс реализован на массиве, поэтому он рекомендован для использования в качестве стека или очереди.

Приведем ниже примеры использования очереди и дека.

Пример 1. Пример использования класса PriorityQueue для сортировки списка алгоритмом пирамидальной сортировки. Про пирамидальную сортировку можно прочитать здесь

Файл примера

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

    /**
     * Количество элементов в списке
     * */
    private static final int MAX_COUNT_ELEMENTS = 20;

    /**
     * Функция для вывода элементов списка
     * @param list список
     * */
    private static <T> void printList(List<T> list) {
        for (T v : list) {
            System.out.print(" " + v);
        }
        System.out.println();
    }

    /**
     * Точка входа в программу
     * */
    public static void main(String[] args) {
        /*Конструируем список*/
        List<Integer> list = new ArrayList<>();

        /*
          Формируем список произвольными значениями из диапозона 
                                                       от 0 до MAX_COUNT_ELEMENTS - 1
        */
        for (int i = 0; i < MAX_COUNT_ELEMENTS; i++) {
            int x = (int) (Math.random() * MAX_COUNT_ELEMENTS);
            list.add(x);
        }

        /*Выводим значения элементов списка до сортировки*/
        System.out.print("Список до сортировки: ");
        printList(list);

        /*Сортируем список с помощью очериди с приоритетами*/
        Queue<Integer> prq = new PriorityQueue<>(list);
        for (int i = 0; i < MAX_COUNT_ELEMENTS; i++) {
            int min_value = prq.poll();
            list.set(i, min_value);
        }

        /*Выводим значения элементов списка после сортировки*/
        System.out.print("Список после сортировки: ");
        printList(list);
    }
}

Проект можно взять здесь

Рис. 1. Вывод программы

Пример 2. Пример использования класса ArrayDeque. Мы реализовали операцию сложения двух натуральных чисел сколь угодно большой длины с одним ограничением: числа должны быть одной длины.

Файл примера

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        /*Первое число*/
        String a = "0123456789";
        /*Второе число*/
        String b = "3745983475";

        /*Заводим дек*/
        Deque<Integer> q = new ArrayDeque<>();
        /*Переменная для запоминания разряда*/
        int ostatok = 0;
        /*Будем двигаться с конца чисел к началу*/
        for (int i = a.length() - 1; i >= 0; --i) {
            /*Запомним очередную цифру чисел*/
            int x = (int) a.charAt(i) - (int) '0';
            int y = (int) b.charAt(i) - (int) '0';

            /*Посчитаем соответствующий разряд результата*/
            int z = (x + y + ostatok) % 10;
            ostatok = (x + y + ostatok) / 10;

            /*Добавим разряд в дек*/
            q.add(z); /*Функция add добавляет элемент в конец дека*/
        }

        /*
         Если остаток (перенос на новый разряд) не равен 0, добавим этот остаток в дек
        */
        while (ostatok != 0) {
            q.add(ostatok % 10);
            ostatok /= 10;
        }

        /*Переменная - результат суммы двух чисел*/
        String ans = "";

        /*Пока дек не пустой*/
        while (!q.isEmpty()) {
            /*Мы возбмем последнюю цифру дека и удалим ее из него*/
            int x = q.pollLast();
            /*Добавим полученную цифру в конец результата*/
            ans += x;
        }
        System.out.println(a + " + " + b + " = " + ans);
    }
}

Проект можно взять здесь

Рис. 2. Вывод программмы

На следующем шаге мы рассмотрим интерфейс Set

Предыдущий шаг Содержание Следующий шаг