Durante nossa aula de hoje, exploramos duas das estruturas de dados mais fundamentais e onipresentes na ciência da computação: Pilhas (Stacks) e Filas (Queues). Elas são os blocos de construção para desde algoritmos de roteamento em redes até o gerenciamento de processos no seu sistema operacional. Vamos entender seus mecanismos, implementações e onde cada uma se destaca.

Pilhas (Stacks) — O Princípio LIFO

Imagine uma pilha de pratos. O último prato que você coloca no topo é o primeiro que você retira. Esse é exatamente o princípio por trás de uma Stack: LIFO (Last In, First Out). Os elementos são inseridos e removidos sempre pelo mesmo lado, chamado de topo da pilha.

As operações básicas são:

  • push(elemento): Insere um elemento no topo.
  • pop(): Remove e retorna o elemento do topo.
  • top() ou peek(): Retorna o elemento do topo sem removê-lo.
  • isEmpty(): Verifica se a pilha está vazia.

Implementação em Python

Em Python, podemos implementar uma pilha de forma simples utilizando uma lista, já que as listas dinâmicas suportam append (nosso push) e pop de forma eficiente (O(1) amortizado para o final da lista).

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")

    def top(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("top from empty stack")

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

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

    def __str__(self):
        return str(self.items)

Todas as operações principais têm complexidade O(1). Simples e eficiente.

Filas (Queues) — O Princípio FIFO

Agora, pense em uma fila de banco. A primeira pessoa a chegar é a primeira a ser atendida. Esse é o princípio FIFO (First In, First Out). Em uma Fila, inserimos no final (chamado de rear ou tail) e removemos do início (chamado de front ou head).

As operações básicas:

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

Implementação em Python

Usar uma lista simples para fila não é eficiente, pois remover o primeiro elemento (pop(0)) custa O(n) — todos os outros elementos precisam ser deslocados. A melhor prática é usar collections.deque, que oferece uma implementação otimizada para inserções e remoções em ambas as extremidades com complexidade O(1).

from collections import deque

class Fila:
    def __init__(self):
        self.items = deque()

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        raise IndexError("dequeue from empty queue")

    def front(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("front from empty queue")

    def rear(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("rear from empty queue")

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

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

    def __str__(self):
        return str(list(self.items))

Tanto append (enqueue) quanto popleft (dequeue) são operações O(1).

Análise e Comparação

A escolha entre Pilha e Fila depende estritamente da regra de negócio do seu algoritmo. Se a sua lógica exige que o último a chegar seja o primeiro a sair (ex: sistema de Undo), use uma Pilha. Se o primeiro a chegar deve ser o primeiro a sair (ex: fila de impressão), use uma Fila.

Ambas podem ser implementadas com arrays (dinâmicos) ou listas encadeadas. A implementação com array (ou deque, que é um array circular) tende a ser mais amigável ao cache do processador, enquanto a lista encadeada tem inserções e remoções mais previsíveis e sem realocações de memória, mas com maior overhead de memória por nó devido aos ponteiros.

Aplicações Práticas no Mundo Real

  • Pilhas:
    • Sistema de Undo (Ctrl+Z) em editores de texto.
    • Navegação Forward/Back no seu navegador.
    • Call Stack de linguagens de programação (gerenciamento de funções).
    • Algoritmo de avaliação de expressões (pós-fixa/infixa — Shunting-yard).
  • Filas:
    • Spooler de impressão.
    • Fila de processos em sistemas operacionais (escalonamento Round Robin).
    • Algoritmos de Busca em Largura (BFS) em grafos.
    • Filas de mensagens (RabbitMQ, Kafka) para comunicação entre microsserviços.

Exercícios de Fixação

Para fixar o conteúdo de hoje, tente implementar:

  1. Inversão de String: Crie uma função que recebe uma string e retorna sua versão invertida usando uma pilha.
  2. Fila com Duas Pilhas: Implemente uma fila onde as operações enqueue e dequeue são feitas utilizando exclusivamente duas pilhas internas. (Esse é um clássico em entrevistas técnicas!).
  3. Validação de Parênteses: Escreva um algoritmo que verifica se uma string contendo (), [], {} está com os parênteses, colchetes e chaves balanceados.

Perguntas Frequentes (FAQ)

  • O que significa LIFO e FIFO?
    LIFO é a sigla para "Last In, First Out" (Último a Entrar, Primeiro a Sair), característico das Pilhas. FIFO é "First In, First Out" (Primeiro a Entrar, Primeiro a Sair), característico das Filas.
  • Qual estrutura de dados é melhor para fazer um sistema de Undo?
    A Pilha. Cada ação do usuário é "empilhada" (push). Ao pressionar Ctrl+Z, a última ação é "desempilhada" (pop) para ser desfeita.
  • O que é um "Stack Overflow"?
    É um erro que ocorre quando a pilha de chamadas (Call Stack) de um programa excede seu limite máximo de memória alocada. Geralmente causado por recursão infinita ou loops excessivamente profundos.
  • Fila com array comum é uma boa ideia?
    Depende. Se você precisa remover do início frequentemente, uma lista comum em Python tem desempenho ruim no pop(0) (O(n)). É melhor usar collections.deque para uma implementação eficiente O(1) em ambas as operações.

Conclusão

Pilhas e Filas são estruturas de dados aparentemente simples, mas extremamente poderosas. Dominá-las é um rito de passagem para qualquer estudante de ciência da computação. Elas formam a base para entender estruturas mais complexas como Árvores, Grafos e Tabelas Hash. Na próxima aula, vamos avançar para listas ligadas e ver como elas se comparam.