Очереди представляют структуру данных, работающую по принципу FIFO (first in - first out). То есть чем раньше был добавлен элемент в коллекцию, тем раньше он из нее удаляется. Это стандартная модель однонаправленной очереди. Однако бывают и двунаправленные - то есть такие, в которых мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.
Особенностью классов очередей является то, что они реализуют специальные интерфейсы Queue или Deque.
Обобщенный интерфейс 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 расширяет вышеописанный интерфейс 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
E removeLast(): возвращает с удалением элемент из конца очереди. Если очередь пуста, генерирует исключение
NoSuchElementException
boolean removeFirstOccurrence(Object obj): удаляет первый встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
boolean removeLastOccurrence(Object obj): удаляет последний встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
Таким образом, наличие методов pop
и push
позволяет классам, реализующим этот элемент, действовать в качестве стека.
В тоже время имеющийся функционал также позволяет создавать двунаправленные очереди, что делает классы, применяющие данный интерфейс,
довольно гибкими.
В Java очереди представлены рядом классов. Одни из низ - класс ArrayDeque<E>.
Этот класс представляют обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection
и применяя интерфейс
Deque
.
В классе ArrayDeque определены следующие конструкторы:
ArrayDeque()
: создает пустую очередь
ArrayDeque(Collection<? extends E> col)
: создает очередь, наполненную элементами из коллекции col
ArrayDeque(int capacity)
: создает очередь с начальной емкостью capacity. Если мы явно не указываем начальную емкость, то
емкость по умолчанию будет равна 16
Пример использования класса:
import java.util.ArrayDeque; public class Program{ public static void main(String[] args) { ArrayDeque<String> states = new ArrayDeque<String>(); // стандартное добавление элементов states.add("Germany"); states.addFirst("France"); // добавляем элемент в самое начало states.push("Great Britain"); // добавляем элемент в самое начало states.addLast("Spain"); // добавляем элемент в конец коллекции states.add("Italy"); // получаем первый элемент без удаления String sFirst = states.getFirst(); System.out.println(sFirst); // Great Britain // получаем последний элемент без удаления String sLast = states.getLast(); System.out.println(sLast); // Italy System.out.printf("Queue size: %d \n", states.size()); // 5 // перебор коллекции while(states.peek()!=null){ // извлечение c начала System.out.println(states.pop()); } // очередь из объектов Person 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;} }