Implementacja stosu i zastosowania

Stos to struktura danych działająca zgodnie z zasadą last-in, first-out (LIFO). Ostatni element odłożony na stos jest pierwszym elementem z niego zdejmowanym. Można wyobrazić go sobie jako stos talerzy: elementy można dodawać i usuwać wyłącznie z góry. Podstawowe operacje to push (dodanie na górze), pop (usunięcie z góry) i peek (odczytanie elementu z góry bez usuwania). Wszystkie trzy operacje mają złożoność O(1) w poprawnie zaimplementowanym stosie.

W Pythonie lista doskonale sprawdza się jako stos: append odpowiada operacji push, pop() operacji pop, a [-1] operacji peek.

Umieszczenie listy w klasie zapewnia przejrzystszy interfejs i zapobiega przypadkowemu użyciu operacji, które nie należą do stosu, takich jak insert lub indeksowanie pozycji innych niż górny element. Jest to implementacja, jakiej oczekują rekruterzy, gdy proszą o „zaimplementowanie stosu od podstaw”.

LeetCode 20 „Valid Parentheses”: określenie, czy ciąg nawiasów jest poprawnie zbilansowany. Dla każdego nawiasu otwierającego należy wykonać push. Dla każdego nawiasu zamykającego należy sprawdzić, czy element na szczycie stosu jest odpowiadającym mu nawiasem otwierającym; jeśli nie albo jeśli stos jest pusty, należy zwrócić False. Jeśli na końcu stos jest pusty, ciąg jest poprawny. To klasyczne pierwsze zastosowanie stosu podczas rozmów kwalifikacyjnych dotyczących programowania.

LeetCode 155 „Min Stack”: zaprojektowanie stosu obsługującego operacje push, pop, peek i getMin, każdą w czasie O(1). Sztuczka polega na utrzymywaniu drugiego stosu, który w każdej chwili przechowuje minimum. Podczas dodawania elementu należy dodać go również na stos minimum, jeśli nowa wartość jest <= bieżącego minimum (albo jeśli stos minimum jest pusty). Podczas usuwania elementu należy usunąć go również ze stosu minimum, jeśli usunięta wartość jest równa bieżącemu minimum.

LeetCode 150 „Evaluate Reverse Polish Notation” (notacja postfiksowa): operandy są odkładane na stos; po napotkaniu operatora należy zdjąć dwa operandy, zastosować operator i odłożyć wynik. Kolejność ma znaczenie przy odejmowaniu i dzieleniu: pierwszy zdjęty operand jest prawym operandem, a drugi — lewym.

LeetCode 394 „Decode String”: mając zakodowany ciąg, taki jak 3[a2[c]], należy rozwinąć go do postaci accaccacc. Należy użyć dwóch stosów: jednego dla liczników powtórzeń i drugiego dla zgromadzonych ciągów. Po napotkaniu cyfry należy zbudować pełną liczbę. Po napotkaniu [ należy odłożyć bieżący ciąg i licznik. Po napotkaniu ] należy zdjąć te wartości ze stosów i powtórzyć bieżący fragment. Po napotkaniu litery należy dodać ją do bieżącego ciągu.

LeetCode 739 „Daily Temperatures”: dla każdego dnia należy znaleźć liczbę dni do wystąpienia wyższej temperatury. Naiwne rozwiązanie ma złożoność O(n²). W rozwiązaniu ze stosem należy przechodzić przez temperatury; dla każdego dnia zdejmować ze stosu wszystkie elementy (indeksy dni), których temperatura jest niższa niż temperatura dzisiejsza. Odpowiedzią dla każdego zdjętego dnia jest (today - popped_day). Następnie należy odłożyć bieżący dzień. Pozostałe elementy stosu nigdy nie doczekały się wyższej temperatury — ich odpowiedź wynosi 0.

Stos wywołań używany w rekurencyjnym DFS można zastąpić jawnym stosem, przekształcając algorytm w iteracyjny. Należy odłożyć korzeń; dopóki stos nie jest pusty, zdejmować węzeł, przetwarzać go i odkładać jego dzieci (najpierw prawe, potem lewe, aby przetwarzać je od lewej do prawej). Iteracyjny DFS zachowuje się tak samo jak rekurencyjny DFS, ale pozwala uniknąć limitu rekurencji Pythona w przypadku głębokich drzew.

Wszystkie operacje stosu (push, pop, peek, isEmpty) mają zamortyzowaną złożoność O(1). Zbudowanie stosu zawierającego n elementów zajmuje O(n). W najgorszym przypadku stos zajmuje O(n) pamięci, gdy przechowywane są wszystkie elementy. W zadaniach wykorzystujących stos monotoniczny każdy element jest odkładany i zdejmowany najwyżej raz, co daje łączny czas O(n) we wszystkich iteracjach — a nie O(n²), jak mogłoby sugerować naiwne odczytanie zewnętrznej pętli.

LeetCode 84 „Largest Rectangle in Histogram” to najtrudniejsze z klasycznych zadań wykorzystujących stos. Dla każdego słupka prostokąt, którego może on być podstawą, rozciąga się w lewo do napotkania niższego słupka i w prawo do napotkania niższego słupka. Stos monotoniczny przechowuje indeksy słupków uporządkowanych rosnąco według wysokości. Po napotkaniu niższego słupka należy zdejmować elementy i obliczać prostokąt o wysokości zdjętego słupka. Stos pozwala znaleźć lewą i prawą granicę w czasie O(1) dla każdego zdejmowanego elementu.

Zadania stosowe często ukrywają się pod postacią „przetwarzania od środka na zewnątrz” albo „znajdowania następnego większego/mniejszego elementu”. O użyciu stosu mogą świadczyć następujące sygnały: potrzebują Państwo ostatnio napotkanego elementu, dopasowują Państwo pary (nawiasy, znaczniki) albo chcą Państwo uzyskać O(n) w zadaniu, które naiwnie wymaga zagnieżdżonych pętli O(n²). W szczególności stosy monotoniczne przekształcają zadanie „dla każdego elementu znajdź najbliższy większy/mniejszy” z O(n²) w O(n).

Podczas rozmowy kwalifikacyjnej należy jasno określić niezmiennik stosu: „Będę utrzymywać stos indeksów w kolejności malejących wysokości”.

Sprawdź swoją wiedzę z zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

W tej lekcji nauczyłeś się, że: listy Pythona implementują operacje push/pop/peek w czasie O(1), dzięki czemu idealnie nadają się na stosy, poprawne nawiasy i stos minimum to dwa klasyczne zadania stosowe podczas rozmów kwalifikacyjnych, a stosy monotoniczne rozwiązują zadania typu next-greater-element w czasie O(n), ponieważ każdy element jest odkładany i zdejmowany najwyżej raz. W następnej części zbudujemy kolejki za pomocą deque z Pythona i rozwiążemy zadanie o maksimum w przesuwanym oknie.