Java Queue Interface и неговите реализации

Тук ще обсъдим интерфейса на Java Queue. Ще разберете Howво представлява структурата на данните на Queue , How е представена в Java, кои методи са най-важни за всички опашки. Също така Howви реализации на Queue са на езика Java. След това разглеждаме по-отблизо най-важните реализации и ги научаваме с примери.

Структура от данни на опашка

Опашката е линейна абстрактна структура от данни с конкретен ред на извършване на операции — First In First Out (FIFO). Това означава, че можете да добавите елемент (or да поставите в опашката, да поставите в опашката) само в края на структурата и да вземете елемент (да извадите от опашката or да премахнете от опашката) само от началото му. Можете да си представите структурата на данните на Queue много лесно. Изглежда като опашка or опашка от клиенти в реалния живот. Клиентът, който е дошъл първи, също ще бъде обслужен първи. Ако имате четирима души на опашка в McDonalds or другаде, първият, който се нареди, ще получи първия магазин. Ако дойде новият клиент, той/тя ще бъде 5-ти по ред за получаване на хамбургери. Така че, докато работите с опашка, нови елементи се добавят към края и ако искате да получите елемент, той ще бъде взет от началото. Това е основният принцип на работата на класическата структура на данните на опашката.

Опашка в Java

Опашката в Java е интерфейс. Според documentацията на Oracle, Queue интерфейсът има 2 суперинтерфейса, 4 различни интерфейса, които наследяват от опашката, и изключително впечатляващ списък от класове. Какво означава? На първо място, Java Queue е част от Collection Framework и имплементира Collection интерфейс. Така че поддържа всички методи на интерфейса за събиране, като вмъкване, изтриване и т.н. Queue имплементира Iterable интерфейс, който позволява обект да бъде целта на израза "for-each loop".

Методи за опашка Java

Опашката декларира редица методи. Като методи на интерфейса те трябва да бъдат представени във всички класове, които имплементират Queue. Най-важните методи за опашка, Java:

• Boolean offer() – вмъква нов елемент в опашката, ако е възможно
• Boolean add(E e) – вмъква нов елемент в опашката, ако е възможно. Връща true в случай на успех и хвърля IllegalStateException, ако няма място.
• Object poll() – извлича и премахва елемент от главата на. Връща null, ако опашката е празна.
• Object remove() – извлича и премахва елемент от главата на опашката.
• Object peek() – извлича, но не премахва елемент от главата на опашката. Връща null, ако опашката е празна.
• Object element() – извлича, но не премахва елемент от главата на опашката.

Подинтерфейси на Java Queue

Интерфейсът на опашката е наследен от 4 подинтерфейса – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Можете да ги разделите на 3 групи: Deques, Blocking Queues и Transfer Queues, като BlockingDeque принадлежи към първите две. Нека хвърлим един поглед на тези групи.

Декес

Deque означава D ouble - E nded Queue и поддържа добавяне or премахване от всяка опашка на данните като опашка (first-in-first-out/FIFO) or от главата като друга популярна структура от данни, наречена стек (last-in- първи излязъл/LIFO). Класове, които прилагат Deque интерфейс: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Блокиране на опашки

Опашка за блокиране е опашка, която блокира нишка в два случая:

• нишката се опитва да получи елементи от празна опашка
• нишката се опитва да постави елементи в пълната опашка

Когато нишка се опита да получи елементи от празна опашка, тя изчаква, докато друга нишка постави елементите в опашката. По същия начин, когато нишка се опита да постави елементи в пълна опашка, тя изчаква, докато друга нишка извади елементите от опашката, за да получи свободно място за елементите. Разбира се, концепцията за "пълна опашка" предполага, че опашката има ограничен размер, който обикновено се посочва в конструктора. Стандартните опашки за блокиране включват LinkedBlockingQueue, SynchronousQueue и ArrayBlockingQueue. Внедряване на класове на интерфейса BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeе подинтерфейс за BlockingQueue. BlockingDeque като BlockingQueue е опашка за блокиране, но двупосочна. Така че наследява свойствата на интерфейса Deque. Той е ориентиран към многопоточно изпълнение, не позволява нулеви елементи и капацитетът може да бъде ограничен. Реализациите на интерфейса BlockingDeque блокират операцията за получаване на елементи, ако опашката е празна, и добавяне на елемент в опашката, ако е пълна.

Трансферни опашки

Интерфейсът TransferQueue разширява интерфейса BlockingQueue. Въпреки това, за разлика от реализацията на опашките на интерфейса BlockingQueue, където нишките могат да бъдат блокирани, ако опашката е празна (четене) or ако опашката е пълна (запис), опашките на интерфейса TransferQueue блокират потока за запис, докато друг поток не извлече елемента. Използвайте метод за прехвърляне за това. С други думи, реализацията на BlockingQueue гарантира, че елементът, създаден от производителя, трябва да бъде в опашката, докато реализацията на TransferQueue гарантира, че елементът на производителя е "получен" от потребителя. Има само една официална Java реализация на интерфейса TransferQueue — LinkedTransferQueue.

