Kolejka i lista — Flawiusz i porządek leksykograficzny

🎯 Po co Ci to?

Stos obsługiwał ostatniego pierwszego — ale świat częściej działa sprawiedliwie: kto pierwszy, ten pierwszy. Kolejka do kasy, zadania drukarki, pakiety w routerze, obsługa zgłoszeń — wszędzie rządzi FIFO. A lista wiązana to struktura, która naprawia największą słabość tablicy (drogie wstawianie w środek) genialnie prostym pomysłem: niech elementy trzymają się za ręce zamiast leżeć pod kolejnymi adresami. Poznasz obie, a przy okazji rozwiążesz dwutysiącletnią zagadkę Flawiusza i zobaczysz, jak posortować dane „jak w słowniku".

✅ Czego się nauczysz

Po tej jednostce potrafisz:

opisać kolejkę (FIFO) i listę wiązaną oraz ich mocne strony wobec tablicy;
rozwiązać problem Flawiusza (odliczanka) za pomocą kolejki;
wyjaśnić porządek leksykograficzny i posortować nim krotki/napisy.

🔁 Przypomnij sobie

Z 9.1: tablica ma drogie wstawianie/usuwanie w środku i z przodu; z 9.2: stos to LIFO — kolejka będzie jego sprawiedliwym rodzeństwem; z 3.4: porównywanie napisów słownikowo.

📘 Wyjaśnienie

📐 DEFINICJA — kolejka (FIFO): struktura z operacjami dodaj (na koniec) i usuń (z początku). Zasada FIFO (First In, First Out): pierwszy dodany wychodzi pierwszy.

Po ludzku: kolejka w sklepie — dochodzisz na koniec, obsługują od przodu. Czym NIE jest: stosem. Stos i kolejka różnią się jednym: z którego końca zdejmujesz. Ta drobna różnica daje przeciwne zachowania (LIFO vs FIFO) i przeciwne zastosowania.

Zwykła tablica jest do kolejki kiepska (usuwanie z przodu $O(n)$ — 9.1!). Dlatego kolejkę buduje się na strukturze z tanim obu końcami — w Pythonie to collections.deque (dwustronna kolejka; append/popleft — oba $O(1)$). Kolejka rządzi wszędzie, gdzie liczy się sprawiedliwość czasowa: zadania drukarki, bufor strumienia wideo, obsługa żądań serwera, przeszukiwanie „wszerz" (o tym w 9.5).

