Java Queue Interface și implementările sale

Aici vom discuta despre interfața Java Queue. Veți afla ce este structura de date a cozii , cum este reprezentată în Java, ce metode sunt cele mai importante pentru toate cozile. De asemenea, ce implementări ale Queue sunt în limbajul Java. După aceea, aruncăm o privire mai atentă la cele mai importante implementări și le învățăm cu exemple.

Structura datelor în coadă

O coadă este o structură de date liniară abstractă cu ordinea specială de efectuare a operațiunilor - First In First Out (FIFO). Asta înseamnă că puteți adăuga un element (sau puneți în coadă, pus în coadă) doar la sfârșitul structurii și puteți lua un element (decodați sau eliminați din coadă) doar de la începutul său. Vă puteți imagina foarte ușor structura datelor din coadă. Pare o coadă sau un rând de clienți în viața reală. Clientul care a venit primul va fi servit și primul. Dacă aveți patru persoane la coadă în McDonalds sau în altă parte, primii care se aliniază vor fi primii care vor primi magazinul. Dacă vine noul client, el/ea va fi al 5-lea la rând care primește hamburgeri. Deci, în timp ce lucrați cu o coadă, elemente noi sunt adăugate la sfârșit, iar dacă doriți să obțineți un element, acesta va fi luat de la început. Acesta este principiul principal al lucrului clasic al structurii de date a cozii.

Coadă în Java

Queue în Java este o interfață. Conform documentației Oracle, interfața Queue are 2 superinterfețe, 4 interfețe diferite care moștenesc din coadă și o listă extrem de impresionantă de clase. Ce înseamnă? În primul rând, Java Queue face parte din cadrul Collection Framework și implementează interfața Collection. Deci, acceptă toate metodele de interfață Collection, cum ar fi inserarea, ștergerea și așa mai departe. Queue implementează o interfață iterabilă, care permite unui obiect să fie ținta instrucțiunii „for-each loop”.

Metode de coadă Java

Coada declară un număr de metode. Ca metode ale interfeței, acestea ar trebui să fie reprezentate în toate clasele care implementează Queue. Cele mai importante metode de coadă, Java:

• Boolean offer() – inserează un nou element în coadă dacă este posibil
• Boolean add(E e) – inserează un nou element în coadă dacă este posibil. Returnează true în caz de succes și aruncă o IllegalStateException dacă nu există spațiu.
• Object poll() – preia și elimină un element din capul fișierului. Returnează null dacă coada este goală.
• Object remove() – preia și elimină un element din capul cozii.
• Object peek() – preia, dar nu elimină un element din capul cozii. Returnează null dacă coada este goală.
• Object element() – preia, dar nu elimină un element din capul cozii.

Subinterfețe ale cozii Java

Interfața de coadă este moștenită de 4 subinterfețe – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Le puteți împărți în 3 grupuri: Deques, Blocking Queues și Transfer Queues cu BlockingDeque aparținând primelor două. Să aruncăm o privire asupra acestor grupuri.

Deques

Deque înseamnă Coadă cu completare dublă și acceptă adăugarea sau eliminarea din fiecare coadă a datelor ca coadă (primul intrat, primul-ieșit/FIFO) sau din cap ca o altă structură de date populară numită stivă (ultimul intrat ) . primul ieşit/LIFO). Clasele care implementează Interfața Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Cozi de blocare

O coadă de blocare este o coadă care blochează un fir în două cazuri:

• threadul încearcă să obțină elemente dintr-o coadă goală
• threadul încearcă să pună elemente în coada completă

