Przewodnik po stosach w Pythonie

Wprowadzenie

Podczas gdy niektóre struktury danych są wszechstronne i można je stosować w szerokim zakresie zastosowań, inne są wyspecjalizowane i zaprojektowane do obsługi konkretnych problemów. Jedną z takich wyspecjalizowanych konstrukcji, znaną ze swojej prostoty, a jednocześnie niezwykłej użyteczności, jest stos.

Czym zatem jest stos? W swojej istocie stos jest liniową strukturą danych, która następuje po LIFO Zasada „ostatni weszło, pierwsze wyszło”.. Pomyśl o tym jak o stosie talerzy w stołówce; bierzesz tylko ten talerz, który jest na górze, a kiedy kładziesz nowy talerz, trafia on na górę stosu.

Ostatni dodany element jest pierwszym elementem do usunięcia

Ale dlaczego zrozumienie stosu jest kluczowe? Z biegiem lat stosy znalazły zastosowanie w wielu obszarach, od zarządzania pamięcią w ulubionych językach programowania po funkcję przycisku Wstecz w przeglądarce internetowej. Ta wewnętrzna prostota w połączeniu z jej szerokimi możliwościami zastosowania sprawia, że ​​stos jest niezbędnym narzędziem w arsenale programisty.

W tym przewodniku szczegółowo omówimy koncepcje stosów, ich implementację, przypadki użycia i wiele więcej. Zdefiniujemy, czym są stosy i jak działają, a następnie przyjrzymy się dwóm najpopularniejszym sposobom implementacji struktury danych stosu w Pythonie.

Podstawowe pojęcia dotyczące struktury danych stosu

W swej istocie stos jest zwodniczo prosty, lecz posiada pewne niuanse, które zapewniają mu wszechstronne zastosowanie w domenie obliczeniowej. Zanim zagłębimy się w jego implementacje i praktyczne zastosowania, upewnijmy się, że mamy solidne zrozumienie podstawowych koncepcji otaczających stosy.

Zasada LIFO (ostatnie weszło, pierwsze wyszło).

LIFO jest wiodącą zasadą stosu. Oznacza to, że ostatni element wprowadzony do stosu jest pierwszym, który go opuści. Ta cecha odróżnia stosy od innych liniowych struktur danych, takich jak kolejki.

Podstawowe operacje

Każda struktura danych jest definiowana przez operacje, które obsługuje. W przypadku stosów te operacje są proste, ale istotne:

• Naciskać – Dodaje element na górę stosu. Jeśli stos jest pełny, operacja ta może spowodować przepełnienie stosu.

• Muzyka pop – Usuwa i zwraca najwyższy element stosu. Jeśli stos jest pusty, próba popu może spowodować niedopełnienie stosu.

• Zerknij (lub z góry) – Obserwuje najwyższy element bez usuwania go. Ta operacja jest przydatna, gdy chcesz sprawdzić bieżący górny element bez zmiany stanu stosu.

Do tej pory znaczenie struktury danych stosu i jej podstawowych koncepcji powinno być oczywiste. W miarę postępów zagłębimy się w jego implementacje, rzucając światło na to, jak te podstawowe zasady przekładają się na praktyczny kod.

Jak zaimplementować stos od podstaw w Pythonie

Po zrozumieniu podstawowych zasad stosów nadszedł czas, aby zakasać rękawy i zagłębić się w praktyczną stronę rzeczy. Do implementacji stosu, choć prostego, można podejść na wiele sposobów. W tej sekcji omówimy dwie podstawowe metody implementacji stosu — użycie tablic i list połączonych.

Implementowanie stosu przy użyciu tablic

Tablice, byt sąsiadujące lokalizacje pamięcioferują intuicyjny sposób reprezentowania stosów. Umożliwiają złożoność czasową O(1) dostępu do elementów według indeksu, zapewniając szybkie operacje push, pop i peek. Ponadto tablice mogą być bardziej wydajne pod względem pamięci, ponieważ nie ma narzutu wskaźników, jak w przypadku list połączonych.

