Estruturas de dados fundamentais

Cada estrutura foi projetada para um padrão de acesso

Um array é como uma caixa de ovos numerada: acesso direto pelo índice em O(1), mas inserir no meio exige mover tudo — O(n). Uma pilha é como uma pilha de pratos: só acessa o topo, mas push e pop são sempre O(1). Uma fila é como uma fila de banco: entra pelo fundo, sai pela frente, ambas O(1). Uma hash table é como um armário com etiquetas: dado o nome da etiqueta, vai direto ao compartimento — O(1) em média.

Pilha, fila e hash table em ação

Interaja com cada estrutura e observe o comportamento de push/pop, enqueue/dequeue e inserção com hash.

Tabela de complexidades

# Complexidades de operações das estruturas principais:
#
# Estrutura    | Acesso  | Busca  | Inserção | Remoção
# -------------|---------|--------|----------|--------
# Array        | O(1)    | O(n)   | O(n)     | O(n)
# Linked list  | O(n)    | O(n)   | O(1)*    | O(1)*
# Stack        | O(n)    | O(n)   | O(1)     | O(1)
# Queue        | O(n)    | O(n)   | O(1)     | O(1)
# Hash table   | O(1)*   | O(1)*  | O(1)*    | O(1)*
#
# * caso médio (hash: pior caso O(n) com muitas colisões)
# * lista ligada: O(1) inserção SE já tiver o ponteiro do nó anterior

# Python: as estruturas nativas
lista = [1, 2, 3]           # array dinâmico (como ArrayList do Java)
lista.append(4)             # O(1) amortizado
lista.insert(0, 0)          # O(n) — desloca todos os elementos

pilha = []                  # use lista como pilha
pilha.append("a")           # push — O(1)
top = pilha.pop()           # pop  — O(1)

from collections import deque
fila = deque()              # use deque como fila
fila.append("a")            # enqueue — O(1)
front = fila.popleft()      # dequeue — O(1) (list.pop(0) seria O(n)!)

tabela = {}                  # hash table nativa (dict)
tabela["chave"] = "valor"   # insert — O(1) médio
v = tabela.get("chave")     # lookup — O(1) médio

Como a hash table funciona internamente

# Como funciona uma hash table por dentro
class HashTableSimples:
    def __init__(self, tamanho=8):
        self.buckets = [[] for _ in range(tamanho)]
        self.tamanho = tamanho

    def _hash(self, chave):
        return hash(chave) % self.tamanho   # função hash

    def inserir(self, chave, valor):
        i = self._hash(chave)
        for par in self.buckets[i]:        # colisão: encadeamento
            if par[0] == chave:
                par[1] = valor; return
        self.buckets[i].append([chave, valor])

    def buscar(self, chave):
        i = self._hash(chave)
        for par in self.buckets[i]:
            if par[0] == chave: return par[1]
        return None

# Colisão: duas chaves diferentes mapeiam para o mesmo bucket
# "gato" e "tago" podem ter o mesmo hash % 8
# Resolução por encadeamento: bucket vira uma lista ligada

Implementando do zero

Mini projeto: use uma pilha (lista Python) para verificar se uma expressão tem parênteses balanceados: ((a+b)*c) é válida, ((a+b não é. Para cada ( empilhe; para cada ) desempilhe. Se a pilha estiver vazia ao final e todos os fechamentos encontraram abertura, a expressão é válida. Estenda para {} e [].

Projeto principal: implemente um sistema de cache LRU (Least Recently Used) — quando o cache está cheio, remove o item usado há mais tempo. Use um dict (hash table) para lookup O(1) e um deque (fila duplamente encadeada) para rastrear a ordem de uso. Essa combinação é exatamente como o functools.lru_cache do Python funciona internamente.

Desafio extra: implemente uma fila com dois stacks. A ideia: um stack para enqueue, outro para dequeue. Quando o stack de dequeue estrazia, mova tudo do stack de enqueue para ele (inverte a ordem). Prove que o custo amortizado por operação é O(1). Essa é uma pergunta clássica de entrevista técnica.

Teste sua intuição

Onde você encontra isso