Java Language
Köer och deques

Användningen av PriorityQueue

PriorityQueue är en datastruktur. Precis som SortedSet sorterar PriorityQueue också sina element baserat på deras prioriteringar. Elementen, som har högre prioritet, kommer först. Typen av PriorityQueue bör implementera ett comparable gränssnitt eller comparator , vars metoder avgör prioriteringarna för elementen i datastrukturen.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

LinkedList som en FIFO-kö

java.util.LinkedList , medan implementeringen av java.util.List är ett allmänt genomförande av java.util.Queue gränssnittet som fungerar för en FIFO- princip (First In, First Out) .

I exemplet nedan, med offer() -metoden, införs elementen i LinkedList . Denna insättningsoperation kallas enqueue . I while slingan nedan tas elementen bort från Queue baserat på FIFO. Denna operation kallas dequeue .

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

Utgången från denna kod är

first element
second element
third element
fourth element
fifth element

Såsom framgår av utgången tas det första insatta elementet "första elementet" bort, "andra elementet" tas bort på andra plats etc.

Stacks

Vad är en stack?

I Java är Stacks en LIFO (Last In, First Out) datastruktur för objekt.

Stack API

Java innehåller ett stack-API med följande metoder

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

Exempel

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

Detta returnerar:

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

En BlockingQueue är ett gränssnitt, som är en kö som blockeras när du försöker ta bort från den och kön är tom, eller om du försöker att förlägga objekt till den och kön redan är full. En tråd som försöker ta bort från en tom kö är blockerad tills någon annan tråd sätter in ett objekt i kön. En tråd som försöker markera ett objekt i en fullständig kö är blockerad tills någon annan tråd skapar utrymme i kön, antingen genom att ta bort ett eller flera objekt eller rensa kön helt.

BlockingQueue-metoder finns i fyra former, med olika sätt att hantera operationer som inte kan uppfyllas omedelbart, men som kan vara nöjda vid någon tidpunkt i framtiden: en kastar ett undantag, den andra ger ett specialvärde (antingen noll eller falsk, beroende på operation), den tredje blockerar den aktuella tråden på obestämd tid tills operationen kan lyckas, och den fjärde blockerar endast en given maximal tidsgräns innan den ger upp.

En BlockingQueue kan vara begränsad eller obegränsad . En avgränsad BlockingQueue är en som initialiseras med initial kapacitet.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

Eventuella samtal till en put () -metod kommer att blockeras om storleken på kön är lika med den definierade initiala kapaciteten.

En obegränsad kö är en som initieras utan kapacitet, faktiskt som standard initierad med Integer.MAX_VALUE.

Några vanliga implementeringar av BlockingQueue är:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Låt oss nu titta på ett exempel på ArrayBlockingQueue :

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

Detta kommer att skriva ut:

Entry one done
Entry two done

Och tråden kommer att blockeras efter den andra utgången.

Kögränssnitt

Grunderna

En Queue är en samling för att hålla element före bearbetning. Köer ordnar, men inte nödvändigtvis, element på ett FIFO-sätt (först-in-först-ut).

Köhuvudet är det element som skulle tas bort genom ett samtal om att ta bort eller polla. I en FIFO-kö införs alla nya element i köens svans.

Kögränssnittet

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Varje Queue finns i två former:

• man kastar ett undantag om operationen misslyckas;
• andra returnerar ett specialvärde om åtgärden misslyckas (antingen null eller false beroende på operationen.

Deque

En Deque är en "dubbel slutad kön" vilket innebär att ett element kan läggas framtill eller i köens svans. Kön kan bara lägga till element i svans i en kö.

Den Deque ärver Queue gränssnittet vilket innebär de vanliga metoder förblir emellertid de Deque gränssnittet erbjuder ytterligare metoder för att vara mer flexibel med en kö. De ytterligare metoderna talar verkligen för sig själv om du vet hur en kö fungerar, eftersom dessa metoder är avsedda att ge mer flexibilitet:

Naturligtvis finns samma alternativ för offer , poll och peek , men de fungerar inte med undantag utan snarare med specialvärden. Det finns ingen mening med att visa vad de gör här.

Lägga till och komma åt element

För att lägga till element i svansen i en Deque kallar du dess add() -metod. Du kan också använda addFirst() och addLast() -metoderna, som lägger till element i huvudet och svansen på teckningen.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

Du kan kika på elementet i könens huvud utan att ta elementet ur kön. Detta görs via metoden element() . Du kan också använda getFirst() och getLast() -metoderna, som returnerar det första och sista elementet i Deque . Så här ser det ut:

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

Ta bort element

För att ta bort element från en täckning kallar du metoden remove remove() , removeFirst() och removeLast() . Här är några exempel:

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();