Kö

För de flesta leder ordet "kö" tankarna till väldigt få trevliga associationer. Men idag pratar vi om olika köer — Java-köer. I Java är en kö allt som ärver Queue -gränssnittet, vilket i sin tur utökar Collection- gränssnittet. Det betyder att köer kan behandlas som samlingar.

Köer i Java stöder två driftsprinciper: FIFO och LIFO .

FIFO - principen (First In, First Out) styr en vanlig kö — det första elementet som läggs till i kön är det första som lämnar den.

LIFO - principen (Last In, First Out) beskriver beteendet hos en stack — det sista elementet som läggs till i kön är det första som lämnar den. Till exempel är det så här du arbetar med en kortlek: du tar bort korten från toppen ett i taget tills du når botten av kortleken.

Köhierarkin i Java ser ut så här:

Här kan du se att Queue har 3 implementeringsklasser: LinkedList , ArrayDeque och PriorityQueue . LinkedList och ArrayDeque ärver inte Queue direkt utan Deque .

Deque är ett gränssnitt som lades till i Java 6. Det innehåller flera metoder som är användbara för köer och låter en kö fungera som en dubbeländad (eller dubbelriktad) kö. Det betyder att det kan varaFIFOochLIFO.

En av Deque -gränssnittets två avkomlingar är ArrayDeque . Den stöder en dubbeländad kö som låter dig infoga och ta bort element från båda ändarna. Det är också en dynamisk array som automatiskt växer i storlek.

Det finns också en PriorityQueue- klass, som är en direkt ättling till Queue : den beter sig annorlunda än de klasser som implementerar Deque .

PriorityQueue är en prioritetskö som organiserar element enligt deras naturliga ordning som standard. Här använder sorteringengränssnitten Comparable och Comparator . Principen är densamma som med TreeSet eller TreeMap — klasser som använder det jämförbara gränssnittet och har sin egen sorteringsordning.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Om du kör det här exemplet ser du det här i konsolen:

Eftersom vi arbetar med köer och inte vanliga samlingar måste vi ta bort elementen från listan. För att göra detta använder vi denna konstruktion:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Deque - gränssnittet ärver Queue -metoderna och lägger till flera av sina egna intressanta metoder:

Låt oss nu titta på några av dessa metoder i praktiken.

Låt oss först lägga till ett element i en kö:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        System.out.println(deque);
    

Låt oss nu hämta värden från en kö:

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The first element is: "+ deque.getFirst());
                          
        System.out.println("The last element is: " + deque.getLast());
                          
    }
    

Denna kod visar det första och sista elementet i kön.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);
    

När vi kör den här koden får vi:

Skillnaden mellan pop() och poll() är att pop() kommer att kasta ett NoSuchElementException om listan är tom lista, men poll() kommer att returnera null .

Nu ska vi överväga metoderna pollFirst() och pollLast() .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);
    

Båda metoderna returnerar och tar bort ett värde från kön.

Här är ett exempel på hur du använder metoderna peekFirst() och peekLast() :

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Båda metoderna returnerar det första/sista elementet från kön och tar inte bort dem. Om kön är tom kommer null att returneras.

Bra gjort! Idag har vi lärt oss hur man arbetar med köer i Java. Nu vet du hur du använder dem i praktiken.