Z drugiej strony tradycyjne tablice mają stały rozmiar, co oznacza, że ​​po zainicjowaniu nie można zmienić ich rozmiaru. Może to prowadzić do: przepełnienie stosu jeśli nie jest monitorowany. Można to przezwyciężyć za pomocą tablic dynamicznych (takich jak tablice Pythona list), którego rozmiar można zmienić, ale operacja ta jest dość kosztowna.

Mając już to wszystko na uwadze, zacznijmy implementować naszą klasę stosu przy użyciu tablic w Pythonie. Przede wszystkim utwórzmy samą klasę z konstruktorem, który jako parametr przyjmuje wielkość stosu:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Jak widać, w naszej klasie przechowywaliśmy trzy wartości. The size jest pożądanym rozmiarem stosu, the stack jest rzeczywistą tablicą używaną do reprezentowania struktury danych stosu, a top jest indeksem ostatniego elementu w stack tablica (szczyt stosu).

Od teraz będziemy tworzyć i wyjaśniać jedną metodę dla każdej z podstawowych operacji na stosie. Każda z tych metod będzie zawarta w pliku Stack klasa, którą właśnie utworzyliśmy.

Zacznijmy od push() metoda. Jak wspomniano wcześniej, operacja push dodaje element na górę stosu. Na początek sprawdzimy, czy na stosie jest jeszcze miejsce na element, który chcemy dodać. Jeśli stos jest pełny, podbijamy Stack Overflow wyjątek. W przeciwnym razie po prostu dodamy element i dostosujemy top i stack odpowiednio:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Teraz możemy zdefiniować metodę usuwania elementu ze szczytu stosu – tzw pop() metoda. Zanim w ogóle spróbujemy usunąć element, musimy sprawdzić, czy na stosie znajdują się jakieś elementy, ponieważ nie ma sensu próbować wyjmować elementu z pustego stosu:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Wreszcie możemy zdefiniować peek() metoda, która po prostu zwraca wartość elementu znajdującego się aktualnie na szczycie stosu:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

I to wszystko! Mamy teraz klasę, która implementuje zachowanie stosów przy użyciu list w Pythonie.

Implementowanie stosu przy użyciu list połączonych

Połączone listy, bycie dynamiczne struktury danych, mogą łatwo rosnąć i kurczyć się, co może być korzystne przy wdrażaniu stosów. Ponieważ listy połączone przydzielają pamięć w miarę potrzeb, stos może dynamicznie rosnąć i zmniejszać się bez potrzeby jawnej zmiany rozmiaru. Kolejną zaletą używania list połączonych do implementowania stosów jest to, że operacje push i pop wymagają jedynie prostych zmian wskaźnika. Wadą tego jest to, że każdy element na połączonej liście ma dodatkowy wskaźnik, co zużywa więcej pamięci w porównaniu do tablic.

Jak już pisaliśmy w „Listy połączone w Pythonie” artykuł, pierwszą rzeczą, którą musimy zaimplementować, zanim rzeczywista lista połączona, będzie klasa dla pojedynczego węzła:

class Node: def __init__(self, data): self.data = data self.next = None

Ta implementacja przechowuje tylko dwa punkty danych – wartość przechowywaną w węźle (data) i odniesienie do następnego węzła (next).

Teraz możemy przejść do samej klasy stosu. Konstruktor będzie nieco inny od poprzedniego. Będzie zawierać tylko jedną zmienną – odwołanie do węzła na górze stosu:

class Stack: def __init__(self): self.top = None

Zgodnie z oczekiwaniami push() metoda dodaje nowy element (w tym przypadku węzeł) na górę stosu:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

Połączenia pop() metoda sprawdza, czy na stosie znajdują się jakieś elementy i usuwa najwyższy, jeśli stos nie jest pusty:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Wreszcie, peek() metoda po prostu odczytuje wartość elementu ze szczytu stosu (jeśli taki istnieje):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Wybór pomiędzy tablicami a listami połączonymi zależy od konkretnych wymagań i ograniczeń aplikacji.

