Pilhas, filas e deques

A restrição é a funcionalidade

Uma pilha é uma pilha de pratos: você só alcança o de cima. Isso parece uma limitação até você perceber que é exatamente o comportamento que quer para o botão "desfazer", para o histórico de chamadas de função e para avaliar expressões aninhadas — situações em que "o último que aconteceu" é sempre o que importa primeiro.

Uma fila é a fila do caixa: quem chegou primeiro é atendido primeiro. É a estrutura da justiça e da ordem de chegada — jobs de impressão, requisições num servidor, mensagens entre serviços, e a busca em largura num grafo.

Um deque (pronuncia-se "deck", de double-ended queue) permite as duas pontas. Com ele você tem pilha e fila ao mesmo tempo — e ganha casos que nenhuma das duas resolve sozinha, como uma janela deslizante que cresce por um lado e encolhe pelo outro.

O buffer circular e a fila feita de duas pilhas

Na primeira aba, veja os índices head e size darem a volta no array sem que nenhum elemento se mova. Na segunda, o truque clássico de construir uma fila usando somente pilhas — e por que ele é O(1) amortizado.

Três interfaces, não três estruturas

# Pilha, fila e deque não são estruturas — são INTERFACES.
# Cada uma restringe deliberadamente o que você pode fazer,
# e é essa restrição que garante o O(1).

# PILHA (stack) — LIFO: só mexe no topo
push(x)     # adiciona no topo        O(1)
pop()       # remove e devolve o topo O(1)
peek()      # olha o topo sem remover O(1)

# FILA (queue) — FIFO: entra atrás, sai na frente
enqueue(x)  # adiciona no fim         O(1)
dequeue()   # remove da frente        O(1)

# DEQUE — as duas pontas
push_front(x) / push_back(x)    # O(1)
pop_front()   / pop_back()      # O(1)

# Repare no que NÃO existe em nenhuma delas:
#   - acesso por índice
#   - inserção no meio
#   - busca por valor
# Justamente as operações que custariam O(n).

Na prática, em Python

# Em Python
# --- PILHA: list já serve ---
pilha = []
pilha.append("a")     # push — O(1) amortizado
topo = pilha.pop()    # pop  — O(1)

# --- FILA: NUNCA use list ---
fila = []
fila.append("a")
fila.pop(0)           # ⚠️ O(n) — desloca todo o array!

from collections import deque
fila = deque()
fila.append("a")      # enqueue    — O(1)
fila.popleft()        # dequeue    — O(1)
fila.appendleft("z")  # push_front — O(1)
fila.pop()            # pop_back   — O(1)

# deque com tamanho máximo: descarta o mais antigo sozinho.
# Perfeito para "últimas N mensagens" ou média móvel.
ultimos = deque(maxlen=100)

# --- FILA THREAD-SAFE (entre threads) ---
from queue import Queue
q = Queue()           # com locks internos; use esta com threads

Por dentro: o buffer circular

# Buffer circular: a implementação clássica de um deque.
class BufferCircular:
    def __init__(self, capacidade):
        self.buf = [None] * capacidade
        self.cap = capacidade
        self.head = 0      # índice do primeiro elemento
        self.tamanho = 0

    def push_back(self, x):
        if self.tamanho == self.cap: raise Exception("cheio")
        self.buf[(self.head + self.tamanho) % self.cap] = x
        self.tamanho += 1

    def push_front(self, x):
        if self.tamanho == self.cap: raise Exception("cheio")
        self.head = (self.head - 1) % self.cap       # anda para trás, dá a volta
        self.buf[self.head] = x
        self.tamanho += 1

    def pop_front(self):
        if not self.tamanho: raise Exception("vazio")
        x = self.buf[self.head]
        self.buf[self.head] = None
        self.head = (self.head + 1) % self.cap
        self.tamanho -= 1
        return x

# O segredo inteiro é o "% cap": os índices dão a volta.
# Nenhum elemento jamais se move na memória — só os índices andam.
# Por isso todas as quatro operações são O(1) de verdade.

Pilha na prática: delimitadores balanceados

# O uso mais clássico de pilha: verificar delimitadores balanceados.
# É literalmente o que seu editor faz para colorir o par de chaves.
def balanceado(texto):
    pares = {")": "(", "]": "[", "}": "{"}
    pilha = []
    for c in texto:
        if c in "([{":
            pilha.append(c)
        elif c in pares:
            if not pilha or pilha.pop() != pares[c]:
                return False          # fechou o que não estava aberto
    return not pilha                # sobrou algo aberto?

balanceado("((a+b)*c)")   # True
balanceado("([)]")        # False — a ordem importa, e a pilha captura isso

# Por que pilha e não um contador?
# Um contador aceitaria "([)]" como válido. A pilha lembra
# QUAL delimitador foi aberto por último — e "por último" é
# exatamente a semântica LIFO.

Construindo do zero

Mini projeto: implemente uma calculadora de notação polonesa reversa (RPN). A entrada "3 4 + 2 *" deve dar 14. O algoritmo cabe em 10 linhas com uma pilha: número você empilha; operador você desempilha dois, aplica e empilha o resultado. Depois estenda para converter expressões infixas comuns (3 + 4 * 2) para RPN com o algoritmo shunting-yard de Dijkstra — que usa uma segunda pilha para os operadores.

Projeto principal: implemente o BufferCircular acima e use-o como buffer de log de tamanho fixo: as últimas 1000 linhas de log de um servidor, onde escrever a linha 1001 sobrescreve a primeira automaticamente. Meça o tempo de 1 milhão de escritas e compare com uma list que faz pop(0) quando passa de 1000 elementos.

Desafio extra: o problema do máximo em janela deslizante. Dado um array e uma janela de tamanho k, devolva o máximo de cada janela. A solução ingênua é O(n·k). Com um deque que guarda índices em ordem decrescente de valor — removendo pela frente os que saíram da janela e por trás os que ficaram menores que o novo elemento — o custo cai para O(n), com cada elemento entrando e saindo do deque no máximo uma vez.

Teste sua intuição

Onde você encontra isso