Durante nossas aulas de ciências da computação, chegamos a um ponto essencial do curso: o estudo das estruturas de dados. Esses conceitos são fundamentais para qualquer pessoa que deseja escrever programas eficientes e bem estruturados. Hoje vamos explorar três estruturas lineares clássicas: pilhas, filas e listas encadeadas. Cada uma delas tem características próprias que as tornam adequadas para diferentes tipos de problema.

O que são Estruturas de Dados?

Estruturas de dados são formas de organizar, gerenciar e armazenar dados em um computador para que possam ser acessados e modificados de maneira eficiente. Elas são a base sobre a qual algoritmos são construídos. Uma escolha adequada de estrutura de dados pode reduzir drasticamente o tempo de execução de um algoritmo e o consumo de memória.

As estruturas lineares, como as que veremos hoje, organizam os dados em sequência, onde cada elemento tem um antecessor e um sucessor (exceto o primeiro e o último).

Pilhas (Stacks)

A pilha é uma estrutura que segue o princípio LIFO (Last In, First Out). Isso significa que o último elemento inserido é o primeiro a ser removido. Para visualizar, pense em uma pilha de livros: você coloca um livro em cima do outro e, quando precisa de um livro, começa retirando do topo.

As operações fundamentais de uma pilha são:

  • push(elemento): insere um novo elemento no topo.
  • pop(): remove e retorna o elemento do topo.
  • peek() ou top(): retorna o elemento do topo sem removê-lo.
  • isEmpty(): verifica se a pilha está vazia.

Vamos ver uma implementação simples em Python:

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

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

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

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

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

    def __len__(self):
        return len(self._itens)

Pilhas são extremamente úteis em diversas aplicações. Um exemplo clássico é o histórico de navegação em browsers. Quando você visita uma página, o endereço é empilhado. Quando você clica em "voltar", a página anterior é desempilhada. Outro exemplo é a funcionalidade de desfazer (undo) em editores de texto: cada ação é armazenada em uma pilha e, ao desfazer, a última ação é desfeita primeiro.

Filas (Queues)

A fila segue o princípio FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser removido. É o mesmo conceito de uma fila de banco ou supermercado: quem chega primeiro é atendido primeiro.

Operações principais:

  • enqueue(elemento): insere um elemento no final da fila.
  • dequeue(): remove e retorna o elemento do início da fila.
  • front(): retorna o elemento do início sem removê-lo.
  • isEmpty(): verifica se a fila está vazia.

Implementação em Python:

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

    def enqueue(self, item):
        self._itens.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self._itens.pop(0)
        return None

    def front(self):
        if not self.is_empty():
            return self._itens[0]
        return None

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

    def __len__(self):
        return len(self._itens)

Note que a implementação acima usa pop(0), que tem complexidade O(n) em Python porque os elementos precisam ser deslocados. Uma implementação mais eficiente usaria uma lista encadeada ou a classe collections.deque.

Filas são amplamente utilizadas em sistemas operacionais para gerenciamento de processos, em sistemas de impressão onde trabalhos são processados na ordem de chegada, e em algoritmos de busca em largura (BFS) para grafos.

Listas Encadeadas (Linked Lists)

Uma lista encadeada é uma estrutura linear onde cada elemento, chamado de nó, contém dois campos: o valor armazenado e uma referência (ponteiro) para o próximo nó da sequência. Diferente dos arrays tradicionais, os elementos não ocupam posições contíguas na memória.

Existem variações importantes:

  1. Lista Simplesmente Encadeada: cada nó possui um ponteiro para o próximo. A navegação é unilateral (do início para o fim).
  2. Lista Duplamente Encadeada: cada nó possui ponteiros para o próximo e para o anterior, permitindo navegação nos dois sentidos.
  3. Lista Circular: o último nó aponta de volta para o primeiro, formando um ciclo.

Implementação simples em Python:

class No:
    def __init__(self, valor):
        self.valor = valor
        self.proximo = None

class ListaEncadeada:
    def __init__(self):
        self.cabeca = None
        self.tamanho = 0

    def inserir_no_inicio(self, valor):
        novo = No(valor)
        novo.proximo = self.cabeca
        self.cabeca = novo
        self.tamanho += 1

    def remover_do_inicio(self):
        if self.cabeca is None:
            return None
        valor = self.cabeca.valor
        self.cabeca = self.cabeca.proximo
        self.tamanho -= 1
        return valor

    def buscar(self, valor):
        atual = self.cabeca
        while atual:
            if atual.valor == valor:
                return True
            atual = atual.proximo
        return False

    def __len__(self):
        return self.tamanho

Vantagens das listas encadeadas:

  • Inserção e remoção em O(1) quando já temos referência ao nó.
  • Crescimento dinâmico sem realocação.
  • Não há desperdício de memória com slots não utilizados.

Desvantagens:

  • Acesso sequencial O(n) para encontrar um elemento.
  • Maior consumo de memória por elemento devido aos ponteiros.
  • Não suporta acesso aleatório como arrays.

Comparação entre as Estruturas

Estrutura Princípio Inserção Remoção Acesso
Pilha LIFO O(1) topo O(1) topo O(n)
Fila FIFO O(1) final O(1) início O(n)
Lista Encadeada Linear O(1) início O(1) início O(n)

Aplicações Práticas

Cada estrutura tem seu lugar ideal:

Pilhas são usadas em:

  • Avaliação de expressões matemáticas (notação polonesa reversa)
  • Parsing de linguagens de programação
  • Algoritmo de busca em profundidade (DFS)
  • Gerenciamento de chamadas de função (call stack)

Filas são usadas em:

  • Escalonamento de processos em sistemas operacionais
  • Filas de mensagens em sistemas distribuídos
  • Algoritmo de busca em largura (BFS)
  • Buffers de streaming de dados

Listas encadeadas são usadas em:

  • Implementação de sistemas de arquivos
  • Gerenciamento de memória dinâmica
  • Listas de reprodução em aplicações multimídia
  • Implementação de tabelas hash com encadeamento separado

FAQ

P: Qual a diferença fundamental entre pilha e fila?
R: A diferença está na ordem de remoção. Pilha utiliza LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a sair. Fila utiliza FIFO (First In, First Out), onde o primeiro elemento inserido é o primeiro a sair.

P: Quando devo usar uma lista encadeada em vez de um array?
R: Prefira lista encadeada quando você precisar fazer muitas inserções e remoções no início ou no meio da estrutura, quando o tamanho dos dados for desconhecido ou muito variável, e quando o acesso sequencial for suficiente para seu caso de uso.

P: O que significa complexidade O(1) e O(n)?
R: O(1) indica que a operação leva um tempo constante, independentemente do tamanho dos dados. O(n) indica que o tempo cresce linearmente com a quantidade de elementos. Por exemplo, acessar o topo de uma pilha é O(1), mas buscar um elemento específico em uma lista encadeada é O(n).

P: É possível implementar uma fila usando pilhas?
R: Sim, é possível utilizar duas pilhas para implementar uma fila. Uma pilha é usada para inserção (enqueue) e outra para remoção (dequeue). Quando a pilha de remoção está vazia, os elementos da pilha de inserção são transferidos para ela, invertendo a ordem e simulando o comportamento FIFO.