Java Queue Interface og dets implementeringer

Her skal vi diskutere Java Queue-grænsefladen. Du vil finde ud af, hvad kødatastruktur er, hvordan den er repræsenteret i Java, hvilke metoder der er de vigtigste for alle køer. Også hvilke implementeringer af Queue er i Java-sproget. Derefter ser vi nærmere på de vigtigste implementeringer og lærer dem med eksempler.

Kødatastruktur

En kø er en lineær abstrakt datastruktur med den særlige rækkefølge for udførelse af operationer - First In First Out (FIFO). Det betyder, at du kun kan tilføje et element (eller sætte i køen) i slutningen af ​​strukturen, og kun tage et element (udsætte eller fjerne fra køen) fra dets begyndelse. Du kan meget nemt forestille dig Kø-datastrukturen. Det virker som en kø eller en række kunder i det virkelige liv. Kunden, der kom først, vil også blive betjent først. Hvis du har fire personer i kø i McDonalds eller andre steder, vil den første, der står i kø, være den første, der får butikken. Hvis den nye kunde kommer, vil han/hun være den 5. i rækken til at få hamburgere. Så mens du arbejder med en kø, tilføjes nye elementer til slutningen, og hvis du vil have et element, tages det fra begyndelsen. Dette er hovedprincippet i klassisk kødatastrukturarbejde.

Kø i Java

Kø i Java er en grænseflade. Ifølge Oracle dokumentation har Queue interface 2 superinterfaces, 4 forskellige interfaces, der arver fra køen, og en ekstremt imponerende liste af klasser. Hvad betyder det? Først og fremmest er Java Queue en del af Collection Framework og implementerer Collection-grænsefladen. Så det understøtter alle metoder til samlingsgrænseflade såsom indsættelse, sletning og så videre. Kø implementerer Iterable-grænseflade, der tillader et objekt at være målet for "for-each loop"-sætningen.

Kø-metoder Java

Køen erklærer en række metoder. Som grænseflademetoder bør de være repræsenteret i alle klasser, der implementerer Queue. De vigtigste kømetoder, Java:

• Boolean offer() – indsætter et nyt element i køen, hvis det er muligt
• Boolean add(E e) – indsætter et nyt element i køen, hvis det er muligt. Returnerer true i tilfælde af succes og kaster en IllegalStateException, hvis der ikke er mellemrum.
• Object poll() – henter og fjerner et element fra hovedet af. Returnerer null, hvis køen er tom.
• Object remove() – henter og fjerner et element fra køens hoved.
• Object peek() – henter, men fjerner ikke et element fra hovedet i køen. Returnerer null, hvis køen er tom.
• Object element() – henter, men fjerner ikke et element fra hovedet i køen.

Undergrænseflader til Java Queue

Køgrænsefladen arves af 4 undergrænseflader – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Du kan opdele dem i 3 grupper: Deques, Blocking Queue og Transfer Queue med BlockingDeque tilhørende de to først. Lad os tage et glimt af disse grupper.

Deques

Deque betyder fordoblet Kø og understøtter tilføjelse eller fjernelse fra enten ende af dataene som en kø (først-ind- først -ud/FIFO) eller fra hovedet som en anden populær datastruktur kaldet stak ( sidst - ind- først ud/LIFO). Klasser, der implementerer Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Blokering af køer

En blokerende kø er en kø, der blokerer en tråd i to tilfælde:

• tråden forsøger at hente elementer fra en tom kø
• tråden forsøger at sætte elementer i den fulde kø

Når en tråd forsøger at hente emner fra en tom kø, venter den, indtil en anden tråd sætter emnerne i køen. På samme måde, når en tråd forsøger at sætte elementer i en fuld kø, venter den, indtil en anden tråd tager elementerne ud af køen for at få ledig plads til elementerne. Sikker på, begrebet "fuld kø" indebærer, at køen har en begrænset størrelse, som normalt er angivet i konstruktøren. Standard blokeringskøer inkluderer LinkedBlockingQueue, SynchronousQueue og ArrayBlockingQueue. Implementering af klasser af BlockingQueue- grænseflade: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeer en undergrænseflade til BlockingQueue. BlockingDeque såsom BlockingQueue er en blokerende kø, men tovejs. Så det arver egenskaberne for Deque-grænsefladen. Den er orienteret til multi-threaded udførelse, tillader ikke nul elementer, og kapaciteten kan være begrænset. Implementeringer af BlockingDeque-grænsefladen blokerer operationen med at hente elementer, hvis køen er tom, og tilføje et element i køen, hvis den er fuld.

