Introdução

Na aula de hoje, dia 224 do nosso curso de Ciências da Computação, demos continuidade ao estudo das estruturas de dados. O foco principal foram as estruturas lineares: pilhas (stack), filas (queue) e listas encadeadas (linked list). Essas estruturas são fundamentais para a organização e manipulação eficiente de dados em memória, servindo como base para diversos algoritmos clássicos e sistemas computacionais modernos.

Pilhas (Stack)

A pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out). O último elemento inserido é o primeiro a ser removido. As operações fundamentais são push (empilhar) e pop (desempilhar). Exploramos exemplos práticos onde esse comportamento é essencial, como no algoritmo de backtracking para resolução de labirintos e no sistema de "desfazer" (undo) de editores de texto.

Discutimos como uma pilha pode ser implementada tanto com arrays (alocação estática) quanto com listas encadeadas (alocação dinâmica), e as vantagens de cada abordagem em termos de desempenho e flexibilidade.

Filas (Queue)

Diferente da pilha, a fila segue o princípio FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser retirado, análogo a uma fila de banco ou de supermercado. As operações principais são enqueue (inserir no fim) e dequeue (remover do início).

Estudamos aplicações reais, como o escalonamento de processos em sistemas operacionais (ready queue) e o buffer de dados em transmissões de rede. Implementamos uma fila circular para otimizar o uso do espaço de memória, evitando o desperdício comum em implementações lineares simples.

Listas Encadeadas (Linked List)

Listas encadeadas são estruturas de dados dinâmicas e lineares. Cada elemento, chamado de nó, contém o valor armazenado e um ponteiro (ou referência) para o próximo nó da sequência. Diferentemente de arrays, elas não exigem um bloco contínuo de memória, o que confere grande flexibilidade para inserções e remoções em qualquer posição (início, meio ou fim), desde que se tenha uma referência para o local desejado.

Analisamos três variações principais:

  • Lista Simplesmente Encadeada: cada nó aponta apenas para o próximo, formando uma sequência linear.
  • Lista Duplamente Encadeada: cada nó aponta para o próximo e para o anterior, permitindo navegação bidirecional.
  • Lista Circular: o último nó aponta de volta para o primeiro, formando um ciclo.

Complexidade das Operações

Comparando as operações básicas e sua complexidade de tempo (Big O):

  • Pilha / Fila (baseada em array): Acesso O(1), Inserção O(1) (amortizado), Remoção O(1), Busca O(n).
  • Lista Encadeada: Inserção no início O(1), Remoção no início O(1), Acesso/Busca O(n), Inserção no fim com tail pointer O(1).

A escolha da estrutura correta depende do tipo de operação que será mais frequente no sistema.

Exemplo de Código

Implementamos uma pilha simples em Python para consolidar os conceitos:

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def size(self):
        return len(self.items)

Também implementamos a base de uma lista encadeada simples com inserção no início:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

Problemas Clássicos

Discutimos como aplicar essas estruturas para resolver problemas clássicos da computação:

  1. Torres de Hanói: resolvido recursivamente utilizando pilhas para rastrear os discos em cada haste.
  2. Josephus Problem: uma solução eficiente utilizando uma lista encadeada circular para simular a eliminação de soldados.
  3. Avaliação de Expressões: o uso de duas pilhas (operandos e operadores) para avaliar expressões aritméticas no formato pós-fixo (Reverse Polish Notation).

Aplicações em Sistemas Reais

Além dos exemplos clássicos, vimos como essas estruturas aparecem no dia a dia da computação:

  • Call Stack: a pilha de chamadas de funções é essencial para o funcionamento de qualquer linguagem de programação.
  • Spooler de Impressão: gerencia os trabalhos de impressão em uma fila, garantindo que sejam processados na ordem correta.
  • Sistemas de Arquivos: algumas implementações utilizam listas encadeadas para gerenciar blocos de dados em disco (File Allocation Table).

Considerações Finais

As aulas de hoje reforçaram que a escolha da estrutura de dados correta é essencial para a eficiência e clareza de um algoritmo. Pilhas, filas e listas encadeadas são a base para tópicos mais avançados, como árvores, grafos e tabelas hash. O exercício de implementação manual dessas estruturas em Python ajudou a consolidar o entendimento sobre alocação dinâmica, gerenciamento de memória e a importância dos ponteiros — conceitos que serão fundamentais nas próximas disciplinas do curso.