Samouczek dotyczący struktury danych stosu w języku Python
Zaimplementuj stos LIFO w Pythonie. Uruchom nasz przykładowy interaktywny kod stosu, aby opanować limity push, pop, peek i pojemności.
Przegląd
Stos to liniowa struktura danych zgodna z zasadą „ostatnie przyszło, pierwsze wyszło” (LIFO). Oznacza to, że ostatni element dodany do stosu jest pierwszym, który należy usunąć, podobnie jak stos talerzy.
Stos obsługuje dwie główne operacje: push (dodaje element na górę) i pop (usuwa ostatnio dodany element). Dodatkowo operacja podglądu lub góry umożliwia sprawdzenie górnego elementu bez jego demontażu.
W Pythonie stosy można łatwo budować przy użyciu listy z metodami `.append()` i `.pop()` lub przy użyciu obiektu `collections.deque`, który oferuje zoptymalizowane operacje na kolejkach dwustronnych w czasie O(1).
Dane wyjściowe kodu i wykonania
Niestandardowa implementacja stosu wykorzystująca strukturę list Pythona do emulacji funkcji push, pop i peek.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
print(f"Pushed: {item}")
def pop(self):
if self.is_empty():
return "Underflow: Stack is empty"
popped = self.items.pop()
print(f"Popped: {popped}")
return popped
def peek(self):
if self.is_empty():
return "Stack is empty"
return self.items[-1]
def size(self):
return len(self.items)
# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")
print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")
stack.pop()
print(f"Stack after Pop: {stack.items}")Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']Wdrażanie krok po kroku
- Zarządzanie funkcjami cofania w systemach oprogramowania
- Analiza składni i sprawdzanie nawiasów w kompilatorach
- Śledzenie stosów wywołań wykonania podczas rekurencji w wyszukiwarkach
Często zadawane pytania
Dlaczego kolekcja.deque jest preferowana zamiast zwykłej listy dla stosów?
Listy są wprawdzie wygodne, ale pod maską stanowią dynamiczne tablice. Po zmianie rozmiaru ponowna alokacja pamięci może zająć czas O(n). Obiekt deque wykorzystuje architekturę list podwójnie połączonych, gwarantując wypychanie i wyskakiwanie O(1).
Czy stosy mogą się przepełniać w Pythonie?
Standardowa klasa stosu w Pythonie korzystająca z tablic listowych będzie rosła, aż zużyje całą dostępną pamięć systemową. Jednak stos rekurencji w Pythonie ma domyślny limit (zwykle 1000), aby zapobiec awarii interpretera przez nieskończone pętle.
Powiązane tematy
Opanuj operacje kolejkowe FIFO w Pythonie. Wykonaj i uruchom nasz interaktywny przykład kolejki prezentujący metody umieszczania w kolejce i usuwania z kolejki.
Implementacja listy pojedynczo połączonej w PythonieDowiedz się, jak zaimplementować pojedynczo połączoną listę w Pythonie. Przeglądaj dynamiczną alokację pamięci, operacje na węzłach, wstawianie, przeglądanie i usuwanie.