Overførselskøer

TransferQueue-grænsefladen udvider BlockingQueue-grænsefladen. Men i modsætning til implementeringen af ​​BlockingQueue-grænsefladekøer, hvor tråde kan blokeres, hvis køen er tom (læser), eller hvis køen er fuld (skriver), blokerer TransferQueue-grænsefladekøer skrivestrømmen, indtil en anden strøm henter elementet. Brug en overførselsmetode til dette. Med andre ord garanterer implementeringen af ​​BlockingQueue, at det af Producen oprettede element skal stå i køen, mens implementeringen af ​​TransferQueue garanterer, at Producer-elementet "modtages" af Forbrugeren. Der er kun én officiel Java-implementering af TransferQueue-grænsefladen - LinkedTransferQueue.

Java-kø-implementeringer

Der er mange klasser, der implementerer kø-grænseflade:

• AbstractQueue ifølge Queue Java 8 docs, denne abstrakte klasse giver grundlæggende implementeringer af nogle Queue-operationer. Det tillader ikke null-elementer. Der er yderligere 3 metoder til tilføjelse, fjernelse og element baseret på henholdsvis Queue classic offer , poll , og peek . Men de kaster undtagelser i stedet for at indikere fejl via falske eller null returneringer.
• ArrayBlockingQueue — en FIFO-blokeringskø med fast størrelse understøttet af et array
• ArrayDeque — array-implementering, der kan ændres størrelse, af Deque-grænsefladen
• ConcurrentLinkedDeque — en ubegrænset samtidig deque baseret på sammenkædede noder.
• ConcurrentLinkedQueue — en ubegrænset trådsikker kø baseret på sammenkædede noder.
• DelayQueue — en tidsbaseret planlægningskø understøttet af en heap
• LinkedBlockingDeque — den samtidige implementering af Deque-grænsefladen.
• LinkedBlockingQueue — en valgfrit afgrænset FIFO-blokeringskø understøttet af sammenkædede noder
• LinkedList — dobbeltlinket listeimplementering af List- og Deque-grænsefladerne. Implementerer alle valgfri listeoperationer og tillader alle elementer (inklusive null)
• LinkedTransferQueue — en ubegrænset TransferQueue baseret på sammenkædede noder
• PriorityBlockingQueue — en ubegrænset blokeringsprioritetskø understøttet af en heap
• PriorityQueue — en prioritetskø baseret på heap-datastrukturen
• SynchronousQueue — en blokerende kø, hvor hver indsættelsesoperation skal vente på en tilsvarende fjernelsesoperation af en anden tråd, og omvendt.

De mest populære implementeringer er LinkedList, ArrayBlockingQueue og PriorityQueue. Lad os se på dem og lave nogle eksempler for bedre forståelse.

LinkedList

Class LinkedList i Java implementerer List og Deque-grænseflader. Så det er en kombination af List og Deque, en tovejskø, der understøtter tilføjelse og fjernelse af elementer fra begge sider. I Java er LinkedList dobbelt-linket List: hvert element i List kalder Node og indeholder et objekt og referencer til to naboobjekter - det forrige og det næste. Du kan sige, at LinkedList ikke er særlig effektiv med hensyn til at bruge hukommelse. Det er sandt, men denne datastruktur kan være nyttig i tilfælde af indsættelse og sletning af operationer. Det sker dog kun, hvis du bruger iteratorer til dem (i dette tilfælde sker det i konstant tid). Adgangsoperationer efter indeks udføres ved at søge fra begyndelsen af ​​slutningen (alt efter hvad der er tættest på) til det ønskede element. Glem dog ikke ekstra omkostninger til lagring af referencer mellem elementer. Så LinkedList er den mest populære køimplementering i Java. Det er også en implementering af List og Deque, og det giver os mulighed for at oprette en tovejskø bestående af alle objekter inklusive null. LinkedList er en samling af elementer.

