💻 Exemplos: Capítulo 05: Estruturas de Dados Lineares

Exemplos de Código: Capítulo 05 — Estruturas de Dados Lineares

Módulo 01: Fundamentos da Computação • Demonstrações Práticas Executáveis

---

💻 Código de Demonstração: Lista Ligada, Pilha (LIFO) e Fila Circular (FIFO)

O script a seguir implementa manualmente as principais estruturas de dados lineares sem uso de bibliotecas de alto nível: uma Lista Simplesmente Ligada com inversão in-place, uma Pilha para verificação de balanceamento de delimitadores e uma Fila Circular baseada em array com ponteiros de leitura e escrita.

"""
Fundamentos da Computação - Módulo 01 / Capítulo 05
Implementação de Estruturas de Dados Lineares: Lista Ligada, Pilha e Fila Circular
"""

from typing import Any, Optional


# =====================================================================
# 1. Lista Simplesmente Encadeada (Linked List)
# =====================================================================

class Nodo:
    def __init__(self, valor: Any, proximo: Optional['Nodo'] = None):
        self.valor = valor
        self.proximo = proximo

class ListaEncadeada:
    def __init__(self):
        self.cabeca: Optional[Nodo] = None
        self.tamanho: int = 0

    def inserir_inicio(self, valor: Any) -> None:
        novo = Nodo(valor, self.cabeca)
        self.cabeca = novo
        self.tamanho += 1

    def inserir_fim(self, valor: Any) -> None:
        novo = Nodo(valor)
        if not self.cabeca:
            self.cabeca = novo
        else:
            atual = self.cabeca
            while atual.proximo:
                atual = atual.proximo
            atual.proximo = novo
        self.tamanho += 1

    def reverter(self) -> None:
        """Inverte os ponteiros da lista in-place em O(n) tempo e O(1) espaço."""
        anterior = None
        atual = self.cabeca
        while atual:
            proximo_no = atual.proximo
            atual.proximo = anterior
            anterior = atual
            atual = proximo_no
        self.cabeca = anterior

    def para_lista(self) -> list:
        elementos = []
        atual = self.cabeca
        while atual:
            elementos.append(atual.valor)
            atual = atual.proximo
        return elementos


# =====================================================================
# 2. Pilha (Stack - LIFO) e Validador de Expressões
# =====================================================================

class Pilha:
    def __init__(self):
        self._itens = []

    def empilhar(self, item: Any) -> None:
        self._itens.append(item)

    def desempilhar(self) -> Any:
        if self.esta_vazia():
            raise IndexError("Desempilhamento em pilha vazia.")
        return self._itens.pop()

    def topo(self) -> Any:
        if self.esta_vazia():
            return None
        return self._itens[-1]

    def esta_vazia(self) -> bool:
        return len(self._itens) == 0

def validar_parenteses(expressao: str) -> bool:
    """Verifica se chaves {}, colchetes [] e parênteses () estão balanceados."""
    pilha = Pilha()
    pares = {')': '(', ']': '[', '}': '{'}

    for char in expressao:
        if char in "({[":
            pilha.empilhar(char)
        elif char in ")}]":
            if pilha.esta_vazia() or pilha.desempilhar() != pares[char]:
                return False
    return pilha.esta_vazia()


# =====================================================================
# 3. Fila Circular (Queue - FIFO com Buffer Fixo)
# =====================================================================

class FilaCircular:
    def __init__(self, capacidade: int):
        self.capacidade = capacidade
        self.buffer = [None] * capacidade
        self.inicio = 0
        self.fim = 0
        self.total = 0

    def enfileirar(self, item: Any) -> bool:
        if self.total == self.capacidade:
            return False  # Fila cheia
        self.buffer[self.fim] = item
        self.fim = (self.fim + 1) % self.capacidade
        self.total += 1
        return True

    def desenfileirar(self) -> Optional[Any]:
        if self.total == 0:
            return None  # Fila vazia
        item = self.buffer[self.inicio]
        self.buffer[self.inicio] = None
        self.inicio = (self.inicio + 1) % self.capacidade
        self.total -= 1
        return item


# =====================================================================
# 4. Demonstração das Estruturas Lineares
# =====================================================================

if __name__ == "__main__":
    print("=" * 65)
    print("DEMONSTRAÇÃO: ESTRUTURAS DE DADOS LINEARES")
    print("=" * 65)

    # 1. Lista Encadeada
    print("\n[1] Operações com Lista Simplesmente Encadeada:")
    lista = ListaEncadeada()
    for num in [10, 20, 30, 40]:
        lista.inserir_fim(num)
    print(f"Lista original: {' -> '.join(map(str, lista.para_lista()))}")
    lista.reverter()
    print(f"Lista invertida (in-place): {' -> '.join(map(str, lista.para_lista()))}")

    # 2. Pilha e Expressões
    print("\n[2] Validação de Balanceamento com Pilha:")
    expressoes = [
        "{ [ ( 2 + 3 ) * 5 ] - 1 }",
        "{ [ ( 2 + 3 ] ) }",
        "( ( ( ) )",
        "def main(): return [x for x in (1, 2, 3)]"
    ]
    for expr in expressoes:
        valida = validar_parenteses(expr)
        print(f"Expressão: '{expr}' -> Válida? {valida}")

    # 3. Fila Circular
    print("\n[3] Fila Circular com Buffer Fixo (Capacidade 3):")
    fila = FilaCircular(3)
    fila.enfileirar("Processo_A")
    fila.enfileirar("Processo_B")
    fila.enfileirar("Processo_C")
    print("Tentando enfileirar 4º item em buffer de 3:", fila.enfileirar("Processo_D"))  # False
    print("Item desenfileirado:", fila.desenfileirar())  # Processo_A
    fila.enfileirar("Processo_D")
    print("Novo item desenfileirado:", fila.desenfileirar())  # Processo_B