📚 Pré-requisitos Teóricos: este projeto aplica conceitos ensinados em Módulo 09: Estruturas de Dados. Recomendado revisar antes de começar.

📦 Biblioteca de Estruturas de Dados Avançadas & Big-O

v1.0 — Pilhas, Filas, Listas Duplamente Encadeadas e Hash Tables

Trilha de Especialização Pedagógica — Projeto 1 de 4

🎓 Nível Profissional Simulado: Engenheiro de Software Júnior. Saber escolher entre um Array e uma LinkedList ou entender como uma HashTable lida com colisões em $O(1)$ é o teste técnico padrão das principais empresas de tecnologia do mundo (FAANG / Big Techs).

—`

🎯 Objetivo & Escopo do Projeto

Construir do zero uma biblioteca de Estruturas de Dados Fundamentais contendo Pilhas (LIFO), Filas (FIFO), Listas Duplamente Encadeadas com ponteiros anterior/próximo e uma Tabela Hash com resolução de colisões por encadeamento separado, acompanhada da análise assintótica de complexidade Big-O de cada método.

—`

🧑‍💼 Fase 1 — Levantamento de Requisitos

O Briefing do Cliente (Arquiteto de Sistemas de Alta Performance)

“Nossa aplicação de processamento de logs sofre com travamentos porque o time usa listas simples para fazer buscas com contains(), o que gera custo $O(n)$ em 2 milhões de registros. Precisamos de uma biblioteca de estruturas de dados padrão da empresa, com Listas Duplamente Encadeadas para inserção $O(1)$ e uma Tabela Hash customizada para indexação rápida $O(1)$ com tratamento rigoroso de colisões.”

Requisitos Funcionais (RF) e Não-Funcionais (RNF)

ID Tipo Descrição Origem no Briefing
RF01 Funcional Implementar Lista Duplamente Encadeada com inserção no início e fim em tempo constante $O(1)$. “inserção O(1)”
RF02 Funcional Implementar Pilha (LIFO) com operações push, pop e peek. “estruturas padrão”
RF03 Funcional Implementar Tabela Hash com hashing modular e resolução de colisões por encadeamento. “indexação rápida O(1) com colisões”
RNF01 Não-Funcional Complexidade temporal média de $O(1)$ para operações na Tabela Hash. Alta Performance
RNF02 Não-Funcional Implementação manual pura sem depender dos tipos internos dict ou collections. Fundamentos de Computação

—`

📋 Fase 2 — Backlog & User Stories

ID User Story Prioridade
US01 Como engenheiro, quero inserir elementos na lista encadeada sem realocação de array em memória. Alta
US02 Como desenvolvedor, quero recuperar valores por chave na Hash Table em tempo $O(1)$. Alta

—`

🌿 Fase 3 — Engenharia em Equipe (Git Flow & Setup)

# Branch da funcionalidade
git checkout -b feature/US02-tabela-hash-encadeada

# Executar a biblioteca e testes
python src/estruturas_core.py

—`

🛠️ Fase 4 — Implementação Guiada (src/estruturas_core.py)

class TabelaHashEncadeada:
    def __init__(self, capacidade=16):
        self.capacidade = capacidade
        self.baldes = [[] for _ in range(capacidade)]

    def _hash(self, chave):
        return hash(chave) % self.capacidade

    def inserir(self, chave, valor):
        indice = self._hash(chave)
        for i, (k, v) in enumerate(self.baldes[indice]):
            if k == chave:
                self.baldes[indice][i] = (chave, valor)
                return
        self.baldes[indice].append((chave, valor))

—`

🚀 Como Executar no Laboratório

1. Abra o terminal na pasta deste projeto

No seu editor/IDE, abra a pasta deste projeto (File > Open Folder) ou navegue via terminal:

cd algoritmos_01_estruturas_dados

2. Execute a aplicação ou testes

go run main.go
# ou python main.py

[!TIP] Dica para execução a partir da raiz do repositório: Se você abriu o repositório completo no VS Code, basta navegar até a pasta antes de executar: cd proj_aplicacoes_full_stack/projetos/algoritmos_01_estruturas_dados`

🧭 Decisões de Arquitetura (ADRs)

—`

🧪 Testes de Validação & Asserções

th = TabelaHashEncadeada(capacidade=4)
th.inserir("id:1", "Valor A")
th.inserir("id:5", "Valor B") # Força colisão no mesmo balde
assert th.buscar("id:1") == "Valor A"
assert th.buscar("id:5") == "Valor B"

—`

✅ Checkpoint Final

  1. Todas as estruturas lineares implementadas e testadas com asserções.
  2. Tratamento de colisão na Hash Table validado.
⬅️ Ver Todos os Projetos no Super-Hub 🏠 Página Inicial do Portal