Podcast o Kolejka (queue)

Kapitoly

Zasada FIFO

Podstawowe operacje

Sekret wydajności

Přepis

Zofia: Wyobraź sobie… jesteś na egzaminie i ląduje przed tobą to zadanie. Musisz obsłużyć setki żądań w odpowiedniej kolejności. Tu właśnie wkracza struktura danych, która ratuje sytuację — a 80% uczniów myli się co do jej najwydajniejszej implementacji.

Szymon: Ale ty nie będziesz w tej grupie. Pokażemy ci, jak to zrobić dobrze.

Zofia: Słuchacie Studyfi Podcast.

Zofia: Dobrze, Szymon, zacznijmy od podstaw. Czym jest ta magiczna „kolejka”?

Szymon: To nic skomplikowanego, Zofio. Pomyśl o zwykłej kolejce do kasy w sklepie. Kto pierwszy przyszedł, ten pierwszy zostanie obsłużony. W informatyce nazywamy to zasadą FIFO — First-In, First-Out.

Zofia: Czyli „pierwsze weszło, pierwsze wyszło”. Proste. Nikt się nie wpycha.

Szymon: Dokładnie! I na tym polega cała filozofia. Element dodany jako pierwszy, jako pierwszy musi kolejkę opuścić.

Zofia: Okej, a jakimi operacjami zarządzamy taką kolejką?

Szymon: Mamy dwie kluczowe. Pierwsza to Enqueue, czyli dodanie nowego elementu na sam koniec kolejki.

Zofia: Jak nowa osoba stająca na końcu ogonka w sklepie. A druga?

Szymon: Druga to Dequeue — usunięcie elementu z samego początku. To tak, jakby kasjer obsłużył pierwszą osobę.

Zofia: A co jeśli chcę tylko zerknąć, kto jest pierwszy, ale go nie obsługiwać? Tak z ciekawości.

Szymon: Świetne pytanie! Do tego służy operacja Peek albo Front. Podglądasz pierwszy element, ale go nie usuwasz z kolejki.

Zofia: Rozumiem. Ale jak to zaimplementować, żeby było szybkie? Wspomniałeś o błędach.

Szymon: I tu jest sedno! Kluczem jest złożoność czasowa O(1), czyli stały czas operacji, niezależnie od wielkości kolejki. Jeśli użyjesz zwykłej tablicy i po każdym usunięciu będziesz przesuwać wszystkie elementy... to katastrofa wydajnościowa.

Zofia: Bo przesuwanie tysiąca elementów zajmie wieki. Więc jak to obejść?

Szymon: Używamy bufora cyklicznego! To taka sprytna tablica z dwoma wskaźnikami: head na początek i tail na koniec. Gdy wskaźnik dojdzie do końca tablicy, po prostu zawija się na jej początek. Dzięki temu nie ma żadnego przesuwania. Genialne w swojej prostocie.