Implementação e Aplicações de Pilhas
Implemente uma pilha com push/pop/peek e resolva valid-parentheses, min-stack e a avaliação de notação polonesa reversa.
Implementação e Aplicações de Pilhas é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
A estrutura de dados Stack
Uma pilha é uma estrutura de dados do tipo último a entrar, primeiro a sair (LIFO). O último elemento inserido com push é o primeiro elemento removido com pop. Pense em uma pilha de pratos: só é possível adicionar ou remover elementos pelo topo. As operações fundamentais são push (adicionar ao topo), pop (remover do topo) e peek (ler o topo sem remover). As três operações custam O(1) em uma pilha bem implementada.
Em Python, uma lista funciona perfeitamente como pilha: append corresponde a push, pop() corresponde a pop e [-1] corresponde 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 com push, pop, peek e isEmpty
Encapsular a lista em uma classe fornece uma interface mais limpa e evita o uso acidental de operações que não pertencem à pilha, como insert ou o uso de índices em posições diferentes do topo. Esta é a implementação que os entrevistadores esperam quando lhe pedem para "implementar uma pilha do 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)) # 2Parênteses válidos (LeetCode 20)
LeetCode 20 'Parênteses válidos': determine se uma cadeia de caracteres com delimitadores está balanceada. Para cada delimitador de abertura, faça push dele. Para cada delimitador de fechamento, verifique se o topo da pilha é o delimitador de abertura correspondente; caso contrário, ou se a pilha estiver vazia, retorne falso. Se a pilha estiver vazia ao final, a cadeia de caracteres será válida. Esta é a primeira aplicação clássica de uma pilha em entrevistas de programação.
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(']')) # FalsePilha mínima (LeetCode 155)
LeetCode 155 'Pilha mínima': projete uma pilha que ofereça push, pop, peek e getMin, todos em O(1). O truque é manter uma segunda pilha que acompanhe o mínimo em cada momento. Ao fazer push, faça também push na pilha de mínimos se o novo valor for <= o mínimo atual (ou se a pilha de mínimos estiver vazia). Ao fazer pop, faça também pop na pilha de mínimos se o valor removido for igual ao mínimo atual.
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()) # -2Avaliar a notação polonesa reversa
LeetCode 150 'Avaliar a notação polonesa reversa' (pós-fixa): os operandos são inseridos na pilha; ao encontrar um operador, faça pop de dois operandos, aplique o operador e faça push do resultado. A ordem é importante para subtração e divisão: o primeiro operando removido é o operando da direita, e o segundo é o da esquerda.
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','+'])) # 22Decodificar uma cadeia de caracteres (LeetCode 394)
LeetCode 394 'Decodificar uma cadeia de caracteres': dada uma cadeia codificada como 3[a2[c]], expanda-a para accaccacc. Use duas pilhas: uma para as contagens de repetições e outra para as cadeias acumuladas. Ao encontrar um dígito, forme o número completo. Ao encontrar [, faça push da cadeia e da contagem atuais. Ao encontrar ], faça pop e repita o segmento atual. Ao encontrar uma letra, acrescente-a à cadeia atual.
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'Temperaturas diárias (prévia de pilha monotônica)
LeetCode 739 'Temperaturas diárias': para cada dia, descubra quantos dias faltam até uma temperatura mais alta. Uma solução de força bruta custa O(n²). Com uma pilha, percorra as temperaturas; para cada dia, remova todas as entradas da pilha (índices de dias) cuja temperatura seja menor que a de hoje. A resposta para esses dias é a diferença entre o dia atual e o dia removido. Faça push do dia atual. As entradas restantes da pilha nunca encontraram um dia mais quente — a resposta para elas é 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 para percurso DFS
A pilha de chamadas usada na DFS recursiva pode ser substituída por uma pilha explícita, tornando o algoritmo iterativo. Faça push da raiz; enquanto a pilha não estiver vazia, faça pop de um nó, processe-o e faça push de seus filhos (primeiro o direito e depois o esquerdo, para processá-los da esquerda para a direita). Esta DFS iterativa tem o mesmo comportamento que a DFS recursiva, mas evita o limite de recursão do Python em árvores profundas.
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]Complexidade de tempo e espaço
Todas as operações de pilha (push, pop, peek, isEmpty) custam O(1) de forma amortizada. Construir uma pilha com n elementos custa O(n). O espaço é O(n) no pior caso, quando todos os elementos são armazenados. Em problemas que usam uma pilha monotônica, cada elemento é inserido e removido no máximo uma vez, resultando em um tempo total de O(n) ao longo de todas as iterações — e não O(n²), como poderia sugerir uma leitura ingênua do laço externo.
# 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}') # <= 2000Maior retângulo em um histograma (prévia)
LeetCode 84 'Maior retângulo em um histograma' é o problema clássico de pilha mais difícil. Para cada barra, o retângulo que ela pode formar se estende para a esquerda até encontrar uma barra mais baixa e para a direita até encontrar outra barra mais baixa. Uma pilha monotônica acompanha os índices das barras em ordem crescente de altura. Quando uma barra mais baixa é encontrada, remova elementos da pilha e calcule o retângulo usando a altura da barra removida. A pilha fornece os limites esquerdo e direito em O(1) por remoção.
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])) # 4Estratégia de entrevista para problemas de Stack
Os problemas de pilha muitas vezes se disfarçam como "processar de dentro para fora" ou "encontrar o próximo elemento maior/menor". Alguns sinais de que uma pilha pode ajudar: você precisa do elemento visto mais recentemente, está correspondendo pares (delimitadores, etiquetas) ou deseja obter O(n) em um problema que, de forma ingênua, exigiria laços aninhados O(n²). Em particular, as pilhas monotônicas transformam o problema de "encontrar, para cada elemento, o maior/menor mais próximo" de O(n²) em O(n).
Em uma entrevista, declare claramente a invariável da sua pilha: "Manterei uma pilha de índices em ordem decrescente de altura."
Verificação rápida
Avalie sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da lição
Nesta lição, você aprendeu que: as listas do Python implementam push, pop e peek em O(1), tornando-as pilhas ideais, parênteses válidos e pilha mínima são os dois problemas clássicos de pilha em entrevistas e pilhas monotônicas resolvem problemas do próximo elemento maior em O(n), inserindo e removendo cada elemento no máximo uma vez. A seguir, construiremos filas com o deque do Python e resolveremos o problema do máximo em uma janela deslizante.
Perguntas Frequentes
A aula “Implementação e Aplicações de Pilhas” é grátis?
Sim — o texto completo de “Implementação e Aplicações de Pilhas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Implementação e Aplicações de Pilhas”?
Implemente uma pilha com push/pop/peek e resolva valid-parentheses, min-stack e a avaliação de notação polonesa reversa. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Implementação e Aplicações de Pilhas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Implementação e Aplicações de Pilhas
- Implementação de Filas e Deque
- Padrão da Pilha Monotônica
- Simulação Mútua de Pilha e Fila