Când un fir încearcă să obțină articole dintr-o coadă goală, așteaptă până când un alt fir pune articolele în coadă. În mod similar, atunci când un fir încearcă să pună elemente într-o coadă plină, așteaptă până când un alt fir scoate elementele din coadă pentru a obține spațiu liber pentru elemente. Sigur, conceptul de „coadă completă” implică faptul că coada are o dimensiune limitată, care este de obicei specificată în constructor. Cozile de blocare standard includ LinkedBlockingQueue, SynchronousQueue și ArrayBlockingQueue. Implementarea claselor de interfață BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeeste o subinterfață pentru BlockingQueue. BlockingDeque, cum ar fi BlockingQueue, este o coadă de blocare, dar bidirecțională. Deci moștenește proprietățile interfeței Deque. Este orientat spre execuție multi-threaded, nu permite zero elemente și capacitatea ar putea fi limitată. Implementările interfeței BlockingDeque blochează operațiunea de obținere a elementelor dacă coada este goală și adăugarea unui element în coadă dacă este plină.

Cozi de transfer

Interfața TransferQueue extinde interfața BlockingQueue. Totuși, spre deosebire de implementarea cozilor de interfață BlockingQueue, unde firele de execuție pot fi blocate dacă coada este goală (citire) sau dacă coada este plină (scriere), cozile de interfață TransferQueue blochează fluxul de scriere până când un alt flux preia elementul. Utilizați o metodă de transfer pentru aceasta. Cu alte cuvinte, implementarea BlockingQueue garantează că elementul creat de Producător trebuie să fie în coadă, în timp ce implementarea TransferQueue garantează că elementul Producer este „primit” de către Consumator. Există o singură implementare oficială Java a interfeței TransferQueue – LinkedTransferQueue.

Implementări Java Queue

Există multe clase care implementează interfața Queue:

• AbstractQueue conform documentelor Queue Java 8, această clasă abstractă oferă implementări de bază ale unor operațiuni Queue. Nu permite elemente nule. Există încă 3 metode de adăugare, eliminare și element bazat pe Coadă de așteptare clasică oferta , sondajul și, respectiv, peek . Cu toate acestea, ei aruncă excepții în loc să indice eșecul prin returnări false sau nule.
• ArrayBlockingQueue — o coadă de blocare FIFO de dimensiune fixă ​​susținută de o matrice
• ArrayDeque — implementarea matricei redimensionabile a interfeței Deque
• ConcurrentLinkedDeque — un deque simultan nelimitat bazat pe noduri legate.
• ConcurrentLinkedQueue — o coadă nelimitată, sigură pentru fire bazată pe noduri legate.
• DelayQueue — o coadă de programare bazată pe timp, susținută de un heap
• LinkedBlockingDeque — implementarea concomitentă a interfeței Deque.
• LinkedBlockingQueue — o coadă de blocare FIFO delimitată opțional, susținută de noduri legate
• LinkedList — implementarea listelor dublu legate a interfețelor List și Deque. Implementează toate operațiunile opționale de listă și permite toate elementele (inclusiv null)
• LinkedTransferQueue — un TransferQueue nelimitat bazat pe noduri legate
• PriorityBlockingQueue — o coadă cu prioritate de blocare nelimitată susținută de un heap
• PriorityQueue — o coadă de prioritate bazată pe structura de date heap
• SynchronousQueue — o coadă de blocare în care fiecare operație de inserare trebuie să aștepte o operație de eliminare corespunzătoare de către un alt fir și invers.

Cele mai populare implementări sunt LinkedList, ArrayBlockingQueue și PriorityQueue. Să ne uităm la ele și să facem câteva exemple pentru o mai bună înțelegere.

LinkedList

Clasa LinkedList în Java implementează interfețele List și Deque. Deci, este o combinație de Listă și Deque, o coadă bidirecțională, care acceptă adăugarea și eliminarea elementelor din ambele părți. În Java, LinkedList este Listă dublu legată: fiecare element al Listă apelează Node și conține un obiect și trimiteri la două obiecte învecinate - anterior și următorul. Puteți spune că LinkedList nu este foarte eficient în ceea ce privește utilizarea memoriei. Este adevărat, dar această structură de date poate fi utilă în cazul performanței operațiunilor de inserare și ștergere. Cu toate acestea, se întâmplă doar dacă folosiți iteratoare pentru ele (în acest caz, apare în timp constant). Operațiile de acces prin index se efectuează prin căutarea de la începutul sfârșitului (oricare este mai aproape) până la elementul dorit. Cu toate acestea, nu uitați de costurile suplimentare pentru stocarea referințelor între elemente. Deci, LinkedList este cea mai populară implementare de coadă în Java. Este și o implementare a List și Deque și ne permite să creăm o coadă bidirecțională constând din orice obiecte, inclusiv null. LinkedList este o colecție de elemente.

