Урок 17

Интерфейс Queue и Реализации


1. Интерфейс Queue

Интерфейс Queue

Интерфейс Queue расширяет Collection и объявляет поведение очередей, которые представляют собой список с дисциплиной "первый вошел первый вышел“ (FIFO). Существуют разные типы очередей, в которых порядок основан на некотором критерии. Очереди не могут хранить значения null.

Методы интерфейса Queue:

  1. Е element() - возвращает элемент из головы очереди. Элемент нe удаляется. Если очередь пуста, инициируется исключение NoSuchElementException.
  2. Е remove() - удаляет элемент из головы очереди, возвращая его. Инициирует исключение NoSuchElementException, если очередь пуста.
  3. Е peek() - возвращает элемент из головы очереди. Возвращает null, если очередь пуста. Элемент не удаляется.
  4. Е роll() - возвращает элемент из головы очереди и удаляет его. Возвращает null, если очередь пуста.
  5. boolean offer(Е оbj) - пытается добавить оbj в очередь. Возвращает true, если оbj добавлен, и false в противном случае.

Пример 1. Использование интерфейса Queue

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("Харьков");
        queue.offer("Киев");
        queue.offer("Кременчуг");
        queue.offer("Львов");
        while (queue.size() > 0) {
            System.out.print(queue.poll() + " ");
        }
    }
}

2. Интерфейс Deque

Интерфейс Deque появился в Java 6. Он расширяет Queue и описывает поведение двунаправленной очереди. Двунаправленная очередь может функционировать как стандартная очередь FIFO либо как стек LIFO.

Методы интерфейса Deque:

  1. void addFirst(Е obj)  - добавляет obj в голову двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  2. void addLast(Е obj) - добавляет obj в хвост двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  3. Е getFirst() - возвращает первый элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключение NoSuchElementException.
  4. Е getLast() - возвращает последний элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключения NoSuchElementException.
  5. boolean offerFirst(Е obj) - пытается добавить obj в голову двунаправленной очереди. Возвращает true, если obj добавлен, и false в противном случае. Таким образом, этот метод возвращает false при попытке добавить obj в полную двунаправленную очередь ограниченной емкости.
  6. boolean offerLast(E obj) - пытается добавить obj в хвост двунаправленной очереди. Возвращает true, если obj добавлен, и false в против ном случае.
  7. Е рор() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  8. void push(Е obj) - добавляет элемент в голову двунаправленной очереди. Если в очереди фиксированного объема нет места, возбуждает исключение IllegalStateException.
  9. Е peekFirst() - возвращает элемент, находящийся в голове двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  10. Е peekLast() - возвращает элемент, находящийся в хвосте двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  11. Е pollFirst() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  12. Е pollLast() - возвращает элемент, находящийся в хвосте двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  13. Е removeLast() - возвращает элемент, находящийся в конце двунаправленной очереди, удаляя его в процессе. Возбуждает исключение NoSuchElementException, если очередь пуста.
  14. Е removeFirst() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  15. boolean removeLastOccurrence(Object obj) - удаляет последнее вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false если очередь не содержала obj.
  16. boolean removeFirstOccurrence(Object obj) - удаляет первое вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false, если очередь не содержала obj.

3. Класс ArrayDeque

ArrayDeque создает двунаправленную очередь.

Конструкторы класса ArrayDeque:

  • ArrayDeque() - создает пустую двунаправленную очередь с вместимостью 16 элементов.
  • ArrayDeque(Collection<? extends E> c) - создает двунаправленную очередь из элементов коллекции c в том порядке, в котором они возвращаются итератором коллекции c.
  • ArrayDeque(int numElements) - создает пустую двунаправленную очередь с вместимостью numElements.

Пример 2. Использование класса ArrayDeque

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>(2);
        stack.push("A");
        stack.push("B");
        stack.push("C");
        stack.push("D");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();

        queue.add("A");
        queue.add("B");
        queue.add("C");
        queue.add("D");
        while (!queue.isEmpty()) {
            System.out.print(queue.remove() + " ");
        }
    }
}

4. Класс LinkedList

Интерфейс LinkedList

Класс LinkedList реализует интерфейсы List, Deque. LinkedList – это двухсвязный список.

Конструкторы класса LinkedList:

  • LinkedList()
  • LinkedList(Collection<? extends Е> с)

Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы:

private static class Entry<E>
{
    E element;
    Entry<E> next;
    Entry<E> prev;
    
    Entry(E element, Entry<E> next, Entry<E> prev)
    {
        this.element = element;
        this.next = next;
        this.prev = prev;
    }
}

Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1). На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1). Позволяет добавлять любые значения в том числе и null.

Пример 3. Использование класса LinkedList

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String args[]) {
        // Create a linked list.
        LinkedList<String> list = new LinkedList<>();

        // Add elements to the linked list.
        list.add("F");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("C");
        list.addLast("Z");
        list.addFirst("A");

        list.add(1, "A2");

        System.out.println("Original contents of list: " + list);

        // Remove elements from the linked list.
        list.remove("F");
        list.remove(2);

        System.out.println("Contents of list after deletion: "
                + list);

        // Remove first and last elements.
        list.removeFirst();
        list.removeLast();

        System.out.println("list after deleting first and last: "
                + list);

        // Get and set a value.
        String val = list.get(2);
        list.set(2, val + " Changed");

        System.out.println("list after change: " + list);
    }
}

5. Класс PriorityQueue

PriorityQueue – это класс очереди с приоритетами. По умолчанию очередь с приоритетами размещает элементы согласно естественному порядку сортировки используя Comparable. Элементу с наименьшим значением присваивается наибольший приоритет. Если несколько элементов имеют одинаковый наивысший элемент – связь определяется произвольно. Также можно указать специальный порядок размещения, используя Comparator.

Конструкторы класса PriorityQueue:

  • PriorityQueue() - создает очередь с приоритетами начальной емкостью 11, размещающую элементы согласно естественному порядку сортировки (Comparable);
  • PriorityQueue(Collection<? extends E> c);
  • PriorityQueue(int initialCapacity);
  • PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
  • PriorityQueue(PriorityQueue<? extends E> c);
  • PriorityQueue(SortedSet<? extends E> c).

Пример 4. Использование класса PriorityQueue

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<String> queue1 = new PriorityQueue<>();
        queue1.offer("Texas");
        queue1.offer("Oklahoma");
        queue1.offer("Indiana");
        queue1.offer("Georgia");
        queue1.offer("Texas");
        System.out.print("Priority queue using Comparable: ");
        while (queue1.size() > 0) {
            System.out.print(queue1.remove() + " ");
        }

        PriorityQueue<String> queue2
                = new PriorityQueue<>(4, Collections.reverseOrder());
        queue2.offer("Texas");
        queue2.offer("Oklahoma");
        queue2.offer("Indiana");
        queue2.offer("Georgia");
        queue2.offer("Texas");
        System.out.print("\nPriority queue using Comparator: ");
        while (queue2.size() > 0) {
            System.out.print(queue2.remove() + " ");
        }
    }
}


0 comments
Leave your comment: