Na aula de hoje, vamos explorar duas estruturas de dados fundamentais na ciência da computação: pilhas e filas. Essas estruturas são amplamente utilizadas em algoritmos, sistemas operacionais e aplicações cotidianas. Vamos entender seus conceitos, operações básicas e implementações práticas.

O que são Estruturas de Dados?

Estruturas de dados são formas organizadas de armazenar e gerenciar dados em um computador, permitindo que operações como inserção, remoção e busca sejam realizadas de maneira eficiente. Cada estrutura possui características específicas que a tornam adequada para diferentes cenários. Pilhas e filas são exemplos clássicos de estruturas lineares, onde os elementos são dispostos em sequência.

Pilhas (Stack)

Uma pilha segue o princípio LIFO (Last In, First Out) — o último elemento inserido é o primeiro a ser removido. Imagine uma pilha de pratos: você coloca pratos no topo e retira também do topo. As operações principais são:

  • push (empilhar): adiciona um elemento ao topo.
  • pop (desempilhar): remove o elemento do topo.
  • top (ou peek): consulta o elemento do topo sem removê-lo.

Pilhas são usadas em algoritmos de backtracking, avaliação de expressões, controle de chamadas de funções (call stack) e funcionalidades como "desfazer" (undo) em editores.

Exemplo: Validação de Parênteses

Um uso clássico de pilhas é verificar se uma expressão matemática possui parênteses balanceados. O algoritmo percorre a string e, ao encontrar um parêntese de abertura, empilha; ao encontrar um de fechamento, desempilha e verifica a correspondência. Se ao final a pilha estiver vazia, a expressão é válida.

def parenteses_balanceados(expr):
    pilha = []
    for char in expr:
        if char == '(':
            pilha.append(char)
        elif char == ')':
            if not pilha:
                return False
            pilha.pop()
    return len(pilha) == 0

print(parenteses_balanceados("(())"))  # True
print(parenteses_balanceados("(()"))   # False

Filas (Queue)

Uma fila segue o princípio FIFO (First In, First Out) — o primeiro elemento inserido é o primeiro a ser removido. É como uma fila de banco: quem chega primeiro é atendido primeiro. Operações básicas:

  • enqueue (enfileirar): adiciona um elemento ao final da fila.
  • dequeue (desenfileirar): remove o elemento da frente.
  • front (ou peek): consulta o elemento da frente.

Existem variações como fila circular e fila de prioridade. Filas são fundamentais em sistemas de gerenciamento de tarefas, buffers de dados e algoritmos de busca em largura (BFS).

Implementação em Python

Vamos ver implementações simples dessas estruturas usando Python.

Pilha com lista

class Pilha:
    def __init__(self):
        self._dados = []
    
    def push(self, item):
        self._dados.append(item)
    
    def pop(self):
        if not self.esta_vazia():
            return self._dados.pop()
        raise IndexError("pilha vazia")
    
    def topo(self):
        if not self.esta_vazia():
            return self._dados[-1]
        raise IndexError("pilha vazia")
    
    def esta_vazia(self):
        return len(self._dados) == 0

Fila com deque

A biblioteca collections fornece a estrutura deque otimizada para inserções e remoções nas extremidades.

from collections import deque

class Fila:
    def __init__(self):
        self._dados = deque()
    
    def enqueue(self, item):
        self._dados.append(item)
    
    def dequeue(self):
        if not self.esta_vazia():
            return self._dados.popleft()
        raise IndexError("fila vazia")
    
    def frente(self):
        if not self.esta_vazia():
            return self._dados[0]
        raise IndexError("fila vazia")
    
    def esta_vazia(self):
        return len(self._dados) == 0

Análise de Complexidade

As operações de inserção (push/enqueue) e remoção (pop/dequeue) em pilhas e filas implementadas com listas ou deques têm complexidade O(1) em média. A busca de um elemento específico, porém, requer percorrer toda a estrutura no pior caso, resultando em O(n). Essa eficiência torna pilhas e filas ideais para cenários onde a ordem de processamento é FIFO ou LIFO.

Aplicações Práticas

  • Pilhas: undo/redo em editores, avaliação de expressões (notação polonesa reversa), percurso em profundidade (DFS) em grafos, alocação de chamadas de funções.
  • Filas: escalonamento de processos em sistemas operacionais, filas de impressão, busca em largura (BFS), sistemas de mensageria e buffers de streaming.

Dominar essas estruturas é essencial para qualquer profissional de computação, pois elas servem como base para algoritmos mais complexos e sistemas eficientes.

Perguntas Frequentes

Qual a diferença entre pilha e fila?
Pilha segue LIFO (último a entrar, primeiro a sair), enquanto fila segue FIFO (primeiro a entrar, primeiro a sair).
O que acontece se tentar remover de uma pilha vazia?
Ocorre um erro de underflow. Na implementação, devemos verificar se a estrutura está vazia antes de remover.
Qual a complexidade das operações em uma fila implementada com deque?
Inserção e remoção nas extremidades têm complexidade O(1).

Considerações Finais

Hoje aprendemos os fundamentos de pilhas e filas, suas operações e implementações em Python. Pratique a implementação e tente resolver problemas como validação de parênteses balanceados (pilha) e atendimento de pedidos (fila). Nas próximas aulas, avançaremos para estruturas mais complexas como árvores e tabelas hash.