Stos w Pythonie
Stos to popularna struktura danych oparta na zasadzie LIFO (Last In, First Out), co oznacza, że element dodany jako ostatni jest usuwany jako pierwszy.
Podstawowe operacje na stosie
Python nie ma wbudowanej klasy Stack, ale stos można łatwo zaimplementować za pomocą listy lub modułu collections.deque.
Implementacja za pomocą listy
stack = []
# Operacja push - dodawanie elementów
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) # Wynik: [10, 20, 30]
# Operacja pop - usuwanie ostatniego elementu
last_element = stack.pop()
print(last_element) # Wynik: 30
print(stack) # Wynik: [10, 20]
# Operacja peek - podglądanie ostatniego elementu (bez usuwania)
if stack: # Sprawdzenie, czy stos nie jest pusty
top_element = stack[-1]
print(top_element) # Wynik: 20Zastosowania stosu
Odwracanie ciągów znaków
Stos pozwala łatwo odwrócić ciąg znaków, ponieważ najpierw dodajemy (push) znaki na stos, a potem usuwamy je w odwrotnej kolejności (pop).
def reverse_string(s):
stack = []
# Dodajemy znaki na stos
for char in s:
stack.append(char)
# Zdejmujemy znaki ze stosu w odwrotnej kolejności
reversed_s = ''.join(stack.pop() for _ in range(len(stack)))
return reversed_s
print(reverse_string("Python")) # Wynik: nohtyPNawigacja wstecz/przód (np. w przeglądarce internetowej)
Można użyć dwóch stosów: jeden do historii wstecznej, drugi do przyszłej.
class BrowserNavigation:
def __init__(self):
self.back_stack = []
self.forward_stack = []
def visit(self, url):
if self.back_stack:
self.forward_stack.clear() # Po nowej wizycie czyścimy stos do przodu
self.back_stack.append(url)
print(f"Odwiedzono: {url}")
def back(self):
if self.back_stack:
self.forward_stack.append(self.back_stack.pop())
return self.back_stack[-1] if self.back_stack else "Brak poprzedniej strony"
return "Nie można cofnąć"
def forward(self):
if self.forward_stack:
url = self.forward_stack.pop()
self.back_stack.append(url)
return url
return "Nie można przejść do przodu"
# Przykład użycia
browser = BrowserNavigation()
browser.visit("example.com")
browser.visit("google.com")
browser.visit("openai.com")
print(browser.back()) # Wynik: google.com
print(browser.back()) # Wynik: example.com
print(browser.forward()) # Wynik: google.comAnaliza nawiasów w wyrażeniach
Stos może służyć do sprawdzania poprawności nawiasów w wyrażeniu matematycznym czy kodzie.
def is_valid_expression(expression):
stack = []
matching_brackets = {')': '(', '}': '{', ']': '['}
for char in expression:
if char in matching_brackets.values(): # Otwierające nawiasy
stack.append(char)
elif char in matching_brackets.keys(): # Zamykające nawiasy
if not stack or stack.pop() != matching_brackets[char]:
return False # Błąd: brak dopasowania
return not stack # Prawidłowe, jeśli stos jest pusty
# Przykład użycia
print(is_valid_expression("{[()]}")) # Wynik: True
print(is_valid_expression("{[(])}")) # Wynik: FalseZewnętrzne biblioteki
queue.LifoQueue
Choć nie jest zewnętrzną biblioteką, warto wspomnieć, że wbudowany moduł queue zawiera klasę LifoQueue, która działa jako stos i dodaje wsparcie dla operacji wielowątkowych.
from queue import LifoQueue
stack = LifoQueue()
stack.put(10) # push
stack.put(20)
stack.put(30)
print(stack.get()) # pop (Wynik: 30)
print(stack.get()) # pop (Wynik: 20)blist
blist to biblioteka, która oferuje zoptymalizowane struktury danych, w tym listy i deki, które mogą być używane jako stosy. Działa szybciej i zużywa mniej pamięci w porównaniu do wbudowanych list przy dużej liczbie elementów.
from blist import blist
stack = blist()
stack.append(10) # push
stack.append(20)
stack.append(30)
print(stack.pop()) # Wynik: 30stack
Prosta biblioteka przeznaczona wyłącznie do obsługi stosów. Obsługuje operacje takie jak push, pop, peek, a także pozwala na sprawdzanie rozmiaru i pustego stosu.
from stack import Stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # Wynik: 30
print(stack.peek()) # Wynik: 20
print(stack.size()) # Wynik: 2pycollections
Biblioteka pycollections dostarcza różnych struktur danych, w tym stosów, kolejek, czy zestawów, z bardziej rozbudowaną funkcjonalnością.
from pycollections import Stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # Wynik: 30
print(stack.peek()) # Wynik: 20
print(stack.is_empty()) # Wynik: Falsepystack
pystack to dedykowana biblioteka do implementacji stosów z dodatkowymi funkcjami, takimi jak operacje na pełnym stosie, wgląd w całą zawartość czy debugowanie.
from pystack import Stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.peek()) # Wynik: 30
print(stack.pop()) # Wynik: 30
print(stack.to_list()) # Wynik: [10, 20]datastructures
Biblioteka dostarczająca różne struktury danych, w tym stosy, z możliwością konfiguracji (np. ograniczenie rozmiaru stosu).
from datastructures.stack import Stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # Wynik: 30
print(stack.is_empty()) # Wynik: Falsemore-itertools
Biblioteka oferująca narzędzia do pracy z iterowalnymi strukturami, w tym stosami, umożliwiając bardziej zaawansowaną manipulację danych.
from more_itertools import always_reversible
stack = always_reversible([10, 20, 30])
print(next(stack)) # Wynik: 30 (działa jako stos)Porównanie bibliotek pod względem wydajności
| Biblioteka / Implementacja | Operacje push i pop (złożoność czasowa) | Uwagi |
|---|---|---|
list (wbudowana) | O(1) | Szybkie, ale może mieć dodatkowy koszt związany z realokacją pamięci. |
collections.deque | O(1) | Bardzo szybka i wydajna dla stosów. Brak obsługi zaawansowanych funkcji jak peek. |
queue.LifoQueue | O(1) | Bezpieczne dla wielowątkowości, ale wolniejsze przez blokady (locks). |
blist | O(log N) | Wolniejsze dla pojedynczych operacji, ale optymalniejsze dla dużych struktur. |
stack (zewnętrzna) | O(1) | Dedykowana, minimalistyczna implementacja, wydajna jak lista. |
pycollections.Stack | O(1) | Porównywalna do stack, ale z dodatkowymi funkcjami jak is_empty. |
pystack | O(1) | Nieco wolniejsza przez dodatkowe funkcje debugowania. |
datastructures.Stack | O(1) | Porównywalna do stack, prostsza, brak blokad wielowątkowych. |
