6.1 Definizione dello stack e le sue proprietà
Lo Stack è una struttura dati astratta che rappresenta una collezione di elementi organizzati secondo il principio "ultimo arrivato, primo uscito" (Last In, First Out, LIFO). Puoi immaginare lo stack come una pila di libri: l'ultimo libro aggiunto si trova in cima alla pila e sarà il primo ad essere rimosso/preso.
Proprietà dello stack:
- LIFO (Last In, First Out): L'ultimo elemento aggiunto viene estratto per primo.
- Operazioni limitate: Lo stack supporta solo l'aggiunta (push), la rimozione (pop) e la visualizzazione (peek) dell'elemento in cima.
- Accesso unidirezionale: È possibile accedere agli elementi solo dalla cima dello stack.
- Semplicità di implementazione: Lo stack può essere facilmente implementato usando un array o una lista collegata.
- Gestione della memoria: Dati temporanei o stati possono essere conservati ed estratti in ordine inverso alla loro aggiunta.
Principio di funzionamento LIFO:
- Aggiunta di un elemento (push): Un nuovo elemento viene aggiunto in cima allo stack.
- Rimozione di un elemento (pop): L'ultimo elemento aggiunto viene rimosso dalla cima dello stack.
- Visualizzazione della cima (peek): Permette di vedere l'elemento in cima allo stack senza rimuoverlo.
Gli elementi dello stack vengono aggiunti e rimossi da un solo lato, chiamato cima (top). Pertanto, l'ultimo elemento aggiunto si trova sempre in cima ed è il primo ad essere rimosso.
6.2 Operazioni principali
Operazioni principali: push, pop, peek
Operazione push: Aggiunge un nuovo elemento in cima allo stack.
Complessità temporale: O(1).
Esempio di emulazione dello stack in Python usando la classe list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Output: [10, 20]
Operazione pop: Rimuove e restituisce l'elemento dalla cima dello stack.
Complessità temporale: O(1).
Esempio di emulazione dello stack in Python usando la classe list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Output: 20
print(stack) # Output: [10]
Operazione peek: Restituisce l'elemento in cima allo stack senza rimuoverlo.
Complessità temporale: O(1).
Esempio di implementazione:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Output: 10
6.3 Esempi d'uso dello stack
Vediamo alcuni esempi di utilizzo dello stack:
Gestione delle chiamate di funzione
In Python, lo stack viene utilizzato per tracciare le funzioni durante l'esecuzione del programma. Ogni volta che una funzione viene chiamata, il suo indirizzo di ritorno e le variabili locali sono posti nello stack. Quando la funzione termina l'esecuzione, il controllo torna alla funzione che l'ha chiamata, e i dati vengono estratti dallo stack.
Esempio di utilizzo dello stack delle chiamate:
In questo esempio, le chiamate ricorsive alla funzione factorial usano lo stack delle chiamate per memorizzare lo stato di ciascuna chiamata fino a quando non viene raggiunta la condizione base (n == 1).
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Output: 120
Annullamento delle operazioni (Undo)
Lo stack è utilizzato per implementare la funzione di annullamento in editor di testo e altre applicazioni. Quando l'utente esegue un'operazione, questa viene salvata nello stack. Quando viene eseguita l'operazione Undo, l'ultima azione viene estratta dallo stack e annullata.
Esempio di utilizzo dello stack per annullare operazioni:
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()
# Esempio di utilizzo:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Output: "Hello World"
editor.undo()
print(editor.text) # Output: "Hello"
editor.undo()
print(editor.text) # Output: ""
GO TO FULL VERSION