0x60Lição 7 de 13

Combine e ordene com pilhas e filas

Use estruturas LIFO e FIFO para aninhamento, desfazer e trabalho nível a nível.

20 min Questionário com 5 perguntas 1 exercício de código

Ao final desta lição, você saberá

Escolher entre uma pilha e uma fila.
Validar colchetes aninhados com uma pilha.
Usar um deque para operações de fila eficientes.

Uma pilha é last-in, first-out (LIFO): você empilha e desempilha na mesma ponta. Ela serve para qualquer coisa aninhada ou reversível - casar colchetes, histórico de desfazer, avaliar expressões, busca em profundidade. Uma fila é first-in, first-out (FIFO): acrescenta no fim e remove do começo. Ela serve para processar na ordem de chegada e para a busca em largura.

Pilhas e filas em Python

Pilha: uma list comum - append() empilha e pop() desempilha, os dois em O(1).
Fila: collections.deque - append() acrescenta e popleft() remove, os dois em O(1). Evite list.pop(0), que é O(n).
Pilha monotônica: uma pilha mantida em ordem crescente ou decrescente encontra o “próximo elemento maior” de cada item em O(n) no total.

solution.py

1def is_balanced(text):
2    pairs = {")": "(", "]": "[", "}": "{"}
3    stack = []
4    for char in text:
5        if char in "([{":
6            stack.append(char)
7        elif char in pairs:
8            if not stack or stack.pop() != pairs[char]:
9                return False
10    return not stack
11
12print(is_balanced("{[()()]}"), is_balanced("([)]"), is_balanced("(("))

Saída

True False False

Todo colchete de abertura espera na pilha pelo seu par; o abridor mais recente ainda sem par precisa fechar primeiro, que é exatamente a ordem LIFO. Dois casos extremos pegam muitos candidatos: um colchete de fechamento com a pilha vazia e abridores que sobram na pilha no fim.

Principais conclusões

Pilhas são LIFO: aninhamento, desfazer, DFS, problemas de pilha monotônica.
Filas são FIFO: ordem de chegada, BFS.
Use deque para filas em Python.

Quiz da aula

5 perguntas · aprovação com 4 acertos · até 50 XP

Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.

Pratique: resolva problemas de entrevistas técnicas

Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.

Exercício 1

Valide os colchetes

+25 XP

Leia uma string feita dos caracteres ()[]{}. Imprima valid se todo colchete for fechado pelo mesmo tipo na ordem certa; caso contrário, invalid.

Aninhados
Cruzados
Não fechado
Começa com um fechamento

main.py

Carregando editor…

O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.

Dúvidas sobre esta lição

Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.

Carregando publicações…