Python Language
Pila
Ricerca…
introduzione
Una pila è un contenitore di oggetti che vengono inseriti e rimossi secondo il principio LIFO (last-in first-out). Negli stack pushdown sono consentite solo due operazioni: spingere l'elemento nella pila e far uscire l'elemento dalla pila . Una pila è una struttura di dati ad accesso limitato: gli elementi possono essere aggiunti e rimossi dallo stack solo nella parte superiore . Ecco una definizione strutturale di una pila: una pila è vuota o è composta da una cima e il resto è una pila.
Sintassi
- stack = [] # Crea lo stack
- stack.append (oggetto) # Aggiungi oggetto all'inizio della pila
- stack.pop () -> oggetto # Restituisce la maggior parte degli oggetti in cima allo stack e la rimuove anche
- lista [-1] -> oggetto # Guarda l'oggetto più in alto senza rimuoverlo
Osservazioni
Da Wikipedia :
In informatica, uno stack è un tipo di dati astratto che funge da raccolta di elementi, con due operazioni principali: push , che aggiunge un elemento alla raccolta e pop , che rimuove l'ultimo elemento aggiunto che non è stato ancora rimosso.
A causa del modo in cui i loro elementi sono accessibili, le pile sono noti anche come Last-In, First-Out (LIFO) impila.
In Python si possono usare gli elenchi come stack con append() come push e pop() come operazioni pop. Entrambe le operazioni vengono eseguite in tempo costante O (1).
La struttura dati deque di Python può anche essere usata come una pila. Rispetto agli elenchi, i deque s consentono operazioni push e pop con una complessità temporale costante da entrambe le estremità.
Creazione di una classe di stack con un oggetto di elenco
Utilizzando un oggetto list è possibile creare uno stack generico completamente funzionale con metodi di supporto come sbirciare e verificare se lo stack è vuoto. Controlla i documenti Python ufficiali per l'utilizzo list come Stack qui .
#define a stack class
class Stack:
def __init__(self):
self.items = []
#method to check the stack is empty or not
def isEmpty(self):
return self.items == []
#method for pushing an item
def push(self, item):
self.items.append(item)
#method for popping an item
def pop(self):
return self.items.pop()
#check what item is on top of the stack without removing it
def peek(self):
return self.items[-1]
#method to get the size
def size(self):
return len(self.items)
#to view the entire stack
def fullStack(self):
return self.items
Un esempio di esecuzione:
stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
Produzione:
Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False
Analisi delle parentesi
Le pile vengono spesso utilizzate per l'analisi. Un semplice compito di analisi consiste nel verificare se una stringa di parentesi corrisponde.
Ad esempio, la stringa ([]) corrisponde, poiché le parentesi esterne e interne formano coppie. ()<>) non corrisponde, perché l'ultimo ) non ha un partner. ([)] non corrisponde, perché le coppie devono essere interamente all'interno o all'esterno di altre coppie.
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
# Checks to see whether the opening bracket matches the closing one
balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket:
return False
else:
return False
return not stack.isEmpty()
