Wzajemna symulacja stosu i kolejki

Implementacja kolejki za pomocą dwóch stosów oraz stosu za pomocą dwóch kolejek to klasyczne zadania projektowe pojawiające się podczas rozmów technicznych. Sprawdzają one zrozumienie niezmienników obu struktur danych oraz umiejętność zachowania gwarancji jednej struktury przy użyciu operacji podstawowych drugiej. Osoby przeprowadzające rozmowy techniczne wykorzystują te zadania również jako punkt wyjścia do omówienia złożoności zamortyzowanej.

Kluczowa obserwacja jest następująca: stosy działają w trybie LIFO, a kolejki w trybie FIFO. Aby przekształcić jedną strukturę w drugą, należy odwrócić kolejność — a odwrócenie stosu na drugi stos przywraca pierwotną kolejność dodawania, czyli kolejność FIFO.

Podejście leniwe polega na użyciu stosu inbox do operacji dodawania oraz stosu outbox do operacji usuwania. Gdy wywoływana jest operacja dequeue, a outbox jest pusty, wszystkie elementy są przenoszone ze stosu inbox na stos outbox — to odwrócenie przywraca kolejność FIFO. Jeśli outbox nie jest pusty, element jest zdejmowany bezpośrednio z niego. Transfery są wykonywane leniwie, dzięki czemu koszt transferu O(n) rozkłada się zamortyzowanie na wiele operacji.

Każdy element jest przenoszony ze stosu inbox na stos outbox najwyżej raz. Usuwanie elementu ze stosu outbox zajmuje O(1), a transfery odbywają się tylko wtedy, gdy outbox jest pusty. Zatem łączna praca dla n operacji dodawania i n operacji usuwania wynosi najwyżej 2n operacji na stosach — łącznie O(n), czyli zamortyzowane O(1) na operację. Oznacza to, że pojedyncze operacje mogą w najgorszym przypadku zajmować O(n), ale średnia złożoność wynosi O(1).

Implementacja stosu za pomocą dwóch kolejek jest mniej naturalna, ponieważ kolejki działają w trybie FIFO. Podejście z leniwym usuwaniem polega na utrzymywaniu jednej głównej kolejki i jednej kolejki tymczasowej. Podczas operacji push dodajemy element do głównej kolejki (O(1)). Podczas operacji pop lub peek usuwamy wszystkie elementy oprócz ostatniego do kolejki tymczasowej, zapamiętujemy ostatni element, a następnie zamieniamy kolejki miejscami. Operacja ta zajmuje O(n), ale push zajmuje O(1).

Elegancka implementacja z jedną kolejką wygląda następująco: podczas operacji push dodajemy nowy element do kolejki, a następnie obracamy kolejkę tak, aby nowy element znalazł się na początku. Obracanie oznacza usunięcie z kolejki i ponowne dodanie wszystkich elementów, które znajdowały się w niej przed operacją push. Dzięki temu pop i peek zajmują O(1) (wystarczy usunąć lub podejrzeć element z początku). Operacja push zajmuje O(n) — jest to przeciwna zależność kosztów niż w wersji z dwiema kolejkami.

Dla kolejki z dwóch stosów: push O(1), pop/peek zamortyzowane O(1) — warto ją wybrać, gdy operacje pop występują często. Dla stosu z dwóch kolejek: push O(1), pop O(n) — warto go wybrać, gdy operacje push występują znacznie częściej niż pop. Dla stosu z jednej kolejki: push O(n), pop O(1) — warto go wybrać, gdy dominują operacje pop. Podczas rozmowy technicznej należy jasno przedstawić te kompromisy, aby pokazać, że myśli się nie tylko w kategoriach „to działa”.

Gdy elementy 1, 2, 3 zostaną umieszczone na stosie (inbox), znajdują się od dołu do góry w kolejności 1, 2, 3. Zdjęcie wszystkich elementów i umieszczenie ich na drugim stosie (outbox) odwraca kolejność: na dole outbox znajduje się 3, a na górze 1. Zdejmowanie elementów z outbox daje kolejno 1, 2, 3 — dokładnie w kolejności ich dodania zgodnej z FIFO. Dlatego właśnie dokładnie dwa odwrócenia (dwa stosy) przywracają FIFO, podczas gdy pojedynczy stos zapewniałby LIFO.

LeetCode 232 to bezpośrednie zadanie „kolejka z dwóch stosów”. Oczekiwanym rozwiązaniem jest leniwy transfer do outbox. Podczas rozmowy technicznej należy zaznaczyć, że każdy element jest przenoszony z inbox do outbox najwyżej raz, dzięki czemu wszystkie operacje mają zamortyzowaną złożoność O(1). Warto również wspomnieć, że pojedyncze wywołanie pop może w najgorszym przypadku mieć złożoność O(n) (gdy outbox jest pusty), ale średnia złożoność dla n operacji wynosi O(1).

LeetCode 225 to problem „stos z kolejek”. Najbardziej przejrzyste jest rozwiązanie z jedną kolejką i obracaniem przy operacji push. Po dodaniu elementu x obracamy kolejkę, przenosząc wszystkie elementy, które już się w niej znajdowały, za element x. Koszt wynosi O(n) dla każdej operacji push, ale operacje top i pop mają złożoność O(1). Należy przedstawić ten kompromis i potwierdzić, że odpowiada on ograniczeniom (na przykład obciążeniu z niewielką liczbą operacji push lub dużą liczbą operacji pop).

Powiązane wyzwanie projektowe: zaimplementowanie trzech stosów przy użyciu jednej tablicy. Jedno podejście dzieli tablicę na trzy równe, stałe sekcje. Bardziej elastyczne podejście wykorzystuje przeplatane przechowywanie z użyciem wskaźników: każdy stos rośnie w swoim obszarze, a gdy granice się zderzą, dane są kopiowane. Sprawdza to umiejętność zarządzania dynamiczną tablicą i pojawia się na rozmowach rekrutacyjnych na stanowiska seniorskie. Podejście ze stałymi sekcjami jest prostsze, ale marnuje miejsce, jeśli stosy rosną nierównomiernie.

Problemy wzajemnej symulacji uczą szerszej zasady: każdą strukturę danych można zbudować na bazie innej, jeśli zapewni się wystarczające buforowanie pośrednie i odwracanie kolejności. Koszt symulacji zależy od tego, które operacje są optymalizowane — zawsze można zapewnić push O(1) lub pop O(1), ale zapewnienie obu operacji w O(1) wymaga amortyzacji albo wielu struktur pomocniczych.

Podczas rozmowy rekrutacyjnej należy zawsze zapytać: „Które operacje wykonuje się częściej?”. Pomaga to wybrać odpowiedni wariant implementacji i pokazuje dojrzałe podejście do wymagań operacyjnych.

Proszę sprawdzić swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

W tej lekcji omówiono: kolejka z dwóch stosów zapewnia zamortyzowane pop O(1) dzięki leniwemu przenoszeniu elementów ze stosu wejściowego do wyjściowego, stos z jednej kolejki zapewnia pop O(1) dzięki obracaniu kolejki przy każdym push (push O(n)) oraz wybór operacji, która ma działać w O(1), zależy od sposobu użycia. W dalszej części poznają Państwo szczegóły implementacji map haszujących i obsługę kolizji.