Constructori LinkedList

LinkedList() fără parametri este folosit pentru a construi o listă goală. LinkedList(Collection<? extends E> c) este pentru crearea unei liste care să conțină elementele colecției specificate, în ordine, acestea sunt returnate de iteratorul colecției.

Principalele metode LinkedList:

• add(E element) Adaugă elementul specificat la sfârșitul acestei liste;
• add(int index, E element) Inserează elementul la indexul de poziție specificat;
• get(int index) Returnează elementul la poziția specificată în această listă;
• remove(int index) Îndepărtează elementul care se află la indexul de poziție;
• remove(Obiect o) Îndepărtează prima apariție a elementului ?o din această listă dacă există.
• remove() Preia și elimină primul element al listei.
• addFirst(), addLast() adaugă un element la începutul/sfârșitul unei liste
• clear() elimină toate elementele din listă
• contains(Object o) returnează adevărat dacă lista conține elementul o.
• indexOf(Object o) returnează indexul primei apariții a elementului o sau -1 dacă nu este în listă.
• set(index int, element E) înlocuiește elementul din poziția indexului cu elementul
• size() Returnează cantitatea de elemente din listă.
• toArray() returnează un tablou care conține toate elementele listei de la primul până la ultimul element.
• pop() care scoate un element din stivă (reprezentat de listă)
• push(E e) care împinge un element pe stivă (reprezentat de această listă)

Exemplu de coadă Java - LinkedList (punerea și eliminarea elementelor în moduri diferite)

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 nu este tocmai coada în sensul general FIFO. Elementele cozii de prioritate sunt ordonate în funcție de ordonarea lor naturală, sau de un Comparator furnizat în momentul construirii cozii, în funcție de constructorul utilizat. Cu toate acestea, nu este o ordine așa cum ar putea fi într-o structură liniară, cum ar fi lista (de la cel mai mare la cel mai mic sau invers). O coadă de prioritate bazată pe o grămadă min de prioritate. Heap este o structură de date bazată pe arbore binar. Prioritatea fiecărui părinte este mai mare decât prioritățile copiilor săi. Un arbore se numește binar complet dacă fiecare părinte are nu mai mult de doi copii, iar umplerea nivelurilor merge de sus în jos (de la același nivel - de la stânga la dreapta). Heap-ul binar se reorganizează de fiecare dată când un nou element este adăugat sau eliminat din el. În cazul min-heap-ului, cel mai mic element merge la rădăcină indiferent de ordinea inserării acestuia. Coadă de prioritate bazată pe acest min-heap, deci dacă avem o Coadă Priority de numere întregi, primul său element va fi cel mai mic dintre aceste numere. Dacă ștergeți rădăcina, următoarea cea mai mică devine rădăcină.

Principalele metode PriorityQueue:

• boolean add(object) inserează elementul specificat în coada de prioritate. Returnează adevărat în caz de succes. Dacă coada este plină, metoda aruncă o excepție.
• oferta booleană (obiect) inserează elementul specificat în această coadă de prioritate. Dacă coada este plină, metoda returnează false.
• boolean remove(obiect) elimină o singură instanță a elementului specificat din această coadă, dacă este prezentă.
• Object poll() preia și elimină capul acestei cozi. Returnează null dacă coada este goală.
• void clear() elimină toate elementele din coada de prioritate.
• Object element() preia capul acestei cozi fără a-l elimina. Aruncă NoSuchElementException dacă coada este goală.
• Object peek() preia capul cozii fără a-l elimina. Returnează null dacă coada este goală.
• boolean contains(Object o) returnează adevărat dacă coada conține elementul o.
• int size() returnează numărul de elemente din această coadă.

