Java Language
Очереди и Deques

Использование PriorityQueue

PriorityQueue - это структура данных. Подобно SortedSet , PriorityQueue также сортирует свои элементы, основываясь на своих приоритетах. Прежде всего, элементы, имеющие более высокий приоритет. Тип PriorityQueue должен реализовывать comparable интерфейс или интерфейс comparator , методы которого определяют приоритеты элементов структуры данных.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

LinkedList как очередь FIFO

Класс java.util.LinkedList при реализации java.util.List является универсальной реализацией интерфейса java.util.Queue также работает с принципом FIFO (First In, First Out) .

В приведенном ниже примере с помощью метода offer() элементы вставляются в LinkedList . Эта операция вставки называется enqueue . В while петли ниже, элементы удаляются из Queue на основе FIFO. Эта операция называется dequeue .

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

Вывод этого кода

first element
second element
third element
fourth element
fifth element

Как видно на выходе, первый вставленный элемент «первый элемент» удаляется во-первых, «второй элемент» удаляется во втором месте и т. Д.

Стеки

Что такое стек?

В Java Stacks представляют собой структуру данных LIFO (Last In, First Out) для объектов.

API стека

Java содержит API стека со следующими методами:

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

пример

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

Это возвращает:

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

BlockingQueue - это интерфейс, который представляет собой очередь, которая блокируется, когда вы пытаетесь удалить из нее, и очередь пуста, или если вы пытаетесь вставить в нее элементы, а очередь уже заполнена. Поток, пытающийся удалить из пустой очереди, блокируется до тех пор, пока какой-либо другой поток не вставит элемент в очередь. Нить, пытающаяся присвоить элемент в полной очереди, блокируется до тех пор, пока какой-либо другой поток не освободит место в очереди, либо путем удаления одного или нескольких элементов, либо очистки всей очереди.

Методы BlockingQueue представлены в четырех формах с различными способами обработки операций, которые не могут быть удовлетворены немедленно, но могут быть удовлетворены в какой-то момент в будущем: один генерирует исключение, второй возвращает специальное значение (либо null, либо false, в зависимости от операция), третий блокирует текущую нить неопределенно до тех пор, пока операция не будет успешной, а четвертые блоки только для заданного максимального срока до отказа.

BlockingQueue может быть ограниченным или неограниченным . Ограниченный BlockingQueue - это тот, который инициализируется начальной загрузкой.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

Любые вызовы метода put () будут заблокированы, если размер очереди равен начальной заданной емкости.

Неограниченная очередь - это то, которое инициализируется без емкости, фактически по умолчанию оно инициализируется Integer.MAX_VALUE.

Некоторые общие реализации BlockingQueue :

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Теперь давайте рассмотрим пример ArrayBlockingQueue :

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

Это напечатает:

Entry one done
Entry two done

И поток будет заблокирован после второго выхода.

Интерфейс очереди

основы

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

Глава очереди - это элемент, который будет удален вызовом для удаления или опроса. В очереди FIFO все новые элементы вставляются в хвост очереди.

Интерфейс очереди

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Каждый метод Queue существует в двух формах:

• один генерирует исключение, если операция завершается с ошибкой;
• другой возвращает специальное значение, если операция завершается с ошибкой (либо null либо false зависимости от операции.

Deque

Deque - это «двойная очередь», что означает, что элементы могут быть добавлены спереди или хвостом очереди. Очередь может добавлять элементы в хвост очереди.

Deque наследует интерфейс Queue что означает, что регулярные методы остаются, однако интерфейс Deque предлагает дополнительные методы, чтобы быть более гибкими с очередью. Дополнительные методы действительно говорят сами за себя, если вы знаете, как работает очередь, поскольку эти методы призваны повысить гибкость:

Конечно, доступны те же варианты offer , poll и peek , однако они не работают с исключениями, а скорее со специальными значениями. Нет смысла показывать, что они здесь делают.

Добавление и доступ к элементам

Чтобы добавить элементы в хвост Deque, вы вызываете его метод add() . Вы также можете использовать addFirst() и addLast() , которые добавляют элементы в голову и хвост deque.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

Вы можете заглянуть в элемент во главе очереди, не вытаскивая элемент из очереди. Это делается с помощью метода element() . Вы также можете использовать методы getFirst() и getLast() , которые возвращают первый и последний элемент в Deque . Вот как это выглядит:

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

Удаление элементов

Чтобы удалить элементы из deque, вы вызываете методы remove() , removeFirst() и removeLast() . Вот несколько примеров:

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();