Co to jest kolejka FIFO?
Kolejka to struktura danych, w której elementy są obsługiwane w kolejności FIFO (First In, First Out), czyli pierwszy wchodzi, pierwszy wychodzi. Oznacza to, że element dodany jako pierwszy zostanie pobrany jako pierwszy.
Najprostsza analogia to kolejka w sklepie: osoba, która ustawiła się najwcześniej, zostanie obsłużona przed osobami, które przyszły później.
Podstawowe operacje kolejki
Typowa kolejka udostępnia operacje:
- enqueue / dodanie elementu — dodaje element na koniec kolejki,
- dequeue / usunięcie elementu — pobiera i usuwa element z początku kolejki,
- peek / podgląd — sprawdza pierwszy element bez usuwania go,
- count / rozmiar — informuje, ile elementów znajduje się w kolejce.
Przykład w C
Queue<string> kolejka = new Queue<string>();
kolejka.Enqueue("Ala");
kolejka.Enqueue("Bartek");
kolejka.Enqueue("Celina");
Console.WriteLine(kolejka.Dequeue()); // Ala
Console.WriteLine(kolejka.Dequeue()); // Bartek
Element Ala został dodany jako pierwszy, więc został też pierwszy pobrany.
FIFO a LIFO
Kolejkę FIFO należy odróżnić od struktury LIFO (Last In, First Out), czyli stosu. W stosie jako pierwszy pobierany jest element dodany jako ostatni.
Zastosowania kolejki
Kolejki są używane m.in. do:
- obsługi zadań w kolejności zgłoszeń,
- buforowania danych,
- kolejkowania wydruków,
- obsługi komunikatów w systemach informatycznych,
- algorytmów grafowych, np. BFS.
W pytaniach egzaminacyjnych hasło FIFO najczęściej oznacza właśnie kolejkę.