Exemplu de 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

Este important să înțelegeți că cozile prioritare se bazează pe grămezi binare, deci nu păstrează elementele în ordine liniară sortată. Fiecare cale de la rădăcină la frunză este ordonată, dar diferitele moduri de la rădăcină nu sunt. Asta înseamnă că poți obține elementul minim al cozii foarte rapid. Dacă ștergeți capul de fiecare dată, veți imprima o structură sortată.

ArrayBlockingQueue

Structura internă de date a ArrayBlockingQueuese bazează pe o matrice circulară pentru a stoca elemente. Este o coadă tipică (FIFO) în cazul în care elemente noi sunt inserate la coada cozii, iar operațiunile de extracție returnează un element din capul cozii. Odată creată, capacitatea cozii nu poate fi modificată. Încercările de a introduce (pune) un element într-o coadă plină duc la blocarea fluxului; încercarea de a lua un element dintr-o coadă goală blochează și firul. După cum am spus mai înainte, această matrice este circulară. Aceasta înseamnă că primul și ultimul element al matricei sunt tratate logic adiacente. Coada avansează indicii elementelor cap și coadă de fiecare dată când puneți elementul în coadă sau îl eliminați din coadă. Dacă un index avansează ultimul element al matricei, repornește de la 0. Prin urmare, coada nu trebuie să mute toate elementele în cazul înlăturării capului (ca în matrice obișnuită). Totuși, în cazul eliminării unui element din mijloc (folosind Iterator.remove), elementele sunt deplasate. ArrayBlockingQueue acceptă o politică de corectitudine suplimentară cu parametru echitabil în constructor pentru a ordona munca fluxurilor de așteptare ale producătorilor (inserarea elementelor) și consumatorilor (extragerea elementelor). În mod implicit, comanda nu este garantată. Cu toate acestea, dacă coada este creată cu „fair == true”, implementarea clasei ArrayBlockingQueue oferă acces la fire în ordine FIFO. Echitatea reduce de obicei lățimea de bandă, dar reduce și volatilitatea și previne epuizarea resurselor.

Constructori de clasă ArrayBlockingQueue

• ArrayBlockingQueue (capacitate int) creează o coadă de capacitate fixă ​​și cu o politică de acces implicită.
• ArrayBlockingQueue (capacitate int, boolean fair) creează o coadă cu o capacitate fixă ​​și o politică de acces specificată.
• ArrayBlockingQueue (capacitate int, fair boolean, Collection <? extinde E> c) creează o coadă cu o capacitate fixă ​​specificată de politica de acces și include elemente în coadă.

Aici avem exemplul BlockingQueueExample. Creăm o coadă a ArrayBlockingQueue cu o capacitate de un element și un flag fair. Sunt pornite două fire. Primul dintre ele, firul Producer, pune în coadă mesajele din matricea de mesaje folosind metoda put. Al doilea thread, Consumer, citește elementele din coadă folosind metoda take și le afișează în consolă. Ordinea elementelor este cea firească pentru coadă.

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();
       }
   }

Ieșirea este coada în ordine naturală; primele două elemente apar cu întârziere. Pentru a consolida ceea ce ați învățat, vă sugerăm să urmăriți o lecție video de la Cursul nostru Java

Concluzii

• Coada este folosită pentru a insera elemente la sfârșitul cozii și elimină de la începutul cozii. Urmează conceptul FIFO.
• Java Queue este o parte a Collection Framework și implementează interfața Collection. Deci, acceptă toate metodele de interfață Collection, cum ar fi inserarea, ștergerea și așa mai departe.
• Cele mai frecvent utilizate implementări ale Queue sunt LinkedList, ArrayBlockingQueue și PriorityQueue.
• Elementele cozii de prioritate sunt ordonate în funcție de ordonarea lor naturală, sau de un Comparator furnizat în momentul construirii cozii, în funcție de constructorul utilizat.
• Dacă se efectuează orice operație nulă pe BlockingQueues, este aruncată NullPointerException.