6.1 Definicja stosu i jego właściwości
Stos — to abstrakcyjna struktura danych, która reprezentuje kolekcję elementów zorganizowaną na zasadzie "ostatni wszedł — pierwszy wyszedł" (Last In, First Out, LIFO). Można go sobie wyobrazić jak stos książek: ostatnio dodana książka znajduje się na szczycie stosu i zostanie usunięta/pobrana pierwsza.
Właściwości stosu:
- LIFO (Last In, First Out): Ostatnio dodany element jest usuwany jako pierwszy.
- Ograniczone operacje: Stos wspiera tylko dodawanie (push), usuwanie (pop) i przeglądanie (peek) elementu na szczycie.
- Jednokierunkowy dostęp: Dostęp do elementów jest możliwy tylko od szczytu stosu.
- Łatwość implementacji: Stos można łatwo zaimplementować za pomocą tablicy lub listy powiązanej.
- Zarządzanie pamięcią: Tymczasowe dane lub stany mogą być przechowywane i pobierane w odwrotnej kolejności dodania.
Zasada działania LIFO:
- Dodawanie elementu (push): Nowy element jest dodawany na szczyt stosu.
- Usuwanie elementu (pop): Ostatnio dodany element jest usuwany ze szczytu stosu.
- Przeglądanie szczytu (peek): Pozwala zobaczyć element na szczycie stosu bez jego usuwania.
Elementy stosu są dodawane i usuwane z jednej strony, zwanej szczytem (top). W ten sposób ostatnio dodany element zawsze znajduje się na szczycie i zostanie usunięty pierwszy.
6.2 Podstawowe operacje
Podstawowe operacje: push, pop, peek
Operacja push: Dodaje nowy element na szczyt stosu.
Złożoność czasowa: O(1).
Przykład emulacji stosu w Pythonie za pomocą klasy list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Wyjście: [10, 20]
Operacja pop: Usuwa i zwraca element ze szczytu stosu.
Złożoność czasowa: O(1).
Przykład emulacji stosu w Pythonie za pomocą klasy list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Wyjście: 20
print(stack) # Wyjście: [10]
Operacja peek: Zwraca element na szczycie stosu bez jego usuwania.
Złożoność czasowa: O(1).
Przykład implementacji:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Wyjście: 10
6.3 Przykłady użycia stosu
Podajmy kilka przykładów użycia stosu:
Zarządzanie wywołaniami funkcji
W Pythonie stos jest używany do śledzenia funkcji podczas wykonywania programu. Za każdym razem, gdy funkcja jest wywoływana, jej adres zwrotny i lokalne zmienne są umieszczane na stosie. Gdy funkcja kończy wykonywanie, kontrola wraca do funkcji, która ją wywołała, a dane są pobierane ze stosu.
Przykład użycia stosu wywołań:
W tym przykładzie rekursywne wywołania funkcji factorial używają stosu wywołań do przechowywania stanu każdego wywołania, dopóki nie zostanie osiągnięty warunek bazowy (n == 1).
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Wyjście: 120
Cofanie operacji (Undo)
Stos jest używany do implementacji funkcji cofania działań w edytorach tekstu i innych aplikacjach. Gdy użytkownik wykonuje akcję, jest ona zapisywana na stosie. Podczas wykonywania operacji Undo ostatnie działanie jest pobierane ze stosu i cofane.
Przykład użycia stosu do cofania operacji:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Przykład użycia:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Wyjście: "Hello World"
editor.undo()
print(editor.text) # Wyjście: "Hello"
editor.undo()
print(editor.text) # Wyjście: ""
GO TO FULL VERSION