INF.04Algorytmika i Struktury Danych
Kolejka FIFO i operacje: Push, Pop, Peek, IsEmpty
Liniowa struktura danych działająca w trybie FIFO (First-In, First-Out), w której nowe elementy dodawane są na końcu, a pobierane z początku, obsługiwana standardowymi metodami.
Zasada działania kolejki FIFO
Kolejka (Queue) to liniowa struktura danych działająca zgodnie z regułą FIFO (First-In, First-Out – pierwszy przybył, pierwszy obsłużony). Element, który został dodany do kolejki jako pierwszy, zostanie jako pierwszy z niej usunięty.
Podstawowe metody i operacje w językach programowania:
| Metoda / Operacja | Znaczenie w kolejce (Queue) | Znaczenie na stosie (Stack - LIFO) | Odpowiednik w C# / Java / C++ |
|---|---|---|---|
push(x) / enqueue(x) | Wstawienie elementu na koniec kolejki | Odłożenie elementu na wierzchołek stosu | C#: queue.Enqueue(x) / stack.Push(x)Java: queue.add(x) / stack.push(x)C++: q.push(x) / s.push(x) |
pop() / dequeue() | Pobranie i usunięcie elementu z początku kolejki | Zdjęcie i usunięcie elementu z wierzchołka stosu | C#: queue.Dequeue() / stack.Pop()Java: queue.poll() / stack.pop()C++: q.pop() / s.pop() |
peek() / top() / front() | Podgląd pierwszego elementu bez jego usuwania | Podgląd elementu na szczycie bez usuwania | C#: queue.Peek() / stack.Peek()Java: queue.peek() / stack.peek()C++: q.front() / s.top() |
isEmpty() / empty() | Sprawdzenie, czy struktura jest pusta (zwraca true / false) | Sprawdzenie, czy stos jest pusty | C#: queue.Count == 0Java: queue.isEmpty()C++: q.empty() |
Złożoność obliczeniowa operacji:
Wszystkie podstawowe operacje na poprawnej implementacji kolejki (lista dowiązana lub bufor cykliczny) wykonują się w stałym czasie O(1).
Pułapki na egzaminie INF.04:
- Na egzaminie często pada pytanie: 'Która metoda zwraca element ze szczytu stosu / początku kolejki bez usuwania go?' – odpowiedź to
peek()(lubtop()/front()). - Próba wywołania
pop()lubpeek()na pustej strukturze powoduje błąd przepełnienia dołu (Underflow /InvalidOperationException).
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Kolejka FIFO i operacje: Push, Pop, Peek, IsEmpty lub rozpocznij trening.