Her skal vi diskutere Java Queue-grensesnittet. Du vil finne ut hva kødatastruktur er, hvordan den er representert i Java, hvilke metoder som er de viktigste for alle køer. Også hvilke implementeringer av Queue er på Java-språket. Etter det ser vi nærmere på de viktigste implementeringene og lærer dem med eksempler.
Kødatastruktur
En kø er en lineær abstrakt datastruktur med den spesielle rekkefølgen for å utføre operasjoner - First In First Out (FIFO). Det betyr at du kan legge til et element (eller kø, sette i køen) bare på slutten av strukturen, og ta et element (avkø eller fjerne fra køen) bare fra begynnelsen. Du kan tenke deg kødatastruktur veldig enkelt. Det virker som en kø eller en rekke kunder i det virkelige liv. Kunden som kom først, kommer også til å bli servert først. Hvis du har fire personer i kø i McDonalds eller andre steder, vil den første som stiller opp være den første som får butikken. Kommer den nye kunden vil han/hun være den 5. i køen for å få hamburgere. Så mens du jobber med en kø, blir nye elementer lagt til på slutten, og hvis du ønsker å få et element, vil det bli tatt fra begynnelsen. Dette er hovedprinsippet for klassisk kødatastrukturarbeid.
Kø i Java
Kø i Java er et grensesnitt. I følge Oracle-dokumentasjonen har Queue-grensesnittet 2 supergrensesnitt, 4 forskjellige grensesnitt som arver fra køen, og en ekstremt imponerende liste over klasser.
Hva betyr det? Først av alt er Java Queue en del av Collection Framework og implementerer Collection-grensesnittet. Så det støtter alle metoder for samlingsgrensesnitt som innsetting, sletting og så videre. Queue implementerer Iterable-grensesnitt, som lar et objekt være målet for "for-each loop"-setningen.
Kømetoder Java
Køen erklærer en rekke metoder. Som grensesnittmetoder bør de være representert i alle klasser som implementerer Queue. De viktigste kømetodene, Java:
Boolsk tilbud() – setter inn et nytt element i køen hvis det er mulig
Boolean add(E e) – setter inn et nytt element i køen hvis det er mulig. Returnerer true i tilfelle suksess og kaster et IllegalStateException hvis det ikke er mellomrom.
Object poll() – henter og fjerner et element fra hodet til. Returnerer null hvis køen er tom.
Object remove() – henter og fjerner et element fra toppen av køen.
Object peek() – henter, men fjerner ikke et element fra toppen av køen. Returnerer null hvis køen er tom.
Object element() – henter, men fjerner ikke et element fra toppen av køen.
Undergrensesnitt til Java Queue
Køgrensesnitt arves av 4 undergrensesnitt – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Du kan dele dem inn i 3 grupper: Deques, Blocking Queue og Transfer Queue med BlockingDeque som tilhører de to først. La oss ta et glimt av disse gruppene.
Deques
Deque betyr doblet avsluttet kø og støtter tillegg eller fjerning fra en av delene av dataene som en kø (først-inn-først-ut/FIFO) eller fra hodet som en annen populær datastruktur kalt stack ( sist -inn- først ut/LIFO). Klasser som implementerer Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Blokkering av køer
En blokkeringskø er en kø som blokkerer en tråd i to tilfeller:
tråden prøver å hente elementer fra en tom kø
tråden prøver å sette elementer i hele køen
Når en tråd prøver å hente elementer fra en tom kø, venter den til en annen tråd setter elementene inn i køen. På samme måte, når en tråd prøver å sette elementer inn i en full kø, venter den til en annen tråd tar elementene ut av køen for å få ledig plass til elementene. Visst, konseptet "full kø" innebærer at køen har en begrenset størrelse, som vanligvis er spesifisert i konstruktøren. Standard blokkeringskøer inkluderer LinkedBlockingQueue, SynchronousQueue og ArrayBlockingQueue. Implementering av klasser av BlockingQueue- grensesnitt: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeer et undergrensesnitt for BlockingQueue. BlockingDeque som BlockingQueue er en blokkeringskø, men toveis. Så det arver egenskapene til Deque-grensesnittet. Den er orientert mot flertrådsutførelse, tillater ikke null elementer og kapasiteten kan være begrenset. Implementeringer av BlockingDeque-grensesnittet blokkerer operasjonen med å hente elementer hvis køen er tom, og legge til et element i køen hvis den er full.
Overføringskøer
TransferQueue-grensesnittet utvider BlockingQueue-grensesnittet. Men i motsetning til implementeringen av BlockingQueue-grensesnittkøer, der tråder kan blokkeres hvis køen er tom (leser), eller hvis køen er full (skriver), blokkerer TransferQueue-grensesnittkøer skrivestrømmen til en annen strøm henter elementet. Bruk en overføringsmetode for dette. Med andre ord garanterer implementeringen av BlockingQueue at elementet opprettet av Produsenten må stå i køen, mens implementeringen av TransferQueue garanterer at Produsent-elementet blir "mottatt" av Forbrukeren. Det er bare én offisiell Java-implementering av TransferQueue-grensesnittet - LinkedTransferQueue.
Java-køimplementeringer
Det er mange klasser som implementerer Queue-grensesnitt:
AbstractQueue i henhold til Queue Java 8 docs, gir denne abstrakte klassen grunnleggende implementeringer av noen køoperasjoner. Den tillater ikke null-elementer. Det er 3 flere metoder for å legge til, fjerne og element basert på henholdsvis Queue klassisk tilbud , avstemning og kikk . Imidlertid kaster de unntak i stedet for å indikere feil via falske eller null-retur.
ArrayBlockingQueue — en FIFO-blokkeringskø med fast størrelse støttet av en matrise
ArrayDeque — array-implementering som kan endre størrelsen på Deque-grensesnittet
ConcurrentLinkedDeque — en ubegrenset samtidig deque basert på koblede noder.
ConcurrentLinkedQueue — en ubegrenset trådsikker kø basert på koblede noder.
DelayQueue - en tidsbasert planleggingskø støttet av en haug
LinkedBlockingDeque — den samtidige implementeringen av Deque-grensesnittet.
LinkedBlockingQueue — en valgfritt avgrenset FIFO-blokkeringskø støttet av koblede noder
LinkedList — dobbeltkoblet listeimplementering av List- og Deque-grensesnittene. Implementerer alle valgfrie listeoperasjoner, og tillater alle elementer (inkludert null)
LinkedTransferQueue — en ubegrenset TransferQueue basert på koblede noder
PriorityBlockingQueue — en ubegrenset blokkeringsprioritetskø støttet av en haug
PriorityQueue — en prioritetskø basert på haugdatastrukturen
SynchronousQueue — en blokkeringskø der hver innsettingsoperasjon må vente på en tilsvarende fjerningsoperasjon av en annen tråd, og omvendt.
De mest populære implementeringene er LinkedList, ArrayBlockingQueue og PriorityQueue. La oss se på dem og ta noen eksempler for bedre forståelse.
LinkedList
Class LinkedList i Java implementerer List og Deque-grensesnitt. Så det er en kombinasjon av List og Deque, en toveis kø, som støtter å legge til og fjerne elementer fra begge sider. I Java er LinkedList dobbeltkoblet List: hvert element i List kaller Node og inneholder et objekt og referanser til to naboobjekter - det forrige og det neste. Du kan si at LinkedList ikke er veldig effektiv når det gjelder bruk av minne. Det er sant, men denne datastrukturen kan være nyttig i tilfelle ytelsen til innsetting og sletting. Det skjer imidlertid bare hvis du bruker iteratorer for dem (i dette tilfellet skjer det i konstant tid). Tilgangsoperasjoner etter indeks utføres ved å søke fra begynnelsen av slutten (det som er nærmest) til ønsket element. Men ikke glem ekstra kostnader for lagring av referanser mellom elementer. Så, LinkedList er den mest populære køimplementeringen i Java. Det er også en implementering av List og Deque, og det lar oss lage en toveis kø bestående av alle objekter inkludert null. LinkedList er en samling av elementer.
LinkedList() uten parametere brukes til å konstruere en tom liste. LinkedList(Collection<? utvider E> c) er for å lage en liste som inneholder elementene i den spesifiserte samlingen, i rekkefølge de returneres av samlingens iterator.
Hovedmetoder for lenket liste:
add(E element) Legger til det spesifiserte elementet på slutten av denne listen;
add(int index, E element) Setter inn elementet ved den angitte posisjonsindeksen;
get(int index) Returnerer elementet på den angitte posisjonen i denne listen;
remove(int index) Fjerner elementet som er på posisjonsindeks;
remove(Object o) Fjerner den første forekomsten av ?o-elementet fra denne listen hvis det er der.
remove() Henter og fjerner det første elementet i listen.
addFirst(), addLast() legger til et element i begynnelsen/slutten av en liste
clear() fjerner alle elementer fra listen
inneholder(Objekt o) returnerer sann hvis listen inneholder o-elementet.
indeksOf(Objekt o) returnerer indeksen for den første forekomsten av o-elementet, eller -1 hvis det ikke er i listen.
set(int index, E element) erstatter elementet i indeksposisjon med elementet
size()Returnerer antallet elementer i listen.
toArray() returnerer en matrise som inneholder alle listens elementer fra første til siste element.
pop() som spretter et element fra stabelen (representert av listen)
push(E e) som skyver et element inn på stabelen (representert av denne listen)
Java Queue Eksempel - LinkedList (sette og fjerne elementer på forskjellige måter)
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 akkurat køen i FIFO generell betydning. Elementene i prioritetskøen er ordnet i henhold til deres naturlige rekkefølge, eller av en komparator som leveres ved købyggingstid, avhengig av hvilken konstruktør som brukes. Imidlertid er det ikke en rekkefølge som det kan være i lineær struktur som liste (fra den største til den minste eller omvendt). En prioritert kø basert på en prioritet min haug. Heap er en datastruktur basert på binært tre. Hver forelders prioritet er høyere enn barnas prioriteringer. Et tre kalles fullstendig binært hvis hver forelder ikke har mer enn to barn, og fyllingen av nivåene går fra topp til bunn (fra samme nivå - fra venstre til høyre). Binær haug omorganiserer seg selv hver gang et nytt element legges til eller fjernes fra det. I tilfelle av min-heap, går det minste elementet til roten uavhengig av rekkefølgen på innsettingen. Prioritetskø basert på denne min-haugen, så hvis vi har en PriorityQueue med heltall, vil dets første element være det minste av disse tallene. Hvis du sletter roten, blir den nest minste en rot.
Prioritetskømetoder:
boolean add(object) setter inn det spesifiserte elementet i prioritetskøen. Returnerer sann ved suksess. Hvis køen er full, gir metoden et unntak.
boolesk tilbud(objekt) setter inn det spesifiserte elementet i denne prioriterte køen. Hvis køen er full, returnerer metoden false.
boolean remove(object) fjerner en enkelt forekomst av det spesifiserte elementet fra denne køen, hvis den er til stede.
Object poll() henter og fjerner hodet på denne køen. Returnerer null hvis køen er tom.
void clear() fjerner alle elementer fra prioritetskøen.
Object element() henter hodet til denne køen uten å fjerne den. Kaster NoSuchElementException hvis køen er tom.
Object peek() henter lederen av køen uten å fjerne den. Returnerer null hvis køen er tom.
boolean contains(Object o) returnerer true hvis køen inneholder o-elementet.
int size() returnerer antall elementer i denne køen.
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 viktig å forstå at prioriterte køer er basert på binære hauger, så de holder ikke elementer i lineær sortert rekkefølge. Hver vei fra roten til bladet er ordnet, men forskjellige veier fra roten er det ikke. Det betyr at du kan få det minimale elementet i køen veldig raskt. Hvis du sletter hodet hver gang, vil du skrive ut en sortert struktur.
ArrayBlockingQueue
Intern datastruktur i ArrayBlockingQueueer basert på en sirkulær matrise for å lagre elementer. Det er en typisk kø (FIFO) i tilfelle nye elementer settes inn på slutten av køen, og utvinningsoperasjoner returnerer et element fra toppen av køen. Når først opprettet køkapasitet kan ikke endres. Forsøk på å sette inn (sette) et element i en full kø fører til blokkering av flyten; prøver å ta et element fra en tom kø blokkerer også tråden. Som vi sa før, er denne matrisen sirkulær. Det betyr at de første og siste elementene i matrisen behandles logisk ved siden av hverandre. Køen fremmer indeksene til hode- og haleelementene hver gang du setter elementet inn i køen eller fjerner det fra køen. Hvis en eller annen indeks går videre til det siste elementet i matrisen, starter den på nytt fra 0. Derfor køen trenger ikke å flytte alle elementene i tilfelle hodet fjernes (som i vanlig array). Men i tilfelle du fjerner et element fra midten (ved hjelp av Iterator.remove), blir elementene forskjøvet. ArrayBlockingQueue støtter en ekstra rettferdighetspolicy med rettferdig parameter i konstruktøren for å bestille arbeidet med ventestrømmer av produsenter (sette inn elementer) og forbrukere (uttrekke elementer). Som standard er ikke bestillingen garantert. Men hvis køen er opprettet med "fair == true", gir implementeringen av ArrayBlockingQueue-klassen trådtilgang i FIFO-rekkefølge. Egenkapital reduserer vanligvis båndbredden, men reduserer også volatiliteten og forhindrer at ressurser går tom.
ArrayBlockingQueue Klassekonstruktører
ArrayBlockingQueue (int kapasitet) oppretter en kø med fast kapasitet og med en standard tilgangspolicy.
ArrayBlockingQueue (int capacity, boolean fair) oppretter en kø med en fast kapasitet og en spesifisert tilgangspolicy.
ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) oppretter en kø med en fast kapasitet spesifisert av tilgangspolicyen og inkluderer elementer i køen.
Her har vi BlockingQueueExample-eksemplet. Vi lager en kø av ArrayBlockingQueue med en kapasitet på ett element og et rettferdig flagg. To tråder er startet. Den første av dem, Produsent-tråd, setter meldinger fra meldingsmatrisen i kø ved å bruke put-metoden. Den andre tråden, Consumer, leser elementer fra køen ved å bruke take- metoden og viser dem i konsollen. Rekkefølgen på 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();
}
}
Utgangen er køen i naturlig rekkefølge; de to første elementene vises med en forsinkelse. For å forsterke det du lærte, foreslår vi at du ser en videoleksjon fra vårt Java-kurs
Konklusjoner
Køen brukes til å sette inn elementer på slutten av køen og fjernes fra begynnelsen av køen. Den følger FIFO-konseptet.
Java Queue er en del av Collection Framework og implementerer Collection-grensesnittet. Så det støtter alle metoder for samlingsgrensesnitt som innsetting, sletting og så videre.
De mest brukte implementeringene av Queue er LinkedList, ArrayBlockingQueue og PriorityQueue.
Elementene i prioritetskøen er ordnet i henhold til deres naturlige rekkefølge, eller av en komparator som leveres ved købyggingstid, avhengig av hvilken konstruktør som brukes.
Hvis en null-operasjon utføres på BlockingQueues, kastes NullPointerException.
Så mens du jobber med en kø, blir nye elementer lagt til på slutten, og hvis du ønsker å få et element, vil det bli tatt fra begynnelsen. Dette er hovedprinsippet for klassisk kødatastrukturarbeid.
Du kan si at LinkedList ikke er veldig effektiv når det gjelder bruk av minne. Det er sant, men denne datastrukturen kan være nyttig i tilfelle ytelsen til innsetting og sletting. Det skjer imidlertid bare hvis du bruker iteratorer for dem (i dette tilfellet skjer det i konstant tid). Tilgangsoperasjoner etter indeks utføres ved å søke fra begynnelsen av slutten (det som er nærmest) til ønsket element. Men ikke glem ekstra kostnader for lagring av referanser mellom elementer. Så, LinkedList er den mest populære køimplementeringen i Java. Det er også en implementering av List og Deque, og det lar oss lage en toveis kø bestående av alle objekter inkludert null. LinkedList er en samling av elementer.
GO TO FULL VERSION