Här kommer vi att diskutera Java Queue-gränssnittet. Du får reda på vad ködatastruktur är, hur den representeras i Java, vilka metoder som är de viktigaste för alla köer. Också vilka implementeringar av Queue är på Java-språket. Därefter tittar vi närmare på de viktigaste implementeringarna och lär oss dem med exempel.
Ködatastruktur
En kö är en linjär abstrakt datastruktur med den speciella ordningen för att utföra operationer — First In First Out (FIFO). Det betyder att du kan lägga till ett element (eller enqueue, sätta i kön) endast i slutet av strukturen, och ta ett element (avkö eller ta bort från kön) bara från dess början. Du kanske föreställer dig ködatastruktur väldigt enkelt. Det verkar som en kö eller en rad kunder i verkliga livet. Kunden som kom först kommer också att betjänas först. Om du har fyra personer i kö i McDonalds eller någon annanstans, kommer den första som ställer upp att vara den första som får butiken. Om den nya kunden kommer blir han/hon den 5:e i kön för att få hamburgare. Så när du arbetar med en kö läggs nya element till i slutet, och om du vill skaffa ett element kommer det att tas från början. Detta är huvudprincipen för klassiskt ködatastrukturarbete.
Kö i Java
Kö i Java är ett gränssnitt. Enligt Oracles dokumentation har Queue interface 2 supergränssnitt, 4 olika gränssnitt som ärver från kön och en extremt imponerande lista med klasser.
Vad betyder det? Först och främst är Java Queue en del av Collection Framework och implementerar Collection-gränssnittet. Så det stöder alla metoder för samlingsgränssnitt som infogning, radering och så vidare. Queue implementerar Iterable-gränssnitt, som gör att ett objekt kan vara målet för "for-each loop"-satsen.
Kömetoder Java
Kön deklarerar ett antal metoder. Som gränssnittsmetoder bör de finnas representerade i alla klasser som implementerar Queue. De viktigaste kömetoderna, Java:
Boolean offer() – infogar ett nytt element i kön om det är möjligt
Boolean add(E e) – infogar ett nytt element i kön om det är möjligt. Returnerar sant vid framgång och kastar ett IllegalStateException om det inte finns något mellanslag.
Object poll() – hämtar och tar bort ett element från huvudet på. Returnerar null om kön är tom.
Object remove() – hämtar och tar bort ett element från köns huvud.
Object peek() – hämtar, men tar inte bort ett element från huvudet i kön. Returnerar null om kön är tom.
Object element() – hämtar, men tar inte bort ett element från huvudet i kön.
Undergränssnitt till Java Queue
Kögränssnitt ärvs av 4 undergränssnitt – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Du kan dela in dem i 3 grupper: Deques, Blocking Queues och Transfer Queues med BlockingDeque som tillhör de två först. Låt oss ta en glimt av dessa grupper.
Deques
Deque betyder dubblerad kö och stöder tillägg eller borttagning från endera delen av data som en kö (först-in-först-ut/FIFO) eller från huvudet som en annan populär datastruktur som kallas stack ( sist - in- först ut/LIFO). Klasser som implementerar Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Blockerande köer
En blockeringskö är en kö som blockerar en tråd i två fall:
tråden försöker hämta element från en tom kö
tråden försöker sätta element i hela kön
När en tråd försöker hämta objekt från en tom kö, väntar den tills någon annan tråd lägger objekten i kön. På samma sätt, när en tråd försöker sätta element i en full kö, väntar den tills någon annan tråd tar elementen ut ur kön för att få ledigt utrymme för elementen. Visst, begreppet "full kö" innebär att kön har en begränsad storlek, vilket vanligtvis anges i konstruktorn. Standard blockeringsköer inkluderar LinkedBlockingQueue, SynchronousQueue och ArrayBlockingQueue. Implementering av klasser av BlockingQueue- gränssnitt: ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeär ett undergränssnitt för BlockingQueue. BlockingDeque som BlockingQueue är en blockeringskö, men dubbelriktad. Så det ärver egenskaperna hos Deque-gränssnittet. Den är inriktad på multi-threaded exekvering, tillåter inte noll element och kapaciteten kan vara begränsad. Implementeringar av BlockingDeque-gränssnittet blockerar operationen att hämta element om kön är tom, och lägga till ett element i kön om den är full.
Överföringsköer
TransferQueue-gränssnittet utökar BlockingQueue-gränssnittet. Men till skillnad från implementeringen av BlockingQueue-gränssnittsköer, där trådar kan blockeras om kön är tom (läser), eller om kön är full (skriver), blockerar TransferQueue-gränssnittsköer skrivströmmen tills en annan ström hämtar elementet. Använd en överföringsmetod för detta. Med andra ord garanterar implementeringen av BlockingQueue att elementet som skapats av Producenten måste finnas i kön, medan implementeringen av TransferQueue garanterar att Producer-elementet "tas emot" av Konsumenten. Det finns bara en officiell Java-implementering av TransferQueue-gränssnittet - LinkedTransferQueue.
Java Queue Implementationer
Det finns många klasser som implementerar kögränssnitt:
AbstractQueue enligt Queue Java 8 docs, denna abstrakt klass ger grundläggande implementeringar av vissa Queue operationer. Det tillåter inte null-element. Det finns ytterligare 3 metoder för att lägga till, ta bort och element baserat på Queue classical offer , poll , respektive peek . Men de kastar undantag istället för att indikera fel via falska eller noll-returer.
ArrayBlockingQueue — en FIFO-blockeringskö med fast storlek som backas upp av en array
ArrayDeque — storleksändringsbar arrayimplementering av Deque-gränssnittet
ConcurrentLinkedDeque — en obegränsad samtidig deque baserad på länkade noder.
ConcurrentLinkedQueue — en obegränsad trådsäker kö baserad på länkade noder.
DelayQueue — en tidsbaserad schemaläggningskö med stöd av en hög
LinkedBlockingDeque — den samtidiga implementeringen av Deque-gränssnittet.
LinkedBlockingQueue — en valfritt begränsad FIFO-blockeringskö som backas upp av länkade noder
LinkedList — dubbellänkad listimplementering av List- och Deque-gränssnitten. Implementerar alla valfria listoperationer och tillåter alla element (inklusive null)
LinkedTransferQueue — en obegränsad TransferQueue baserad på länkade noder
PriorityBlockingQueue — en obegränsad blockeringsprioritetskö som backas upp av en hög
PriorityQueue — en prioritetskö baserad på heapdatastrukturen
SynchronousQueue — en blockeringskö där varje infogningsoperation måste vänta på en motsvarande borttagningsoperation av en annan tråd, och vice versa.
De mest populära implementeringarna är LinkedList, ArrayBlockingQueue och PriorityQueue. Låt oss titta på dem och göra några exempel för bättre förståelse.
Länkad lista
Class LinkedList i Java implementerar List- och Deque-gränssnitt. Så det är en kombination av List och Deque, en tvåvägskö, som stöder att lägga till och ta bort element från båda sidor. I Java är LinkedList dubbellänkad List: varje element i List anropar Node och innehåller ett objekt och referenser till två angränsande objekt - det föregående och nästa. Du kan säga att LinkedList inte är särskilt effektivt när det gäller att använda minne. Det är sant, men den här datastrukturen kan vara användbar i händelse av att infoga och ta bort operationer. Men det händer bara om du använder iteratorer för dem (i det här fallet sker det konstant). Åtkomstoperationer genom index utförs genom att söka från början av slutet (beroende på vilket som är närmast) till det önskade elementet. Glöm dock inte extra kostnader för att lagra referenser mellan element. Så, LinkedList är den mest populära köimplementeringen i Java. Det är också en implementering av List och Deque och det tillåter oss att skapa en dubbelriktad kö som består av alla objekt inklusive null. LinkedList är en samling element.
LinkedList() utan parametrar används för att konstruera en tom lista. LinkedList(Collection<? utökar E> c) är till för att skapa en lista som innehåller elementen i den angivna samlingen, i ordning de returneras av samlingens iterator.
Huvudmetoder för länkad lista:
add(E element) Lägger till det angivna elementet i slutet av denna lista;
add(int index, E element) Infogar elementet vid det angivna positionsindexet;
get(int index) Returnerar elementet på den angivna positionen i denna lista;
remove(int index) Tar bort elementet som är på positionsindex;
remove(Object o) Tar bort den första förekomsten av elementet ?o från den här listan om det finns där.
remove() Hämtar och tar bort det första elementet i listan.
addFirst(), addLast() lägger till ett element i början/slutet av en lista
clear() tar bort alla element från listan
innehåller(Objekt o) returnerar sant om listan innehåller o-elementet.
indexOf(Objekt o) returnerar indexet för den första förekomsten av elementet o, eller -1 om det inte finns i listan.
set(int index, E element) ersätter elementet i indexposition med elementet
size()Returnerar antalet element i listan.
toArray() returnerar en array som innehåller alla listelement från första till sista elementet.
pop() som visar ett element från stacken (representeras av listan)
push(E e) som skjuter in ett element på stacken (representeras av den här listan)
Java Queue Exempel — LinkedList (sätta och ta bort element på olika sätt)
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 är inte exakt kön i FIFO generella betydelse. Elementen i prioritetskön är ordnade enligt deras naturliga ordning, eller av en komparator som tillhandahålls vid kökonstruktionstiden, beroende på vilken konstruktör som används. Det är dock inte en ordning som den kan vara i linjär struktur såsom lista (från den största till den minsta eller vice versa). En prioritetskö baserad på en prioritetsminhög. Heap är en datastruktur baserad på binärt träd. Varje förälders prioritet är större än deras barns prioriteringar. Ett träd kallas komplett binärt om varje förälder inte har fler än två barn, och fyllningen av nivåerna går från topp till botten (från samma nivå - från vänster till höger). Binary heap omorganiserar sig själv varje gång ett nytt element läggs till eller tas bort från det. Vid min-hög går det minsta elementet till roten oavsett i vilken ordning det infogas. Prioritetskö baserad på denna min-hög, så om vi har en PriorityQueue med heltal, kommer dess första element att vara det minsta av dessa tal. Om du tar bort roten blir den näst minsta en rot.
Prioritetskömetoder:
boolean add(object) infogar det angivna elementet i prioritetskön. Returnerar sant vid framgång. Om kön är full, ger metoden ett undantag.
boolean offer(object) infogar det angivna elementet i denna prioritetskö. Om kön är full returnerar metoden false.
boolean remove(object) tar bort en enda instans av det angivna elementet från den här kön, om det finns.
Object poll() hämtar och tar bort huvudet på denna kö. Returnerar null om kön är tom.
void clear() tar bort alla element från prioritetskön.
Object element() hämtar huvudet på denna kö utan att ta bort det. Kastar NoSuchElementException om kön är tom.
Object peek() hämtar huvudet i kön utan att ta bort det. Returnerar null om kön är tom.
boolean innehåller(Objekt o) returnerar sant om kön innehåller o-elementet.
int size() returnerar antalet element i denna kö.
Exempel 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 är viktigt att förstå att prioriterade köer är baserade på binära högar, så de håller inte element i linjär sorterad ordning. Varje väg från roten till bladet är ordnad, men olika vägar från roten är det inte. Det betyder att du kan få den minimala delen av kön mycket snabbt. Om du tar bort huvudet varje gång kommer du att skriva ut en sorterad struktur.
ArrayBlockingQueue
Intern datastruktur för ArrayBlockingQueueär baserad på en cirkulär array för att lagra element. Det är en typisk kö (FIFO) om nya element infogas längst ner i kön och extraktionsoperationer returnerar ett element från köns huvud. När kökapaciteten väl har skapats kan den inte ändras. Försök att infoga (sätta) ett element i en full kö leder till att flödet blockeras; att försöka ta ett element från en tom kö blockerar också tråden. Som vi sa tidigare är denna array cirkulär. Det betyder att de första och sista elementen i arrayen behandlas logiskt intill varandra. Kön flyttar fram indexen för huvud- och svanselementen varje gång du sätter elementet i kön eller tar bort det från kön. Om något index flyttar fram det sista elementet i arrayen, startar det om från 0. Därför kön behöver inte flytta alla element i händelse av att huvudet tas bort (som i vanlig array). Men om man tar bort ett element från mitten (med Iterator.remove), flyttas elementen. ArrayBlockingQueue stöder en ytterligare rättvisa policy med rättvis parameter i konstruktorn för att ordna arbetet med väntande flöden av producenter (infoga element) och konsumenter (extrahera element). Som standard är beställningen inte garanterad. Men om kön skapas med "fair == true", ger implementeringen av klassen ArrayBlockingQueue trådåtkomst i FIFO-ordning. Equity minskar vanligtvis bandbredden, men minskar också volatiliteten och förhindrar att resurserna tar slut.
ArrayBlockingQueue Class-konstruktörer
ArrayBlockingQueue (int kapacitet) skapar en kö med fast kapacitet och med en standardåtkomstpolicy.
ArrayBlockingQueue (int capacity, boolean fair) skapar en kö med en fast kapacitet och en specificerad åtkomstpolicy.
ArrayBlockingQueue (int kapacitet, boolesk rättvis, Collection <? förlänger E> c) skapar en kö med en fast kapacitet specificerad av åtkomstpolicyn och inkluderar element i kön.
Här har vi exemplet BlockingQueueExample. Vi skapar en kö av ArrayBlockingQueue med en kapacitet på ett element och en rättvis flagga. Två trådar startas. Den första av dem, Producer-tråden, köar meddelanden från meddelandematrisen med put-metoden. Den andra tråden, Consumer, läser element från kön med take -metoden och visar dem i konsolen. Ordningen på element är den naturliga för kön.
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();
}
}
Utdata är kön i naturlig ordning; de två första elementen visas med en fördröjning. För att förstärka det du lärde dig föreslår vi att du tittar på en videolektion från vår Java-kurs
Slutsatser
Kön används för att infoga element i slutet av kön och tar bort från början av kön. Den följer FIFO-konceptet.
Java Queue är en del av Collection Framework och implementerar Collection-gränssnittet. Så det stöder alla metoder för samlingsgränssnitt som infogning, radering och så vidare.
De mest använda implementeringarna av Queue är LinkedList, ArrayBlockingQueue och PriorityQueue.
Elementen i prioritetskön är ordnade enligt deras naturliga ordning, eller av en komparator som tillhandahålls vid kökonstruktionstiden, beroende på vilken konstruktör som används.
Om någon nolloperation utförs på BlockingQueues, kastas NullPointerException.
Så när du arbetar med en kö läggs nya element till i slutet, och om du vill skaffa ett element kommer det att tas från början. Detta är huvudprincipen för klassiskt ködatastrukturarbete.
Du kan säga att LinkedList inte är särskilt effektivt när det gäller att använda minne. Det är sant, men den här datastrukturen kan vara användbar i händelse av att infoga och ta bort operationer. Men det händer bara om du använder iteratorer för dem (i det här fallet sker det konstant). Åtkomstoperationer genom index utförs genom att söka från början av slutet (beroende på vilket som är närmast) till det önskade elementet. Glöm dock inte extra kostnader för att lagra referenser mellan element. Så, LinkedList är den mest populära köimplementeringen i Java. Det är också en implementering av List och Deque och det tillåter oss att skapa en dubbelriktad kö som består av alla objekt inklusive null. LinkedList är en samling element.
GO TO FULL VERSION