Implementazione e applicazioni dello stack
Implementi uno stack con push/pop/peek e risolva valid-parentheses, min-stack e la valutazione della notazione polacca inversa
Implementazione e applicazioni dello stack è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
La struttura dati stack
Uno stack è una struttura dati LIFO, cioè «ultimo a entrare, primo a uscire». L'ultimo elemento inserito è il primo a essere estratto. Si pensi a una pila di piatti: è possibile aggiungere o rimuovere elementi solo dalla cima. Le operazioni fondamentali sono push (aggiungere in cima), pop (rimuovere dalla cima) e peek (leggere l'elemento in cima senza rimuoverlo). In uno stack implementato correttamente, tutte e tre hanno complessità O(1).
In Python, una lista è perfetta per implementare uno stack: append corrisponde a push, pop() a pop e [-1] a peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Classe Stack con Push, Pop, Peek e isEmpty
Racchiudere la lista in una classe offre un'interfaccia più pulita e impedisce l'uso accidentale di operazioni che non appartengono a uno stack, come insert o l'indicizzazione in posizioni diverse dalla cima. Questa è l'implementazione che gli esaminatori si aspettano quando chiedono di «implementare uno stack da zero».
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Parentesi valide (LeetCode 20)
LeetCode 20 'Valid Parentheses': determinare se una stringa di parentesi è bilanciata. Per ogni parentesi di apertura, la si inserisce nello stack. Per ogni parentesi di chiusura, si verifica che l'elemento in cima allo stack sia la parentesi di apertura corrispondente; in caso contrario, oppure se lo stack è vuoto, si restituisce False. Se al termine lo stack è vuoto, la stringa è valida. Questa è la prima applicazione canonica di uno stack nei colloqui tecnici di programmazione.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalseStack del minimo (LeetCode 155)
LeetCode 155 'Min Stack': progettare uno stack che supporti push, pop, peek e getMin, tutti con complessità O(1). Il trucco consiste nel mantenere un secondo stack che memorizzi il minimo in ogni momento. Durante l'inserimento, si inserisce il nuovo valore anche nello stack dei minimi se è <= al minimo corrente (oppure se lo stack dei minimi è vuoto). Durante la rimozione, si rimuove un elemento anche dallo stack dei minimi se il valore estratto è uguale al minimo corrente.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Valutare la notazione polacca inversa
LeetCode 150 'Evaluate Reverse Polish Notation' (notazione postfissa): gli operandi vengono inseriti nello stack; quando si incontra un operatore, si estraggono due operandi, si applica l'operatore e si inserisce il risultato. L'ordine è importante per la sottrazione e la divisione: il primo operando estratto è quello a destra, il secondo è quello a sinistra.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Decodificare una stringa (LeetCode 394)
LeetCode 394 'Decode String': data una stringa codificata come 3[a2[c]], espanderla in accaccacc. Si usano due stack: uno per i conteggi delle ripetizioni e uno per le stringhe accumulate. Quando si incontra una cifra, si costruisce il numero completo. Quando si incontra [, si inseriscono nello stack la stringa e il conteggio correnti. Quando si incontra ], si estraggono e si ripete il segmento corrente. Quando si incontra una lettera, la si aggiunge alla stringa corrente.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Temperature giornaliere (anteprima dello stack monotono)
LeetCode 739 'Daily Temperatures': per ogni giorno, trovare dopo quanti giorni si verificherà una temperatura più alta. Un approccio esaustivo richiede O(n²). Con uno stack, si scorrono le temperature; per ogni giorno, si estraggono tutti gli elementi dello stack (indici dei giorni) la cui temperatura è inferiore a quella odierna. Per quei giorni, la risposta è (today - popped_day). Si inserisce quindi il giorno corrente nello stack. Gli elementi rimasti nello stack non hanno mai trovato un giorno più caldo: per loro la risposta è 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Stack per la visita DFS
Lo stack delle chiamate usato nella DFS ricorsiva può essere sostituito con uno stack esplicito, rendendo l'algoritmo iterativo. Si inserisce la radice; finché lo stack non è vuoto, si estrae un nodo, lo si elabora e si inseriscono i suoi figli (prima il destro e poi il sinistro, per elaborare da sinistra a destra). Questa DFS iterativa si comporta esattamente come quella ricorsiva, ma evita il limite di ricorsione di Python per gli alberi profondi.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Complessità temporale e spaziale
Tutte le operazioni dello stack (push, pop, peek, isEmpty) hanno complessità O(1)O(n) su tutte le iterazioni, non O(n²) come potrebbe suggerire una lettura ingenua del ciclo esterno.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Rettangolo più grande nell'istogramma (anteprima)
LeetCode 84 'Largest Rectangle in Histogram' è il più difficile tra i classici problemi con gli stack. Per ogni barra, il rettangolo che può avere come altezza quella della barra si estende verso sinistra finché non trova una barra più bassa e verso destra finché non trova una barra più bassa. Uno stack monotono memorizza gli indici delle barre in ordine crescente di altezza. Quando si incontra una barra più bassa, si estrae l'elemento e si calcola il rettangolo usando l'altezza della barra estratta. Lo stack fornisce i limiti sinistro e destro in O(1) per ogni estrazione.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Strategia per i problemi con gli stack
I problemi con gli stack spesso si presentano sotto forma di «elaborare dall'interno verso l'esterno» oppure «trovare l'elemento maggiore o minore successivo». Alcuni segnali che indicano l'utilità di uno stack sono: serve l'elemento visto più di recente, occorre associare coppie (parentesi, tag) oppure si vuole ottenere O(n) in un problema che, con un approccio ingenuo, richiederebbe cicli annidati O(n²). In particolare, gli stack monotoni trasformano il problema «trovare per ogni elemento il maggiore o minore più vicino» da O(n²) a O(n).
Durante un colloquio tecnico, esponga chiaramente l'invariante dello stack: «Manterrò uno stack di indici in ordine decrescente di altezza».
Verifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: le liste Python implementano push, pop e peek in O(1), rendendole stack ideali, le parentesi valide e il min stack sono i due problemi canonici sugli stack nei colloqui tecnici e gli stack monotoni risolvono i problemi dell'elemento maggiore successivo in O(n), inserendo ed estraendo ogni elemento al massimo una volta. Ora costruiremo le code con deque di Python e risolveremo il problema del massimo in una finestra scorrevole.
Domande Frequenti
La lezione «Implementazione e applicazioni dello stack» è gratuita?
Sì — il testo completo di «Implementazione e applicazioni dello stack» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Implementazione e applicazioni dello stack»?
Implementi uno stack con push/pop/peek e risolva valid-parentheses, min-stack e la valutazione della notazione polacca inversa Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Implementazione e applicazioni dello stack»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Implementazione e applicazioni dello stack
- Implementazione della coda e deque
- Schema dello stack monotono
- Simulazione reciproca di stack e coda