Java Language
Kolejki i Deques

Zastosowanie PriorityQueue

PriorityQueue to struktura danych. Podobnie jak SortedSet , PriorityQueue sortuje również elementy na podstawie ich priorytetów. Elementy, które mają wyższy priorytet, są na pierwszym miejscu. Typ PriorityQueue powinien implementować interfejs comparable lub comparator , którego metody decydują o priorytetach elementów struktury danych.

//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 jako kolejka FIFO

Klasa java.util.LinkedList , podczas gdy implementacja java.util.List jest implementacją interfejsu java.util.Queue ogólnego zastosowania, działającą również na zasadzie FIFO (pierwsze wejście, pierwsze wyjście) .

W poniższym przykładzie z metodą offer() elementy są wstawiane do LinkedList . Ta operacja wstawiania nazywana jest enqueue . W while pętli poniżej, elementy usunięte z Queue podstawie FIFO. Ta operacja nosi nazwę 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() );
}

Dane wyjściowe tego kodu to

first element
second element
third element
fourth element
fifth element

Jak widać na wyjściu, pierwszy wstawiany element „pierwszy element” jest usuwany najpierw, „drugi element” jest usuwany na drugim miejscu itp.

Półki na książki

Co to jest stos?

W Javie stosy są strukturą danych LIFO (Last In, First Out) dla obiektów.

Stos API

Java zawiera interfejs API stosu z następującymi metodami

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

Przykład

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

To zwraca:

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

BlockingQueue to interfejs, który jest kolejką, która blokuje się, gdy próbujesz usunąć z niej kolejkę, a kolejka jest pusta lub jeśli próbujesz kolejkować do niej elementy, a kolejka jest już pełna. Wątek próbujący usunąć z kolejki pustą kolejkę jest blokowany, dopóki jakiś inny wątek nie wstawi elementu do kolejki. Wątek próbujący zakolejkować element w pełnej kolejce jest blokowany, dopóki jakiś inny wątek nie zwolni miejsca w kolejce, albo przez usunięcie z kolejki jednego lub więcej elementów, albo całkowite wyczyszczenie kolejki.

Metody BlockingQueue występują w czterech postaciach, z różnymi sposobami obsługi operacji, których nie można natychmiast spełnić, ale które mogą być spełnione w przyszłości: jeden zgłasza wyjątek, drugi zwraca specjalną wartość (zerową lub fałszywą, w zależności od operacji), trzeci blokuje bieżący wątek na czas nieokreślony, aż operacja się powiedzie, a czwarty blokuje tylko określony maksymalny limit czasu przed poddaniem się.

BlockingQueue może być ograniczony lub nieograniczony . Ograniczona BlockingQueue to taka, która jest inicjowana z początkową pojemnością.

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

Wszelkie wywołania metody put () zostaną zablokowane, jeśli rozmiar kolejki jest równy zdefiniowanej pojemności początkowej.

Nieograniczona kolejka to taka, która jest inicjowana bez pojemności, w rzeczywistości domyślnie jest inicjowana Integer.MAX_VALUE.

Niektóre typowe implementacje BlockingQueue to:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Spójrzmy teraz na przykład 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");

Spowoduje to wydrukowanie:

Entry one done
Entry two done

Wątek zostanie zablokowany po drugim wyjściu.

Interfejs kolejki

Podstawy

Queue to kolekcja do przechowywania elementów przed przetwarzaniem. Kolejki zwykle, ale niekoniecznie, porządkują elementy w FIFO (pierwsze weszło pierwsze wyszło).

Szef kolejki to element, który zostałby usunięty przez wywołanie usunięcia lub odpytania. W kolejce FIFO wszystkie nowe elementy są wstawiane na końcu kolejki.

Interfejs kolejki

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

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Każda metoda Queue istnieje w dwóch formach:

• jeden zgłasza wyjątek, jeśli operacja się nie powiedzie;
• inny zwraca specjalną wartość, jeśli operacja się nie powiedzie ( null lub false zależnie od operacji.

Deque

Deque to „podwójnie zakończona kolejka”, co oznacza, że elementy można dodawać z przodu lub z tyłu kolejki. Tylko kolejka może dodawać elementy do ogona kolejki.

Deque dziedziczy interfejs Queue , co oznacza, że pozostają zwykłe metody, jednak interfejs Deque oferuje dodatkowe metody, aby być bardziej elastycznym z kolejką. Dodatkowe metody naprawdę mówią same za siebie, jeśli wiesz, jak działa kolejka, ponieważ metody te mają na celu zwiększenie elastyczności:

Oczywiście dostępne są te same opcje offer , poll i peek , jednak nie działają one z wyjątkami, ale ze specjalnymi wartościami. Nie ma sensu pokazywać, co tutaj robią.

Dodawanie i dostęp do elementów

Aby dodać elementy do ogona Deque, wywołujesz jego metodę add() . Możesz także użyć addFirst() i addLast() , które dodają elementy do głowy i ogona deque.

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

Możesz zerknąć na element na szczycie kolejki bez wyjmowania elementu z kolejki. Odbywa się to za pomocą metody element() . Możesz także użyć metod getLast() getFirst() i getLast() , które zwracają pierwszy i ostatni element w Deque . Oto jak to wygląda:

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

Usuwanie elementów

Aby usunąć elementy z deque, wywołujesz metody remove() , removeFirst() i removeLast() . Oto kilka przykładów:

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