Struktury danych — Stos

W programowaniu musimy pracować z mnóstwem danych. Dlatego musimy przechowywać i organizować dane w efektywny sposób. Wtedy przydają się struktury danych. Możemy używać struktur danych do przechowywania, organizowania, przetwarzania i pobierania danych. Struktury danych można dalej podzielić na 2 kategorie w zależności od sposobu ułożenia danych.

W tym artykule będę mówić o strukturach liniowych ( stosach ). W porównaniu ze strukturami nieliniowymi koncepcje stojące za strukturami liniowymi są stosunkowo łatwiejsze do zrozumienia. Niektóre przykłady takich struktur liniowych to Stack, Queues, Deques i Lists. Będziemy przechodzić przez każdą z tych struktur danych jeden po drugim. Te liniowe struktury można traktować jako mające 2 końce. (przód i tył | lewa i prawa strona | góra i dół) Niektóre konstrukcje liniowe umożliwiają wkładanie i wyjmowanie elementów tylko z jednego końca, podczas gdy inne konstrukcje pozwalają na to z obu stron.

1. Półki na książki

• Zasadniczo stos jest uporządkowanym zbiorem elementów, w którym wkładanie i wyjmowanie elementów odbywa się na tym samym końcu. Ten koniec jest powszechnie znany jako „Góra”. Również koniec, przeciwny do góry, jest znany jako „dno”
• Ponadto nowsze elementy znajdują się blisko góry, podczas gdy starsze są blisko dołu. Dlatego kolejność wyjmowania przedmiotów ze stosu będzie odwrotnością kolejności wkładania przedmiotów do stosu.
• Teraz, gdy już dobrze rozumiemy zachowanie stosu, przyjrzyjmy się kilku ważnym operacjom związanym ze strukturą danych stosu.
• push (element) — Metoda push służy do wstawiania elementu na górę stosu.
• pop ()- Metoda pop służy do usuwania wierzchołka — większości elementów ze stosu
• peek () — Metoda Peek służy do przeglądania aktualnie najwyższego elementu stosu.
• size () — Zwraca liczbę elementów znajdujących się na stosie
• is_empty () — Ta metoda jest przydatna do sprawdzenia, czy stos jest pusty, czy nie
• Zauważ, że tutaj koniec listy jest uważany za wierzchołek stosu. (Złożoność czasowa — O(1)) Możemy uznać początek listy za szczyt stosu, jednak nie byłoby to zbyt wydajne, ponieważ złożoność czasowa wynosiłaby O(n) , gdy przesuwamy lub zdejmujemy elementy.
• Gdy uznamy koniec listy za szczyt stosu


• Teraz, gdy wiemy, jak zaimplementować stos, przyjrzyjmy się niektórym scenariuszom, w których użycie struktury danych stosu staje się niezbędne.
• Konwersje systemu liczbowego
• Przede wszystkim zobaczmy, jak możemy przekonwertować liczbę dziesiętną na binarną za pomocą stosu.

• Teraz rozszerzmy powyższy algorytm, aby przekonwertować liczbę dziesiętną na dowolny system liczbowy z zakresu od 2 do 16.


Prawie każdy język programowania używa nawiasów w swojej składni. Dlatego jeśli nie użyjemy nawiasów w zrównoważony sposób, może wystąpić błąd składniowy.

