Tak, a je tady další datová struktura. Tentokrát si budeme povídat o frontě, což je téměř opak zásobníku, který jsme si popsali v minulém článku. Fronta lze implementovat 2 způsoby (jako zásobník) a to pomocí pole či spojového seznamu. Implementace s použitím spojového seznamu je složitější, a tak si nejprve ukážeme frontu s pomocným polem. Frontu se spojovým seznamem si ukážeme někdy příště.
Fronta je založena na opačné manipulaci s daty, než používá zásobník. Zásobník používá LIFO, zatímco fronta pracuje s daty pomocí FIFO "First In, First Out", neboli první dovnitř, první ven. Tato metoda lze krásně přirovnat k frontě v obchodě. Zákazník, který se jako první zařadí do fronty, bude také první obsloužen a odejde pryč.
Na předchozím obrázku je krásně vidět, že první prvek byl použit a vyřazen jako první.
Implementace do Javy:
public class Queue {
private int size;
private int[] values;
private int front;
private int back;
public Queue(int size) {
this.size = size;
values = new int[size];
}
public void write(int i) {
if(!is_full()) {
back = (back + 1) % size;
values[back] = i;
} else
throw new UnsupportedOperationException("Queue is full!");
}
public int read() {
if(!is_empty()) {
front = (front + 1) % size;
return values[front];
}
return 0;
}
private boolean is_full() {
if(((back + 1) % size) == front)
return true;
else
return false;
}
private boolean is_empty() {
if(front != back)
return false;
else
return true;
}
}
Třída obsahuje 2 soukromé metody, které slouží k ověření plnosti/prázdnosti fronty. Dále obsahuje dvě veřejné metody- read a write. Write slouží k zapsání hodnoty do fronty a read k přečtení aktuálního prvku. Fronta by samozřejmě šla napsat použitelněji, ale tato implementace je podle mého názoru nejsnadší na pochopení.
Příklad použití:
public class Main {
public static void main(String[] args) {
Queue fronta = new Queue(10);
fronta.write(1);
fronta.write(2);
fronta.write(3);
fronta.write(4);
for(int i = 0;i<4;i++) {
System.out.println(fronta.read());
}
}
}
Výpis by vypadal takto:
1
2
3
4
