Очереди представляют структуру данных, работающую по принципу 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
- E removeLast(): возвращает с удалением элемент из конца очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- boolean removeFirstOccurrence(Object obj): удаляет первый встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
- boolean removeLastOccurrence(Object obj): удаляет последний встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
Таким образом, наличие методов pop и push позволяет классам, реализующим этот элемент, действовать в качестве стека. В тоже время имеющийся функционал также позволяет создавать двунаправленные очереди, что делает классы, применяющие данный интерфейс, довольно гибкими.
Класс ArrayDeque
В Java очереди представлены рядом классов. Одни из низ - класс ArrayDeque<E>. Этот класс представляют обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection и применяя интерфейс Deque.
В классе ArrayDeque определены следующие конструкторы:
- ArrayDeque(): создает пустую очередь
- ArrayDeque(Collection<? extends E> col): создает очередь, наполненную элементами из коллекции col
- ArrayDeque(int capacity): создает очередь с начальной емкостью capacity. Если мы явно не указываем начальную емкость, то емкость по умолчанию будет равна 16
Пример использования класса:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 |
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;}
} |