Lista wiązana naprawia inną słabość tablicy. Zamiast trzymać elementy pod kolejnymi adresami, każdy element (węzeł) przechowuje swoją wartość i wskazówkę, gdzie leży następny — jak podchody, gdzie każda kartka mówi, gdzie szukać kolejnej. Zaleta: wstawienie w środek to przepięcie dwóch wskazówek — $O(1)$, bez przesuwania ogona (rozwiązuje ból wstawiania z 6.4!). Wada: dostęp po indeksie jest drogi — do piątego elementu trzeba przejść przez cztery poprzednie ($O(n)$; nie ma „skoku po adresie" jak w tablicy). Handel jest jasny: tablica — szybki dostęp, drogie wstawianie w środek; lista wiązana — tanie wstawianie w środek, drogi dostęp. Wybierasz wedle tego, co robisz częściej.

Popis 1: problem Flawiusza. Legenda: 41 obrońców, otoczonych, staje w kole i odlicza — co druga osoba ginie; ostatni ocalały przeżyje. Gdzie stanąć, by ocaleć? Historyk Józef Flawiusz podobno wyliczył swoje miejsce i przeżył (a potem napisał o tym książkę). Symulacja to wprost kolejka:

def flawiusz(n, k):                  # n osób, ginie co k-ta
    kolejka = list(range(1, n + 1))  # osoby 1..n (używamy listy jako kolejki)
    while len(kolejka) > 1:
        for _ in range(k - 1):
            kolejka.append(kolejka.pop(0))    # k-1 osób "przechodzi" na koniec
        kolejka.pop(0)                        # k-ta ginie
    return kolejka[0]

Idea: żywi krążą po kole (kolejka!), $k-1$ osób „przechodzi" na koniec (dodaj na koniec, usuń z przodu — czysty FIFO), $k$-ta ginie (usuwana bez powrotu). Krążenie po kole to dokładnie to, do czego kolejka jest stworzona.

Problem Flawiusza dla 7 osób, co druga ginie: koło z ponumerowanymi osobami; strzałki pokazują kolejność eliminacji (2, 4, 6, 1, 5, 3), ocalały to numer 7. · rys. własny

Popis 2: porządek leksykograficzny. Jak posortować pary, krotki, napisy „jak w słowniku"? Reguła słownika: porównaj pierwsze elementy; jeśli równe — drugie; jeśli równe — trzecie… Napisy już tak porównywaliśmy (3.4: „ananas" < „banan"). Uogólnienie na krotki nazywa się porządkiem leksykograficznym i jest domyślnym sposobem, w jaki komputery porównują dane złożone. Dzięki niemu sortowanie wielokryterialne jest darmowe: chcesz uczniów wg klasy, a w klasie wg nazwiska? Posortuj po krotce (klasa, nazwisko) — leksykografia zrobi resztę.

💭 Pomyśl: Sortujesz listę osób najpierw po wieku, a przy równym wieku alfabetycznie. Jak jednym sortowaniem po krotce to załatwić — i w jakiej kolejności ułożyć elementy krotki?

Sprawdź odpowiedź

Sortuj po krotce (wiek, nazwisko) — leksykografia porówna najpierw wiek, a przy remisie nazwiska. Kolejność w krotce = kolejność ważności kryteriów (pierwszy element rządzi). Chcesz najpierw alfabetycznie, potem po wieku — daj (nazwisko, wiek). To najprostszy przepis na sortowanie wielokryterialne w informatyce; alternatywa ze stabilnym sortowaniem (6.4, zadanie 3) — sortuj po najmniej ważnym kryterium, potem stabilnie po ważniejszym — daje ten sam efekt i bywa potrzebna, gdy kryteria mają różne kierunki (rosnąco/malejąco).

⚠️ Uwaga, pułapka

W kodzie Flawiusza użyliśmy list z pop(0) (usuń z przodu) dla czytelności — ale pop(0) na zwykłej liście to $O(n)$ (9.1: usuwanie z przodu przesuwa resztę)! Dla 41 osób nieszkodliwe, dla miliona — katastrofa. Prawdziwa kolejka (deque) robi to w $O(1)$. To ważna lekcja: „działa" i „działa wydajnie" to różne rzeczy — struktura użyta wbrew swojemu charakterowi (lista jako kolejka) daje poprawny wynik drogo. Znajomość kosztów operacji (9.1) chroni przed cichym $O(n^2)$ ukrytym w niewinnym pop(0).

🌍 Powiązania

Kolejka porządkuje świat wszędzie, gdzie „pierwszy zgłoszony, pierwszy obsłużony": kolejka drukarki, bufor odtwarzacza (dane wchodzą i wychodzą w tym samym porządku), obsługa zdarzeń w aplikacji, przeszukiwanie grafu wszerz (9.5 — kolejka jest jego silnikiem). Lista wiązana napędza struktury, które ciągle rosną i kurczą się w środku: historia „cofnij" jako lista, uczestnicy gry dołączający i odchodzący, a nawet sam system plików. Porządek leksykograficzny to domyślne porównanie krotek w większości języków — używasz go za każdym razem, gdy sortujesz dane „po kilku kolumnach".

🛠️ Teraz Ty

Bez komputera: rozwiąż Flawiusza dla $n = 7$, $k = 2$ (rysuj koło, wykreślaj co drugiego) — kto ocaleje? Posortuj leksykograficznie krotki [(2, "b"), (1, "z"), (2, "a"), (1, "a")]. Z komputerem: zaimplementuj flawiusz na deque (import from collections import deque; append/popleft), sprawdź dla $n=41$, $k=3$; posortuj listę (klasa, nazwisko, średnia) uczniów po krotce i zobacz wielokryterialność w akcji.

📐 Definicje tej lekcji

Kolejka (FIFO) — dodaj na koniec / usuń z przodu; pierwszy wchodzi, pierwszy wychodzi.
Lista wiązana — węzły trzymające wartość + wskazówkę do następnego; tanie wstawianie w środek ($O(1)$), drogi dostęp po indeksie ($O(n)$).
Porządek leksykograficzny — porównanie krotek/napisów element po elemencie „jak w słowniku"; pierwszy różniący się rozstrzyga.

📌 Najważniejsze w pigułce

Kolejka (FIFO) rządzi tam, gdzie liczy się sprawiedliwość czasowa; stos i kolejka różnią się tylko końcem zdejmowania.
Lista wiązana odwraca handel tablicy: tanie wstawianie w środek, drogi dostęp po indeksie.
Leksykografia daje sortowanie wielokryterialne za darmo: kolejność w krotce = ważność kryteriów.

🎒 Zadania

Flawiusz dla $n = 6$, $k = 2$: wypisz kolejność eliminacji i ocalałego. Potem sprawdź $k = 3$ — zmienia się ocalały?

Wskazówka i odpowiedź

$n=6, k=2$: giną 2, 4, 6, 3, 1 → ocaleje 5. $k=3$: giną 3, 6, 4, 2, 5 → ocaleje 1. Zmiana kroku $k$ całkowicie zmienia wynik — problem Flawiusza jest zaskakująco czuły na parametry (istnieje nawet elegancki wzór dla $k=2$, ale dla ogólnego $k$ najprościej symulować kolejką). Historyk musiał znać dokładnie $n$ i $k$, by wybrać miejsce — albo mieć szczęście.

Masz posortować rekordy (nazwisko, imię, wiek) alfabetycznie po nazwisku, a przy tym samym nazwisku po imieniu, a przy obu równych — od najmłodszego. Jaką krotką sortujesz i dlaczego akurat taką?

Wskazówka i odpowiedź

Dokładnie krotką (nazwisko, imię, wiek) — leksykografia porówna nazwiska, przy remisie imiona, przy podwójnym remisie wiek (rosnąco = od najmłodszego, bo mniejsza liczba jest „mniejsza" leksykograficznie). Kolejność elementów krotki dokładnie odwzorowuje hierarchię kryteriów. Gdyby wiek miał być malejąco (od najstarszego), a reszta rosnąco — leksykografia sama nie wystarczy (miesza kierunki); wtedy sortuje się wielokrotnie stabilnie albo neguje klucz wieku.

Kolejka priorytetowa to kolejka, w której wychodzi nie „pierwszy w kolejności", lecz „najważniejszy" (najpilniejsze zgłoszenie, najkrótsza trasa). Czemu zwykła kolejka FIFO tu nie wystarczy i jaka struktura się nasuwa?

Wskazówka i odpowiedź

FIFO wydaje w kolejności przybycia, ignorując ważność — pilne zgłoszenie czekałoby za błahymi. Potrzeba struktury, która zawsze szybko oddaje najważniejszy element niezależnie od tego, kiedy wszedł. Utrzymywanie posortowanej listy działa, ale wstawianie w niej jest drogie. Nasuwa się (i jest właściwą odpowiedzią) kopiec — bohater następnej jednostki, który trzyma najważniejszy element na wierzchu i pozwala go zdjąć oraz dołożyć nowy w czasie logarytmicznym.

🔍 Sprawdź, czy umiesz

Odróżnić kolejkę od stosu i podać po dwa zastosowania każdego.
Rozwiązać Flawiusza kolejką i wyjaśnić rolę FIFO w krążeniu po kole.
Posortować dane wielokryterialnie porządkiem leksykograficznym, dobierając kolejność w krotce.

Ucz się tej jednostki z asystentem