Kolejka (FIFO) - implementacja i przykłady użycia
1. Czym jest kolejka?
Kolejka (queue) to abstrakcyjna struktura danych działająca na zasadzie FIFO (First In, First Out) – pierwszy element wchodzi, pierwszy wychodzi.
Analogia ze świata rzeczywistego:
Wyobraź sobie kolejkę w sklepie: - Nowe osoby dołączają z tyłu kolejki - Obsługiwane są osoby z przodu kolejki - Nie możesz "wskoczyć" w środek kolejki
Wizualizacja:
Enqueue (dodaj) Dequeue (usuń)
↓ ↓
┌───┬───┬───┬───┬───┐
│ 9 │ 5 │ 3 │ 1 │ │
└───┴───┴───┴───┴───┘
REAR FRONT
(tył) (przód)
2. Podstawowe operacje
| Operacja | Opis | Złożoność |
|---|---|---|
| enqueue(x) | Dodaje element na końcu kolejki | O(1) |
| dequeue() | Usuwa i zwraca element z przodu | O(1)* |
| peek() | Zwraca element z przodu (bez usuwania) | O(1) |
| is_empty() | Sprawdza, czy kolejka jest pusta | O(1) |
| size() | Zwraca liczbę elementów | O(1) |
*zależy od implementacji
3. Implementacja z użyciem collections.deque
Najlepsza implementacja w Pythonie – zoptymalizowana w C.
Użycie:
4. Implementacja z użyciem listy pythonowej (NIEWYDAJNE!)
Problem: list.pop(0) to O(n), bo musi przesunąć wszystkie elementy!
5. Implementacja z użyciem listy jednokierunkowej
Zalety: - Wszystkie operacje O(1) - Dynamiczny rozmiar - Brak przepełnienia
6. Implementacja kolejki cyklicznej (Circular Queue)
Wykorzystuje tablicę stałego rozmiaru z wskaźnikami front i rear.
Użycie:
Zastosowania: - Bufory cykliczne - Pula zasobów (connection pool) - Systemy czasu rzeczywistego
7. Praktyczne zastosowania kolejki
7.1. Obsługa zadań w drukarce
7.2. BFS (Breadth-First Search) – przeszukiwanie grafu
7.3. Najkrótsza ścieżka w grafie (BFS)
7.4. System obsługi klientów (call center)
7.5. Przetwarzanie wsadowe (Batch Processing)
7.6. Symulacja obsługi klientów w sklepie
8. Kolejka priorytetowa (wprowadzenie)
Kolejka priorytetowa – elementy z wyższym priorytetem są obsługiwane pierwsze.
9. Porównanie implementacji
| Implementacja | Enqueue | Dequeue | Pamięć | Zalety |
|---|---|---|---|---|
collections.deque |
O(1) | O(1) | O(n) | Najszybsza, prosta |
| Lista pythonowa | O(1) | O(n) | O(n) | Prosta (ale wolna!) |
| Lista jednokierunkowa | O(1) | O(1) | O(n) | Edukacyjna |
| Kolejka cykliczna | O(1) | O(1) | O(capacity) | Stały rozmiar |
Rekomendacja: Używaj collections.deque w praktyce!
10. Złożoność czasowa i pamięciowa
Złożoność czasowa (z deque):
| Operacja | Złożoność |
|---|---|
enqueue(x) |
O(1) |
dequeue() |
O(1) |
peek() |
O(1) |
is_empty() |
O(1) |
size() |
O(1) |
Złożoność pamięciowa:
- O(n) – gdzie n to liczba elementów w kolejce
11. Typowe błędy
Błąd 1: Użycie list.pop(0) dla kolejki
Błąd 2: Dequeue z pustej kolejki
12. Kolejka vs Stos
| Cecha | Kolejka (FIFO) | Stos (LIFO) |
|---|---|---|
| Zasada | Pierwszy in, pierwszy out | Ostatni in, pierwszy out |
| Dodawanie | Na końcu (rear) | Na górze (top) |
| Usuwanie | Z przodu (front) | Z góry (top) |
| Zastosowania | BFS, zadania, obsługa | DFS, undo, parsowanie |
| Analogia | Kolejka w sklepie | Stos talerzy |
13. Podsumowanie
Kolejka to fundamentalna struktura danych FIFO:
- Wszystkie operacje O(1) (z
deque) - Naturalna dla zadań sekwencyjnych
- Kluczowa dla BFS i wielu algorytmów
- Szeroko wykorzystywana w systemach
Kluczowe zastosowania:
- BFS (przeszukiwanie grafu wszerz)
- Obsługa zadań (drukarki, serwery)
- Symulacje (kolejki klientów)
- Przetwarzanie wsadowe
- Systemy czasu rzeczywistego
Kiedy używać kolejki:
- FIFO (pierwszy wchodzi, pierwszy wychodzi)
- Obsługa zadań w kolejności
- BFS (przeszukiwanie wszerz)
- Przetwarzanie strumieniowe
- Bufory danych
Co dalej warto poznać:
- Kolejka priorytetowa (heap)
- Deque (kolejka dwustronna)
- Algorytmy grafowe (BFS, najkrótsza ścieżka)
- Systemy kolejkowe (message queues)