Реализации на Java Queue

Има много класове, които реализират интерфейс на Queue:

• AbstractQueue според documentите на Queue Java 8, този абстрактен клас осигурява основни реализации на някои операции на Queue. Не позволява нулеви елементи. Има още 3 метода за добавяне, премахване и елемент, базирани съответно на Queue classical offer , poll и peek . Те обаче хвърлят изключения, instead of да посочват неуспех чрез фалшиви or нулеви връщания.
• ArrayBlockingQueue — FIFO блокираща опашка с фиксиран размер, подкрепена от масив
• ArrayDeque — реализация на масив с възможност за промяна на размера на интерфейса Deque
• ConcurrentLinkedDeque — неограничен едновременен deque, базиран на свързани възли.
• ConcurrentLinkedQueue — неограничена нишково-безопасна опашка, базирана на свързани възли.
• DelayQueue — базирана на времето опашка за планиране, подкрепена от купчина
• LinkedBlockingDeque — едновременната реализация на интерфейса Deque.
• LinkedBlockingQueue — опционално ограничена опашка за блокиране на FIFO, подкрепена от свързани възли
• LinkedList — реализация на двойно свързан списък на интерфейсите List и Deque. Внедрява всички незадължителни списъчни операции и разрешава всички елементи (включително null)
• LinkedTransferQueue — неограничен TransferQueue, базиран на свързани възли
• PriorityBlockingQueue — неограничена опашка с приоритет за блокиране, подкрепена от куп
• PriorityQueue — опашка с приоритет, базирана на структурата на данните в купчина
• SynchronousQueue — блокираща опашка, където всяка операция за вмъкване трябва да изчака съответната операция за премахване от друга нишка и обратно.

Най-популярните реализации са LinkedList, ArrayBlockingQueue и PriorityQueue. Нека да ги разгледаме и да направим няколко примера за по-добро разбиране.

LinkedList

Клас LinkedList в Java имплементира List и Deque интерфейси. И така, това е комбинация от List и Deque, двупосочна опашка, която поддържа добавяне и премахване на елементи от двете страни. В Java LinkedList е двойно свързан списък: всеки елемент на List извиква Node и съдържа обект и препратки към два съседни обекта - предишния и следващия. Може да кажете, че LinkedList не е много ефективен по отношение на използването на паметта. Това е вярно, но тази структура от данни може да бъде полезна в случай на изпълнение на операциите за вмъкване и изтриване. Това обаче се случва само ако използвате итератори за тях (в този случай се случва в постоянно време). Операциите за достъп по индекс се извършват чрез търсене от началото на края (което е по-близо) до желания елемент. Не забравяйте обаче за допълнителните разходи за съхранение на препратки между елементите. И така, LinkedList е най-популярната реализация на опашка в Java. Това също е имплементация на List и Deque и ни позволява да създадем двупосочна опашка, състояща се от всяHowви обекти, включително null. LinkedList е колекция от елементи.

Конструктори на LinkedList

LinkedList() без параметри се използва за конструиране на празен списък. LinkedList(Collection<? extends E> c) е за създаване на списък, съдържащ елементите на посочената колекция, в ред, те се връщат от итератора на колекцията.

Основни методи на LinkedList:

• add(E element) Добавя посочения елемент в края на този списък;
• add(int index, E element) Вмъква елемента на указаната позиция индекс;
• get(int index) Връща елемента на посочената позиция в този списък;
• remove(int index) Премахва елемента, който е на позиция index;
• remove(Object o) Премахва първото срещане на елемент ?o от този списък, ако е там.
• remove() Извлича и премахва първия елемент от списъка.
• addFirst(), addLast() добавяне на елемент в началото/края на списък
• clear() премахва всички елементи от списъка
• съдържа (Object o) връща true, ако списъкът съдържа o елемента.
• indexOf(Object o) връща индекса на първото срещане на елемента o or -1, ако не е в списъка.
• set(int index, E element) замества елемента в индексна позиция с елемента
• size() Връща количеството елементи в списъка.
• toArray() връща масив, съдържащ всички елементи на списъка от първия до последния елемент.
• pop(), който изважда елемент от стека (представен от списъка)
• push(E e), който избутва елемент в стека (представен от този списък)

Пример за Java Queue — LinkedList (поставяне и премахване на елементи по различни начини)

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

PriorityQueue

PriorityQueue не е точно опашката в общото meaning на FIFO. Елементите на приоритетната опашка се подреждат според естествения им ред or чрез компаратор, предоставен по време на изграждане на опашка, в зависимост от това кой конструктор се използва. Това обаче не е ред, Howъвто би могъл да бъде в линейна структура като списък (от най-големия към най-малкия or обратно). Опашка с приоритет, базирана на минимална купчина с приоритет. Heap е структура от данни, базирана на двоично дърво. Приоритетът на всеки родител е по-голям от приоритетите на неговите деца. Едно дърво се нарича пълно двоично, ако всеки родител има не повече от две деца и запълването на нивата върви отгоре надолу (от едно и също ниво - отляво надясно). Двоичната купчина се реорганизира всеки път, когато се добави or премахне нов елемент от нея. В случай на min-heap, най-малкият елемент отива в корена, независимо от реда на неговото вмъкване. Приоритетна опашка, базирана на тази min-heap, така че ако имаме PriorityQueue от цели числа, нейният първи елемент ще бъде най-малкото от тези числа. Ако изтриете корена, следващият най-малък става корен.