LinkedList-konstruktører

LinkedList() uden parametre bruges til at konstruere en tom liste. LinkedList(Collection<? udvider E> c) er til at oprette en liste, der indeholder elementerne i den angivne samling, i den rækkefølge, de returneres af samlingens iterator.

Vigtigste LinkedList-metoder:

• add(E element) Tilføjer det angivne element til slutningen af ​​denne liste;
• add(int index, E element) Indsætter elementet ved det angivne positionsindeks;
• get(int index) Returnerer elementet på den angivne position i denne liste;
• remove(int index) Fjerner det element, der er på positionsindeks;
• remove(Object o) Fjerner den første forekomst af ?o element fra denne liste, hvis det er der.
• remove() Henter og fjerner det første element på listen.
• addFirst(), addLast() tilføjer et element til begyndelsen/slutningen af ​​en liste
• clear() fjerner alle elementer fra listen
• indeholder(Objekt o) returnerer sand, hvis listen indeholder o-elementet.
• indexOf(Objekt o) returnerer indekset for den første forekomst af o-elementet, eller -1, hvis det ikke er på listen.
• set(int index, E element) erstatter elementet i indeksposition med elementet
• size()Returnerer antallet af elementer på listen.
• toArray() returnerer et array, der indeholder alle listens elementer fra det første til det sidste element.
• pop() der viser et element fra stakken (repræsenteret af listen)
• push(E e), der skubber et element ind på stakken (repræsenteret af denne liste)

Java Queue Eksempel — LinkedList (sætte og fjerne elementer på forskellige måder)

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

Prioritetskø

PriorityQueue er ikke ligefrem køen i FIFO's generelle betydning. Elementerne i prioritetskøen er ordnet i henhold til deres naturlige rækkefølge, eller af en komparator, der leveres ved køens konstruktionstidspunkt, afhængigt af hvilken konstruktør der bruges. Det er dog ikke en rækkefølge, som den kunne være i lineær struktur såsom liste (fra den største til den mindste eller omvendt). En prioritetskø baseret på en prioritet min heap. Heap er en datastruktur baseret på binært træ. Hver forælders prioritet er større end deres børns prioriteter. Et træ kaldes komplet binært, hvis hver forælder ikke har mere end to børn, og fyldningen af ​​niveauerne går fra top til bund (fra samme niveau - fra venstre mod højre). Binær heap reorganiserer sig selv, hver gang et nyt element tilføjes eller fjernes fra det. I tilfælde af min-heap går det mindste element til roden uanset rækkefølgen af ​​dets indsættelse. Prioritetskø baseret på denne min-heap, så hvis vi har en PriorityQueue af heltal, vil dets første element være det mindste af disse tal. Hvis du sletter roden, bliver den næstmindste en rod.

Prioritetskømetoder:

• boolean add(object) indsætter det angivne element i prioritetskøen. Returnerer sandt i tilfælde af succes. Hvis køen er fuld, giver metoden en undtagelse.
• boolesk tilbud(objekt) indsætter det angivne element i denne prioritetskø. Hvis køen er fuld, returnerer metoden falsk.
• boolean remove(object) fjerner en enkelt forekomst af det angivne element fra denne kø, hvis det er til stede.
• Object poll() henter og fjerner hovedet af denne kø. Returnerer null, hvis køen er tom.
• void clear() fjerner alle elementer fra prioritetskøen.
• Object element() henter hovedet af denne kø uden at fjerne det. Kaster NoSuchElementException, hvis køen er tom.
• Object peek() henter hovedet i køen uden at fjerne det. Returnerer null, hvis køen er tom.
• boolean contains(Object o) returnerer sand, hvis køen indeholder o-elementet.
• int size() returnerer antallet af elementer i denne kø.

