GrabDuck

Очереди и класс ArrayDeque | Java

:

Последнее обновление: 30.10.2015

Очереди представляют структуру данных, работающую по принципу FIFO (first in - first out). То есть чем раньше был добавлен элемент в коллекцию, тем раньше он из нее удаляется. Это стандартная модель однонаправленной очереди. Однако бывают и двунаправленные - то есть такие, в которых мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.

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

Интерфейс Queue

Обобщенный интерфейс Queue<E> расширяет базовый интерфейс Collection и определяет поведение класса в качестве однонаправленной очереди. Свою функциональность он раскрывает через следующие методы:

  • E element(): возвращает, но не удаляет, элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException

  • boolean offer(E obj): добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе - false

  • E peek(): возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null

  • E poll(): возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null

  • E remove(): возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException

Таким образом, у всех классов, которые реализуют данный интерфейс, будет метод offer для добвления в очередь, метод poll для извлечения элемента из головы очереди, и методы peek и element, позволяющие просто получить элемент из головы очереди.

Интерфейс Deque

Интерфейс Deque расширяет вышеописанный интерфейс Queue и определяет поведение двунаправленной очереди, которая работает как обычная однонаправленная очередь, либо как стек, действующий по принципу LIFO (последний вошел - первый вышел).

Интерфейс Deque определяет следующие методы:

  • void addFirst(E obj): добавляет элемент в начало очереди

  • void addLast(E obj): добавляет элемент obj в конец очереди

  • E getFirst(): возвращает без удаления элемент из головы очереди. Если очередь пуста, генерирует исключение NoSuchElementException

  • E getLast(): возвращает без удаления последний элемент очереди. Если очередь пуста, генерирует исключение NoSuchElementException

  • boolean offerFirst(E obj): добавляет элемент obj в самое начало очереди. Если элемент удачно добавлен, возвращает true, иначе - false

  • boolean offerLast(E obj): добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе - false

  • E peekFirst(): возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null

  • E peekLast(): возвращает без удаления последний элемент очереди. Если очередь пуста, возвращает значение null

  • E pollFirst(): возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null

  • E pollLast(): возвращает с удалением последний элемент очереди. Если очередь пуста, возвращает значение null

  • E pop(): возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException

  • void push(E element): добавляет элемент в самое начало очереди

  • E removeFirst(): возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException

Таким образом, наличие методов pop и push позволяет классам, реализующим этот элемент, действовать в качестве стека. В тоже время имеющийся функционал также позволяет создавать двунаправленные очереди, что делает классы, применяющие данный интерфейс, довольно гибкими.

Класс ArrayDeque

В Java очереди представлены рядом классов. Одни из низ - класс ArrayDeque<E>. Этот класс представляют обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection и применяя интерфейс Deque.

В классе ArrayDeque определены следующие конструкторы:

  • ArrayDeque(): создает пустую очередь

  • ArrayDeque(Collection<? extends E> col): создает очередь, наполненную элементами из коллекции col

  • ArrayDeque(int capacity): создает очередь с начальной емкостью capacity. Если мы явно не указываем начальную емкость, то емкость по умолчанию будет равна 16

Пример использования класса:

import java.util.ArrayDeque;

public class CollectionApp {

    public static void main(String[] args) {
        
        ArrayDeque<String> states = new ArrayDeque<String>();
        // стандартное добавление элементов
        states.add("Германия");
        states.add("Франция");
        // добавляем элемент в самое начало
        states.push("Великобритания"); 
        
        // получаем первый элемент без удаления
        String sFirst = states.getFirst();
        String sLast = states.getLast();
        
        while(states.peek()!=null){
            // извлечение c начала
            System.out.println(states.pop());
        }
        System.out.printf("Размер очереди: %d \n", states.size());
        
        
        ArrayDeque<Person> people = new ArrayDeque<Person>();
        people.addFirst(new Person("Tom"));
        people.addLast(new Person("Nick"));
        for(Person p : people){
        
            System.out.println(p.getName());
        }
    }
}
class Person{
    
    private String name;
    public Person(String value){
        
        name=value;
    }
    String getName(){return name;}
}