Mod 01 Fundamentos Da Computacao • Trilha Progressiva em 4 Níveis

🎯 Nível 1: Fundamentos

Problema 05.1 — Lista Simplesmente Encadeada com Nós em Python Puro

Contexto: Lista Simplesmente Encadeada com Nós em Python Puro no contexto de Estruturas de Dados Lineares: Listas, Pilhas e Filas.

Requisitos de Execução:

  1. Criar estrutura de nós encadeados com operações inserir_inicio, inserir_fim e imprimir.

Resultado Esperado

Lista Encadeada: [10] -> [20] -> [30] -> NULL

📤 Instruções de Entrega (Microsoft Teams)

  1. Salve o arquivo como: Atividade_05_1_SeuNome
  2. Envie na tarefa: Atividade Cap 05 - Estruturas de Dados Lineares: Listas, Pilhas e Filas
🔑 Gabarito de Código & Solução Comentada 
# singly_linked_list.py
class Node:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None

class SinglyLinkedList:
    def __init__(self):
        self.cabeca = None

    def inserir_fim(self, val):
        novo = Node(val)
        if not self.cabeca: self.cabeca = novo; return
        atual = self.cabeca
        while atual.proximo: atual = atual.proximo
        atual.proximo = novo

    def imprimir(self):
        elementos, atual = [], self.cabeca
        while atual:
            elementos.append(f"[{atual.valor}]")
            atual = atual.proximo
        print(" -> ".join(elementos) + " -> NULL")

lista = SinglyLinkedList()
lista.inserir_fim(10); lista.inserir_fim(20); lista.inserir_fim(30)
lista.imprimir()

🔍 Nível 2: Prática

Problema 05.2 — Avaliador de Expressões em Notação Polonesa Reversa (RPN) com Pilha

Contexto: Avaliador de Expressões em Notação Polonesa Reversa (RPN) com Pilha no contexto de Estruturas de Dados Lineares: Listas, Pilhas e Filas.

Requisitos de Execução:

  1. Implementar pilha LIFO para avaliar expressões pós-fixas (ex.: 3 4 + 2 * 7 /).

Resultado Esperado

Expressão RPN '3 4 + 2 *' -> Resultado: 14

📤 Instruções de Entrega (Microsoft Teams)

  1. Salve o arquivo como: Atividade_05_2_SeuNome
  2. Envie na tarefa: Atividade Cap 05 - Estruturas de Dados Lineares: Listas, Pilhas e Filas
🔑 Gabarito de Código & Solução Comentada 
# rpn_evaluator.py
def avaliar_rpn(expressao):
    pilha = []
    tokens = expressao.split()
    for t in tokens:
        if t.isdigit():
            pilha.append(int(t))
        else:
            b = pilha.pop()
            a = pilha.pop()
            if t == '+': pilha.append(a + b)
            elif t == '-': pilha.append(a - b)
            elif t == '*': pilha.append(a * b)
            elif t == '/': pilha.append(a // b)
    return pilha[0]

expr = "3 4 + 2 *"
print(f"RPN '{expr}' = {avaliar_rpn(expr)}")

⚡ Nível 3: Integração

Problema 05.3 — Fila Circular Baseada em Array com Controle de Ponteiros

Contexto: Fila Circular Baseada em Array com Controle de Ponteiros no contexto de Estruturas de Dados Lineares: Listas, Pilhas e Filas.

Requisitos de Execução:

  1. Implementar fila FIFO circular com capacidade fixa, ponteiros front e rear e controle de overflow.

Resultado Esperado

Fila: Enqueue(10), Enqueue(20), Dequeue() -> Retorna 10 | Tamanho restante: 1

📤 Instruções de Entrega (Microsoft Teams)

  1. Salve o arquivo como: Atividade_05_3_SeuNome
  2. Envie na tarefa: Atividade Cap 05 - Estruturas de Dados Lineares: Listas, Pilhas e Filas
🔑 Gabarito de Código & Solução Comentada 
# circular_queue.py
class FilaCircular:
    def __init__(self, capacidade=5):
        self.capacidade = capacidade
        self.fila = [None] * capacidade
        self.front = 0
        self.rear = 0
        self.tamanho = 0

    def enqueue(self, item):
        if self.tamanho == self.capacidade: raise OverflowError("Fila cheia")
        self.fila[self.rear] = item
        self.rear = (self.rear + 1) % self.capacidade
        self.tamanho += 1

    def dequeue(self):
        if self.tamanho == 0: raise IndexError("Fila vazia")
        item = self.fila[self.front]
        self.fila[self.front] = None
        self.front = (self.front + 1) % self.capacidade
        self.tamanho -= 1
        return item

q = FilaCircular(3)
q.enqueue("A"); q.enqueue("B")
print("Dequeue:", q.dequeue())
q.enqueue("C")
print("Estado Fila:", q.fila)

🏆 Nível 4: Desafio Corporativo

Problema 05.4 — Deque (Double-Ended Queue) Duplamente Encadeado em O(1)

Contexto: Deque (Double-Ended Queue) Duplamente Encadeado em O(1) no contexto de Estruturas de Dados Lineares: Listas, Pilhas e Filas.

Requisitos de Execução:

  1. Implementar Deque com nós duplamente encadeados e operações append_left, append_right, pop_left, pop_right.

Resultado Esperado

Deque Operando: AppendLeft(1), AppendRight(2) -> PopLeft(): 1 | PopRight(): 2

📤 Instruções de Entrega (Microsoft Teams)

  1. Salve o arquivo como: Atividade_05_4_SeuNome
  2. Envie na tarefa: Atividade Cap 05 - Estruturas de Dados Lineares: Listas, Pilhas e Filas
🔑 Gabarito de Código & Solução Comentada 
# double_ended_queue.py
class DNode:
    def __init__(self, v): self.v, self.prev, self.next = v, None, None

class Deque:
    def __init__(self): self.head, self.tail = None, None

    def append_right(self, val):
        n = DNode(val)
        if not self.tail: self.head = self.tail = n
        else:
            self.tail.next = n; n.prev = self.tail; self.tail = n

    def pop_left(self):
        if not self.head: raise IndexError("Vazio")
        v = self.head.v
        self.head = self.head.next
        if self.head: self.head.prev = None
        else: self.tail = None
        return v

d = Deque()
d.append_right(100); d.append_right(200)
print(f"Pop Left: {d.pop_left()}")
print(f"Pop Left: {d.pop_left()}")