Algoritmy.net > Datové struktury > Fronta
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
Kód
/**
* 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;
}
}
}