• W pierwszym etapie tego problemu rozważę tylko jeden rodzaj nawiasów, powiedzmy (). Musimy sprawdzić, czy zbiór nawiasów jest zrównoważony, czy nie. W przypadku równowagi powinniśmy zwrócić wartość true, w przeciwnym razie false.
• ( ) — zrównoważony | ( ( ) ) — zrównoważony | ( ( ( ) ( ) ) ) — zrównoważony
• ( ( ) niezrównoważony | ( ) ( ) ( — niezrównoważony | ( ( ( ) ) ( ) — niezrównoważony

• ( [ ] ) — zrównoważony | ( ( ) { } ) — zrównoważony | ( ( [ { } [ ] ] ) ) — zrównoważony
• ( ( ) niezrównoważony | ( ) { } ] — niezrównoważony | ( ( { } [ [ ) — niezrównoważony


3. Odwróć łańcuch za pomocą stosu



4. Wrostek | Notacja postfiksowa i prefiksowa

W informatyce mamy do czynienia z wieloma wyrażeniami arytmetycznymi. Wyrażenie składa się z operatorów (+, -, *, / itd.), operandów (A, B, c, d, 1, 2,… ) oraz symboli, takich jak nawiasy okrągłe.

• Notacja infiksowa — w tej notacji operator jest umieszczany pomiędzy operandami. (<operand> <operator> <operand>)
• Jeśli wyrażenie składa się tylko z jednego operatora (np. 2 + 3, 4 * 6), możemy od razu rozwiązać to wyrażenie. Jeśli jednak wyrażenie ma więcej niż jeden operator, nie możemy go rozwiązać bezpośrednio ze względu na niejednoznaczność wyrażenia. Rozważmy to wyrażenie 1 + 4 * 5. Jeśli najpierw wykonamy dodawanie, otrzymamy odpowiedź jako [ ( 1 + 4 ) * 5 ] = 25, a jeśli najpierw wykonamy mnożenie, otrzymamy odpowiedź jako [1 + (4 * 5 ) )] = 21. Jak widać, w tym zapisie jest pewna niejednoznaczność. Dlatego, aby rozwiązać ten problem, używamy czegoś, co nazywa się „priorytetem operatora”. Zgodnie z operatorem pierwszeństwa mnożenia należy dokonać przed dodawaniem. Zatem poprawna odpowiedź powinna brzmieć 21, a nie 25.
• Zasadniczo, aby rozwiązać wyrażenie zapisane w notacji wrostkowej, musimy postępować zgodnie z zestawem reguł, a także musimy dodać nawiasy. Tak więc ta notacja może zająć więcej pamięci podczas rozwiązywania. Aby przezwyciężyć te wyzwania, naukowcy wymyślili dwie inne notacje, przedrostek i przyrostek.
• W notacji z prefiksem operator jest umieszczany przed operandami (<operator><operand> <operand>), podczas gdy w notacji z przyrostkiem operator jest umieszczany po operandach. (<operand> <operand><operator>)
• W porównaniu z notacją infiksową pozostałe dwie notacje są dość trudne do odczytania i zrozumienia dla człowieka. Ponieważ jednak te dwa zapisy nie mają dodatkowych symboli, takich jak nawiasy kwadratowe, i nie zawierają żadnych dwuznaczności, wyrażenia zapisane w tych dwóch formatach mogą być łatwo odczytywane przez komputery.


• Ocena wyrażenia przyrostkowego : Kiedy musimy ocenić wyrażenie przyrostkowe, powinniśmy rozpocząć skanowanie od lewej strony, aż znajdziemy operatora. Po znalezieniu operatora musimy wykonać odpowiednią operację algebraiczną na pierwszych 2 argumentach po lewej stronie operatora.

• Przede wszystkim musimy usunąć wszystkie spacje w naszym wejściu. Dlatego musimy użyć metody podziału. Następnie musimy przeskanować nasze wyrażenie od lewej do prawej. Jeśli natrafimy na liczbę, musimy wrzucić ją do stosu. Jeśli napotkamy operatora, musimy wyrzucić 2 z najwyższych przedmiotów w naszym stosie. Następnie musimy wywołać naszą funkcję pomocniczą, aby wykonać operację arytmetyczną. Następnie wrzucimy wynik do stosu. Gdy skończymy skanowanie, zwrócimy to, co pozostało na naszym stosie, co jest odpowiedzią na obliczone wyrażenie postfiksowe.


• Zobaczmy teraz, jak możemy przekonwertować wyrażenie w formacie infiksowym na przyrostek przy użyciu Pythona.