po wyjaśnieniu tych ważnych metod, rzućmy okiem na ostateczną implementację naszej klasy stosu:
metody push i pop pojawiają się dokładnie tak, jak tego oczekujemy (lines13–32). Możemy użyć naszej metody push do utworzenia niestandardowego inicjalizatora z niektórymi wartościami wariadycznymi (linie 7-11). Dodatkowo możemy sprawdzić, czy nasz rootNode ma wartość (linie 34-36) i posiada podstawową metodę drukowania, która iteruje przez naszą listę, o ile jest w stanie uzyskać dostęp do węzłów przez następną właściwość (linie 38-44).
podstawowy test funkcjonalności stosu wygląda następująco:
Wiedza o tym, jak wdrożyć stos, to jedno, ale jeszcze ważniejsze jest rozpoznanie sytuacji, do których stos jest odpowiedni. W następnej sekcji przyjrzymy się trzem takim przypadkom.
Przypadek Użycia 1: Kolejność odwrotna
ponieważ kolejność stosu jest stała, kolejność odwrotna może być bardzo łatwo osiągnięta przez wyskakiwanie elementów z jednego stosu i natychmiast na drugi. Nie mieszaj się z wymianą indeksów!
przypadek użycia 2: testowanie symetrii
kolejnym dobrym przykładem użycia stosów jest testowanie symetrii. W poniższym przykładzie testujemy ciąg nawiasów, aby upewnić się, że każdy wspornik zamykający jest prawidłowym odpowiednikiem wcześniejszego wspornika otwierającego.
zaczynamy od sprawdzenia, czy liczba znaków jest podzielna przez dwa, ponieważ Nieparzysta liczba znaków byłaby natychmiast asymetryczna (linia 6). Następnie sprawdzamy, czy mamy poprawne dane wejściowe, definiując zestaw znaków nielegalnych, a następnie sprawdzamy, czy nasz łańcuch wejściowy ma zerowy zakres nielegalnych znaków (linie 7-8). Aby sprawdzić, czy nasze nawiasy zamykające i otwierające są zgodne, umieszczamy je w słowniku jako pary klucz-wartość (linia 10). W innych sytuacjach możesz być w stanie obliczyć wartość odwrotną bez konieczności przechowywania par w słowniku. Następnie mamy nasz stos (linia 11). Celem naszego stosu w tym przypadku jest przechowywanie nawiasów otwierających. Podczas iteracji naszego ciągu możemy sprawdzić, czy nasz znak jest nawiasem otwierającym, testując, czy jest kluczem w naszym słowniku. Jeśli tak, wciskamy go na nasz stos. Po znalezieniu pierwszego zamkniętego nawiasu wiemy, że przechodzimy przez drugą połowę naszego wzorca, więc ustawiamy naszą pierwszą połowę logiczną na false (linia 12). Jeśli znajdziemy więcej nawiasów otwierających po tym punkcie, możemy sprawdzić wartość logiczną i wskazać nieudany test. Dla każdego wspornika zamykającego zdejmujemy ostatni wspornik otwierający i sprawdzamy, czy są one poprawną parą klucz-wartość. Po raz kolejny, musimy tylko raz iterować przez łańcuch, więc otrzymujemy wiele wartości z algorytmu liniowego.
przypadek użycia 3: cofanie poleceń
na koniec użyjemy stosu w połączeniu ze wzorcem poleceń, aby utworzyć historię cofania. Na początek przyjrzyjmy się prostemu obiektowi konta bankowego. Ma saldo i limit debetowy oraz kilka prostych metod deponowania i wypłacania środków:
zamiast wywoływać metody wpłaty i wypłaty bezpośrednio, możemy przechowywać odpowiednie informacje w poleceniu. W poniższym fragmencie określamy, jaki rodzaj działania chcemy wykonać z nieruchomością enum (depozyt lub wypłata) i kwotą . Przechowujemy również wartość logiczną, aby wskazać, czy polecenie było możliwe do wykonania (linie 4-11). Zauważ, że jeśli żądanie wypłaty przekroczy limit debetowy, nic nie stanie się z kontem bankowym, a pomyślana wartość logiczna pozostanie fałszywa, w przeciwnym razie stanie się prawdziwa po zakończeniu polecenia (linie 18-26). Mamy dwie metody wywołania lub cofnięcia polecenia, z których każda bierze konto bankowe jako argument (linie 18 & 28). Metody te biorą konto bankowe i wywołują jego instancje, które widzieliśmy w poprzednim fragmencie.
Wracając do konta bankowego, możemy teraz wprowadzić naszą właściwość commandStack, która została zainicjowana przez nasz BankAccountType (linia 47). Oznaczamy nasze metody wpłat i wypłat jako fileprivate, dzięki czemu mogą być dostępne tylko przez nasz BankAccountCommand (linie 62 & 66). Teraz mamy dwie ujawnione metody: process (command:) i undoLastCommand(). Pierwszy przyjmuje polecenie jako wejście, wykonuje je z kontem bankowym jako wejście, a następnie wypycha polecenie na stos. W międzyczasie metoda undoLastCommand usuwa ostatnie polecenie ze stosu i wykonuje undo (linie 51-60).
jest to bardzo prosty wzór, który jest bardzo potężny. Możliwe aplikacje są nieograniczone i zapewniają satysfakcjonujące wrażenia użytkownika.
a teraz zobaczmy wzór w akcji:
Wrap Up
w tym artykule zbadaliśmy koncepcję stosu i zachowania LIFO. Zaimplementowaliśmy własny stos używając podwójnie połączonej listy i zademonstrowaliśmy, jak alokuje i dealokuje pamięć w miarę zmian rozmiaru stosu. Przyjrzeliśmy się również trzem powszechnym przypadkom użycia stosów: cofaniu, testowaniu symetrii i cofaniu. Każda z tych trzech sytuacji pojawia się niezliczoną ilość razy w rzeczywistych projektach. Mam nadzieję, że pomyślicie o stosie jako odpowiedniej strukturze do obsługi tych potrzeb. Jak zawsze, dziękuję za przeczytanie!