Tutorial sulla struttura dei dati dello stack Python
Implementa uno stack LIFO in Python. Esegui il nostro esempio di codice stack interattivo per padroneggiare i limiti di push, pop, peek e capacità.
Panoramica
Uno Stack è una struttura di dati lineare che segue il principio LIFO (Last-In, First-Out). Ciò significa che l'ultimo elemento aggiunto alla pila è il primo ad essere rimosso, in modo simile ad una pila di piatti.
Lo stack supporta due operazioni principali: push (aggiunge un elemento in cima) e pop (rimuove l'elemento aggiunto più recentemente). Inoltre, un'operazione di sbirciatina o dall'alto consente di ispezionare l'elemento superiore senza rimuoverlo.
In Python, gli stack possono essere facilmente costruiti utilizzando una lista con i metodi `.append()` e `.pop()`, o utilizzando l'oggetto `collections.deque` che offre operazioni ottimizzate sulla coda double-ended in tempo O(1).
Codice e output di esecuzione
Un'implementazione Stack personalizzata che utilizza la struttura dell'elenco di Python per emulare le funzioni push, pop e 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']Implementazione passo dopo passo
- Gestione delle funzioni di annullamento nei sistemi software
- Analisi della sintassi e controllo delle parentesi nei compilatori
- Tracciamento degli stack di chiamate di esecuzione durante la ricorsione nei motori
Domande frequenti
Perchécollections.deque è preferito rispetto a un normale elenco per Stacks?
Sebbene gli elenchi siano convenienti, sotto il cofano si tratta di array dinamici. Quando vengono ridimensionati, la riallocazione della memoria può richiedere tempo O(n). L'oggetto deque utilizza un'architettura a lista doppiamente concatenata, garantendo push e pop O(1).
Gli stack possono traboccare in Python?
Una classe stack standard in Python che utilizza array di elenchi crescerà fino a consumare tutta la memoria di sistema disponibile. Lo stack di ricorsione in Python, tuttavia, ha un limite predefinito (tipicamente 1000) per evitare che cicli infiniti blocchino l'interprete.
Argomenti correlati
Master operazioni coda FIFO in Python. Esegui ed esegui il nostro esempio di coda interattiva che mostra i metodi di accodamento e rimozione dalla coda.
Implementazione di elenchi concatenati singolarmente in PythonScopri come implementare un elenco collegato singolarmente in Python. Esplora l'allocazione dinamica della memoria, le operazioni dei nodi, l'inserimento, l'attraversamento e l'eliminazione.