Основни методи на PriorityQueue:

• boolean add(object) вмъква посочения елемент в приоритетната опашка. Връща true в случай на успех. Ако опашката е пълна, методът хвърля изключение.
• boolean offer(object) вмъква посочения елемент в тази приоритетна опашка. Ако опашката е пълна, методът връща false.
• boolean remove(object) премахва едно копие на посочения елемент от тази опашка, ако е налице.
• Object poll() извлича и премахва главата на тази опашка. Връща null, ако опашката е празна.
• void clear() премахва всички елементи от приоритетната опашка.
• Object element() извлича главата на тази опашка, без да я премахва. Изхвърля NoSuchElementException, ако опашката е празна.
• Object peek() извлича главата на опашката, без да я премахва. Връща null, ако опашката е празна.
• boolean contains(Object o) връща true, ако опашката съдържа o елемента.
• int size() връща броя на елементите в тази опашка.

Пример за PriorityQueue

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Важно е да се разбере, че приоритетните опашки са базирани на двоични купчини, така че те не поддържат елементи в линеен сортиран ред. Всеки път от корена до листа е подреден, но различните пътища от корена не са. Това означава, че можете да получите минималния елемент от опашката много бързо. Ако изтривате главата всеки път, ще отпечатате сортирана структура.

ArrayBlockingQueue

Вътрешна структура на данните на ArrayBlockingQueueсе основава на кръгъл масив за съхраняване на елементи. Това е типична опашка (FIFO), в случай че нови елементи са вмъкнати в опашката на опашката и операциите за извличане връщат елемент от главата на опашката. Веднъж създаденият капацитет на опашката не може да бъде променен. Опитите за вмъкване (поставяне) на елемент в пълна опашка водят до блокиране на потока; опитът да се вземе елемент от празна опашка също блокира нишката. Както казахме преди, този масив е кръгъл. Това означава, че първият и последният елемент на масива се третират логически съседни. Опашката напредва в индексите на елементите head и tail всеки път, когато поставите elemento в опашката or го премахнете от опашката. Ако няHowъв индекс придвижи напред последния елемент от масива, той се рестартира от 0. Следователно, опашката не трябва да измества всички елементи в случай на премахване на главата (Howто в обикновения масив). Въпреки това, в случай на премахване на елемент от средата (с помощта на Iterator.remove), елементите се изместват. ArrayBlockingQueue поддържа допълнителна политика за справедливост с параметър fair в конструктора, за да подреди работата на чакащите потоци на производители (вмъкване на елементи) и потребители (извличане на елементи). По подразбиране поръчката не е гарантирана. Въпреки това, ако опашката е създадена с "fair == true", изпълнението на класа ArrayBlockingQueue осигурява достъп до нишката във FIFO ред. Собственият капитал обикновено намалява честотната лента, но също така намалява променливостта и предотвратява изчерпването на ресурсите.

Конструктори на клас ArrayBlockingQueue

• ArrayBlockingQueue (int капацитет) създава опашка с фиксиран капацитет и с правила за достъп по подразбиране.
• ArrayBlockingQueue (int капацитет, boolean fair) създава опашка с фиксиран капацитет и определена политика за достъп.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) създава опашка с фиксиран капацитет, определен от правилата за достъп, и включва елементи в опашката.

Тук имаме примера за BlockingQueueExample. Създаваме опашка от ArrayBlockingQueue с капацитет от един елемент и справедлив флаг. Започват се две нишки. Първият от тях, нишката на производителя, подрежда съобщенията от масива съобщения с помощта на метода put. Втората нишка, Consumer, чете елементи от опашката с помощта на метода take и ги показва в конзолата. Редът на елементите е естественият за опашката.

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

Резултатът е опашката в естествен ред; първите два елемента се появяват със закъснение. За да затвърдите наученото, ви предлагаме да гледате видео урок от нашия курс по Java

Изводи

• Опашката се използва за вмъкване на елементи в края на опашката и премахване от началото на опашката. Той следва концепцията FIFO.
• Java Queue е част от Collection Framework и имплементира Collection интерфейс. Така че поддържа всички методи на интерфейса за събиране, като вмъкване, изтриване и т.н.
• Най-често използваните реализации на Queue са LinkedList, ArrayBlockingQueue и PriorityQueue.
• Елементите на приоритетната опашка се подреждат според естествения им ред or чрез компаратор, предоставен по време на изграждане на опашка, в зависимост от това кой конструктор се използва.
• Ако се извърши нулева операция върху BlockingQueues, се хвърля изключение NullPointerException.