Fronta

Fronta je jedním ze základních datových typů a slouží k ukládání a výběru dat takovým způsobem, aby prvek, který byl uložen jako první, byl také jako první vybrán. Tomuto principu se říká FIFO - first in, fist out. Opačný přístup - LIFO - last in, first out - používá datový typ zásobník.

Speciálním případem fronty je tzv. prioritní fronta, ve které mohou prvky s vyšší prioritou předbíhat na výstupu ty s nižší prioritou.

Typické operace

Fronta

addLast (enqueue) – Vloží prvek do fronty.
deleteFirst (poll, dequeue) – Získá a odstraní první prvek (hlavu) fronty.
getFirst (peek) – Získá první prvek fronty.
isEmpty – Dotaz na prázdnost fronty.
size – Vrátí počet obsažených prvků.

Využití

Fronta má v informatice široké využití, toto jsou některé příklady:

Synchronizační primitivum
Operátor roura (pipe) - komunikace mezi procesy v operačních systémech
Kruhový buffer - vyrovnávací paměť pro datové toky
Řazení prioritní frotou (haldou) - heapsort

Kód

Java

 /**
  * Fronta - implementovana jako spojovy seznam
  */
 public class Queue {
     private Node first;
     private Node last;
     private int size;
     public Queue() {
         this.size = 0;
     }
 
     /**
      * Prida na konec fronty prvek - asymptoticka sloztitost O(1)
      * @param i prvek k vlozeni
      */
     public void addLast(int i) {
         Node n = new Node(i);
         if(getSize() == 0) {
             this.first = n;
             this.last = n;
         } else {
             this.last.next = n;
             this.last = n;
         }
         size++;     
     }
 
     /**
      * Odebere z fronty prvni prvek - asymptoticka sloztitost O(1)
      * @return prvni prvek
      */
     public int deteteFirst() {
         if(getSize() == 0) throw new IllegalStateException("Fronta je prazdna");
         int value = first.value;
         first = first.next;
         size--;
         return value;
     }
     /**
      * Vrati prvni prvek fronty 
      * @return prvni prvek
      */
     public int getFirst() {
         if(getSize() == 0) throw new IllegalStateException("Fronta je prazdna");
         return first.value;
     }
     /**
      * Getter na delku
      * @return delka fronty
      */
     public int getSize() {
         return size;
     }
     
     /**
      * Dotaz pra prazdnost
      * @return true, pokud je fronta prazdna
      */
     public boolean isEmpty() {
         return this.size == 0;
     }
 
     /**
      * Klasicka toString metoda, vraci textovou reprezentaci objektu
      * @return textova reprezentace objektu
      */
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
         Node curr = first;
         for(int i = 0;  i < this.size; i++) {
             builder.append(curr.value).append(" ");
             curr = curr.next;
         }
         return builder.toString();
     }  
 
     /**
      * Vnitrni reprezentace prvku
      */
     private class Node {
         private int value;
         private Node next;
         private Node(int value) {
             this.value = value;
         }
     }    
 }

Typické operace

Využití

Kód

Doporučujeme