Jak zaimplementować stos przy użyciu wbudowanych struktur Pythona

Dla wielu programistów budowanie stosu od podstaw w celach edukacyjnych może nie być najskuteczniejszym sposobem wykorzystania stosu w rzeczywistych aplikacjach. Na szczęście wiele popularnych języków programowania ma wbudowane struktury danych i klasy, które w naturalny sposób obsługują operacje na stosach. W tej sekcji przyjrzymy się ofercie Pythona w tym zakresie.

Python, będąc językiem wszechstronnym i dynamicznym, nie ma dedykowanej klasy stosu. Jednak wbudowane struktury danych, w szczególności listy i klasa deque z collections moduł, mogą bez problemu służyć jako stosy.

Używanie list Pythona jako stosów

Listy w Pythonie mogą dość skutecznie emulować stos ze względu na ich dynamiczną naturę i obecność metod takich jak append() i pop().

• Operacja push – Dodanie elementu na szczyt stosu jest tak proste, jak użycie append() metoda:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Operacja Pop – Usunięcie najwyższego elementu można wykonać za pomocą pop() metoda bez żadnego argumentu:

  top_element = stack.pop() 

• Operacja podglądu Dostęp do góry bez pojawiania się można uzyskać za pomocą indeksowania ujemnego:

  top_element = stack[-1] 

Korzystanie z dlatego Klasa od kolekcje Moduł

Połączenia deque Klasa (skrót od double-ended kolejki) to kolejne wszechstronne narzędzie do implementacji stosów. Jest zoptymalizowany pod kątem szybkiego dołączania i wyskakiwania z obu końców, dzięki czemu jest nieco bardziej wydajny w przypadku operacji na stosach niż na listach.

• Inicjalizacji:

  from collections import deque
  stack = deque()
  

• Operacja push – Podobnie jak listy, append() stosowana jest metoda:

  stack.append('A')
  stack.append('B')
  

• Operacja Pop – Podobnie jak listy, pop() metoda spełnia swoje zadanie:

  top_element = stack.pop() 

• Operacja podglądu – Podejście jest takie samo jak w przypadku list:

  top_element = stack[-1] 

Kiedy używać którego?

Chociaż zarówno listy, jak i deques mogą być używane jako stosy, jeśli używasz struktury głównie jako stosu (z dołączeniami i wyskokami z jednego końca), deque może być nieco szybszy dzięki optymalizacji. Jednak w większości zastosowań praktycznych i jeśli nie chodzi o aplikacje krytyczne pod względem wydajności, listy Pythona powinny wystarczyć.

Potencjalne problemy związane ze stosem i sposoby ich przezwyciężenia

Chociaż stosy są niezwykle wszechstronne i wydajne, jak każda inna struktura danych, nie są odporne na potencjalne pułapki. Podczas pracy ze stosami istotne jest rozpoznanie tych wyzwań i posiadanie strategii pozwalających im sprostać. W tej sekcji zajmiemy się niektórymi typowymi problemami związanymi ze stosem i zbadamy sposoby ich rozwiązania.

Przepełnienie stosu

Dzieje się tak, gdy podejmowana jest próba wepchnięcia elementu na stos, który osiągnął maksymalną pojemność. Jest to szczególnie problem w środowiskach, w których rozmiar stosu jest stały, na przykład w niektórych scenariuszach programowania niskiego poziomu lub wywołaniach funkcji rekurencyjnych.

Jeśli używasz stosów opartych na tablicach, rozważ przejście na tablice dynamiczne lub implementacje list połączonych, które same zmieniają rozmiar. Kolejnym krokiem w zapobieganiu przepełnieniu stosu jest ciągłe monitorowanie rozmiaru stosu, szczególnie przed operacjami wypychania, i dostarczanie przejrzystych komunikatów o błędach lub monitów o przepełnienie stosu.

