Implementacja kolejki (FIFO) z operacjami enqueue i dequeue. Zastosowanie: BFS, kolejki zadań.
Kolejka to liniowa struktura danych działająca na zasadzie FIFO (First In, First Out) – kto pierwszy wejdzie, ten pierwszy wyjdzie. Element wstawiony najwcześniej zostaje pobrany jako pierwszy, a każdy nowy czeka na swoją kolej za tymi, które trafiły do niej przed nim.
Kluczowa cecha kolejki to działanie na dwóch przeciwnych końcach. Nowe elementy dokładamy zawsze z tyłu (operacja dodaj, po angielsku enqueue), a zdejmujemy zawsze z przodu (operacja usun, po angielsku dequeue). Dwa różne końce dla wkładania i wyjmowania odpowiadają za to, że kolejność jest zachowana – nic nie może „wepchnąć się" przed elementy, które już czekają.
Analogia: kolejka w sklepie – kto przyszedł pierwszy, ten obsługiwany jest najpierw. Klienci dołączają na końcu, a kasa obsługuje osobę stojącą z przodu.
Kontrast ze stosem: stos działa według reguły LIFO (Last In, First Out) i korzysta tylko z jednego końca – wkłada i zdejmuje elementy z tej samej strony (ze szczytu). Kolejka jest jego przeciwieństwem: dwa różne końce i odwrotna kolejność obsługi. W skrócie: stos oddaje najpierw to, co włożono najpóźniej, a kolejka to, co włożono najwcześniej.
Podstawowe operacje:
dodaj(x) – wkłada element x na koniec kolejki.
usun() – zdejmuje i zwraca element z początku kolejki.
pierwszy() – sprawdza wartość pierwszego elementu, nie zdejmując go.
pusta() – sprawdza czy kolejka nie zawiera elementów.
rozmiar() – zwraca liczbę elementów aktualnie czekających w kolejce.
Implementacja: wydajną kolejkę buduje się na kolejce dwustronnej (deque z modułu collections). Działa ona jak lista dwukierunkowa ze wskaźnikami na oba końce – head (przód) i tail (tył) – dzięki czemu potrafi dokładać i zdejmować elementy z każdej strony bez przechodzenia przez całą strukturę. To właśnie ta możliwość operowania bezpośrednio na obu końcach czyni kolejkę szybką (szczegóły w sekcji ## Złożoność).
Kolejka priorytetowa: specjalna odmiana, w której każdy element ma priorytet i jako pierwszy zdejmowany jest element o najwyższym priorytecie – niezależnie od kolejności wstawiania. Analogia: kobiety w ciąży i osoby starsze mają pierwszeństwo w sklepie.
Algorytmy wykorzystujące kolejkę:
Algorytmy grafowe – przeszukiwanie wszerz (BFS), algorytm Dijkstry (z kolejką priorytetową).
Algorytmy zarządzania procesami – system operacyjny obsługuje procesy w kolejce.
Symulacje – modelowanie systemów obsługi (kolejki w sklepie, ruch sieciowy).
Dodawaj elementy z tyłu, a zdejmuj z przodu (FIFO) – kto pierwszy, ten pierwszy.
Dodaj kilka elementów i obserwuj, jak zmienia się struktura.
// kolejka oparta na liście dynamicznej kolejka ← pusta lista funkcja dodaj(x): // wkładamy element na koniec dodaj x na koniec kolejka funkcja usun(): jeżeli pusta(): zwróć błąd // zdejmujemy z początku x ← kolejka[0] usuń pierwszy element z kolejka zwróć x funkcja pierwszy(): jeżeli pusta(): zwróć błąd zwróć kolejka[0] funkcja pusta(): zwróć długość(kolejka) = 0
# Kolejka to zwykła lista – operacje zapisujemy jako funkcje,
# którym przekazujemy tę listę w argumencie.
def pusta(kolejka):
return len(kolejka) == 0
def dodaj(kolejka, x):
# dokładamy na koniec = na tył kolejki
kolejka.append(x)
def usun(kolejka):
if pusta(kolejka):
return None
# zdejmujemy element z przodu (indeks 0)
return kolejka.pop(0)
def pierwszy(kolejka):
if pusta(kolejka):
return None
return kolejka[0]
# Przykład użycia
kolejka = []
dodaj(kolejka, "Anna")
dodaj(kolejka, "Bartek")
dodaj(kolejka, "Cezary")
print(kolejka)
# Wynik: ['Anna', 'Bartek', 'Cezary']
print(usun(kolejka))
# Wynik: Anna
print(pierwszy(kolejka))
# Wynik: Bartek
print(pusta(kolejka))
# Wynik: FalseO(1)O(n)O(1)W dobrej implementacji wszystkie podstawowe operacje kolejki – dodaj, usun, pierwszy i pusta – wykonują się w czasie stałym O(1). Wynika to wprost z tego, że działamy wyłącznie na końcach struktury: dokładamy z tyłu, zdejmujemy z przodu i nigdy nie musimy niczego przeszukiwać ani przesuwać. Struktura deque ma wskaźniki na oba końce, więc dotarcie do przodu i tyłu jest natychmiastowe, niezależnie od liczby czekających elementów.
Inaczej wygląda to w naiwnej implementacji opartej na zwykłej liście (jak w poniższym kodzie w Pythonie z pop(0)). Wtedy operacja usun() z początku ma złożoność O(n), ponieważ po zabraniu pierwszego elementu wszystkie pozostałe trzeba przesunąć o jedną pozycję w lewo, aby zapełnić powstałą lukę. Im dłuższa kolejka, tym więcej tej pracy – i właśnie dlatego w praktyce sięga się po deque zamiast listy.
Złożoność pamięciowa to O(n) – kolejka przechowuje wszystkie n czekających elementów naraz.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: