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

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

Очереди представляют структуру данных, работающую по принципу 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

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

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;}
}
Помощь сайту
Юмани:
410011174743222
Перевод на карту
Номер карты:
4048415020898850