Jeśli przepełnienie stosu nastąpi z powodu nadmiernej liczby wywołań rekurencyjnych, rozważ rozwiązania iteracyjne lub zwiększ limit rekurencji, jeśli pozwala na to środowisko.

Niedopełnienie stosu

Dzieje się tak, gdy następuje próba wyrzucenia elementu z pustego stosu. Aby temu zapobiec, przed wykonaniem operacji pop lub peek zawsze sprawdź, czy stos jest pusty. Zwróć wyraźny komunikat o błędzie lub uporaj się z niedomiarem bez powodowania awarii programu.

W środowiskach, w których jest to dopuszczalne, rozważ zwrócenie specjalnej wartości podczas wyskakiwania z pustego stosu, aby zaznaczyć nieważność operacji.

Ograniczenia pamięci

W środowiskach o ograniczonej pamięci nawet dynamiczna zmiana rozmiaru stosów (takich jak te oparte na listach połączonych) może prowadzić do wyczerpania pamięci, jeśli staną się zbyt duże. Dlatego miej oko na ogólne wykorzystanie pamięci przez aplikację i wzrost stosu. Być może wprowadź miękkie ograniczenie wielkości stosu.

Obawy dotyczące bezpieczeństwa wątku

W środowiskach wielowątkowych jednoczesne operacje na współdzielonym stosie przez różne wątki mogą prowadzić do niespójności danych lub nieoczekiwanych zachowań. Potencjalne rozwiązania tego problemu mogą być następujące:

• Muteksy i blokady – Używaj muteksów (obiektów wzajemnego wykluczania) lub blokad, aby mieć pewność, że tylko jeden wątek może w danym momencie wykonywać operacje na stosie.
• Operacje atomowe – Wykorzystuj operacje atomowe, jeśli są obsługiwane przez środowisko, aby zapewnić spójność danych podczas operacji push i pop.
• Stosy lokalne wątku – W scenariuszach, w których każdy wątek potrzebuje swojego stosu, rozważ użycie pamięci lokalnej wątku, aby zapewnić każdemu wątkowi oddzielną instancję stosu.

Chociaż stosy są rzeczywiście potężne, świadomość potencjalnych problemów z nimi związanych i aktywne wdrażanie rozwiązań zapewni niezawodne i wolne od błędów aplikacje. Rozpoznanie tych pułapek to połowa sukcesu – drugą połową jest przyjęcie najlepszych praktyk, aby skutecznie im zaradzić.

Wnioski

Stosy, pomimo pozornie prostej natury, stanowią podstawę wielu podstawowych operacji w świecie komputerów. Od analizowania złożonych wyrażeń matematycznych po zarządzanie wywołaniami funkcji – ich użyteczność jest szeroka i niezbędna. Kiedy zapoznaliśmy się z tajnikami tej struktury danych, stało się jasne, że jej siła leży nie tylko w wydajności, ale także w wszechstronności.

Jednak, jak w przypadku wszystkich narzędzi, jego skuteczność zależy od sposobu, w jaki jest używany. Upewnij się tylko, że dokładnie rozumiesz jego zasady, potencjalne pułapki i najlepsze praktyki, aby mieć pewność, że będziesz w stanie wykorzystać prawdziwą moc stosów. Niezależnie od tego, czy wdrażasz rozwiązanie od zera, czy korzystasz z wbudowanych funkcji w językach takich jak Python, to przemyślane zastosowanie tych struktur danych wyróżni Twoje rozwiązania.

• Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
• PlatoData.Network Pionowe generatywne AI. Wzmocnij się. Dostęp tutaj.
• PlatoAiStream. Inteligencja Web3. Wiedza wzmocniona. Dostęp tutaj.
• PlatonESG. Węgiel Czysta technologia, Energia, Środowisko, Słoneczny, Gospodarowanie odpadami. Dostęp tutaj.
• Platon Zdrowie. Inteligencja w zakresie biotechnologii i badań klinicznych. Dostęp tutaj.
• Źródło: https://stackabuse.com/guide-to-stacks-in-python/