Eksempel på 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

Det er vigtigt at forstå, at prioritetskøer er baseret på binære heaps, så de holder ikke elementer i lineær sorteret rækkefølge. Hver vej fra roden til bladet er ordnet, men forskellige veje fra roden er det ikke. Det betyder, at du kan få det minimale element i køen meget hurtigt. Hvis du sletter hovedet hver gang, udskriver du en sorteret struktur.

ArrayBlockingQueue

Intern datastruktur i ArrayBlockingQueueer baseret på et cirkulært array til at gemme elementer. Det er en typisk kø (FIFO) i tilfælde af, at nye elementer indsættes i ende af køen, og udtræksoperationer returnerer et element fra køens hoved. Når først oprettet køkapacitet kan ikke ændres. Forsøg på at indsætte (sætte) et element i en fuld kø fører til blokering af flowet; forsøger at tage et element fra en tom kø blokerer også tråden. Som vi sagde før, er dette array cirkulært. Det betyder, at det første og det sidste element i arrayet behandles logisk ved siden af ​​hinanden. Køen fremfører indekserne for hoved- og haleelementerne, hver gang du sætter elementoen i køen eller fjerner den fra køen. Hvis et eller andet indeks fremrykker det sidste element i arrayet, genstarter det fra 0. Derfor, køen behøver ikke at flytte alle elementer i tilfælde af at hovedet fjernes (som i det sædvanlige array). Men i tilfælde af at et element fjernes fra midten (ved hjælp af Iterator.remove), flyttes elementerne. ArrayBlockingQueue understøtter en yderligere retfærdighedspolitik med fair parameter i konstruktøren for at bestille arbejdet med ventende strømme af producenter (indsættelse af elementer) og forbrugere (udtræk af elementer). Som standard er ordren ikke garanteret. Men hvis køen er oprettet med "fair == true", giver implementeringen af ​​ArrayBlockingQueue-klassen trådadgang i FIFO-rækkefølge. Egenkapital reducerer typisk båndbredden, men reducerer også volatiliteten og forhindrer at løbe tør for ressourcer.

ArrayBlockingQueue Klassekonstruktører

• ArrayBlockingQueue (int kapacitet) opretter en kø med fast kapacitet og med en standardadgangspolitik.
• ArrayBlockingQueue (int kapacitet, boolean fair) opretter en kø med en fast kapacitet og en specificeret adgangspolitik.
• ArrayBlockingQueue (int kapacitet, boolesk fair, Collection <? udvider E> c) opretter en kø med en fast kapacitet specificeret af adgangspolitikken og inkluderer elementer i køen.

Her har vi BlockingQueueExample-eksemplet. Vi opretter en kø af ArrayBlockingQueue med en kapacitet på ét element og et fair flag. To tråde er startet. Den første af dem, Producer-tråd, sætter meddelelser fra meddelelsesarrayet i kø ved hjælp af put-metoden. Den anden tråd, Consumer, læser elementer fra køen ved hjælp af take- metoden og viser dem i konsollen. Rækkefølgen af ​​elementer er den naturlige for køen.

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

Outputtet er køen i naturlig rækkefølge; de to første elementer vises med en forsinkelse. For at styrke det, du har lært, foreslår vi, at du ser en videolektion fra vores Java-kursus

Konklusioner

• Køen bruges til at indsætte elementer i slutningen af ​​køen og fjernes fra begyndelsen af ​​køen. Det følger FIFO-konceptet.
• Java Queue er en del af Collection Framework og implementerer Collection-grænsefladen. Så det understøtter alle metoder til samlingsgrænseflade såsom indsættelse, sletning og så videre.
• De mest anvendte implementeringer af Queue er LinkedList, ArrayBlockingQueue og PriorityQueue.
• Elementerne i prioritetskøen er ordnet i henhold til deres naturlige rækkefølge, eller af en komparator, der leveres ved køens konstruktionstidspunkt, afhængigt af hvilken konstruktør der bruges.
• Hvis der udføres en nul-handling på BlockingQueues, kastes NullPointerException.