Ciências da computação dia 165

Na aula de hoje, número 165 da série, exploramos duas estruturas de dados lineares fundamentais: pilhas e filas. Essas estruturas são a base para muitos algoritmos e sistemas, desde o gerenciamento de chamadas de funções até o escalonamento de processos. Vamos detalhar seus conceitos, operações e aplicações.

Pilhas (Stacks)

Uma pilha (stack) é uma estrutura que segue o princípio LIFO (Last In, First Out). O último elemento inserido é o primeiro a ser removido. Imagine uma pilha de livros: para pegar o livro do meio, é necessário retirar os de cima primeiro.

Operações Básicas

Push: insere um elemento no topo da pilha.
Pop: remove o elemento do topo.
Top (ou Peek): consulta o elemento do topo sem removê-lo.
isEmpty: verifica se a pilha está vazia.

Aplicações

Mecanismo "desfazer" (undo) em editores de texto.
Navegação entre páginas web (botão voltar).
Avaliação de expressões matemáticas (notação polonesa reversa).
Pilha de chamadas de funções (call stack) em linguagens de programação.

Um exemplo clássico do uso de pilhas é a verificação de parênteses balanceados em expressões matemáticas e código fonte. Ao percorrer a expressão, cada parêntese aberto é empilhado; ao encontrar um parêntese fechado, o topo da pilha é desempilhado e comparado. Se houver correspondência, continua; caso contrário, a expressão está mal formada. Ao final, se a pilha estiver vazia, a expressão é válida.

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.esta_vazia():
            return self.itens.pop()
    def top(self):
        if not self.esta_vazia():
            return self.itens[-1]
    def esta_vazia(self):
        return len(self.itens) == 0

Filas (Queues)

Uma fila (queue) segue o princípio FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser removido. É análogo a uma fila de banco: quem chega primeiro é atendido primeiro.

Operações Básicas

Enqueue: insere um elemento no final da fila.
Dequeue: remove o elemento do início da fila.
Front: consulta o elemento do início sem removê-lo.
isEmpty: verifica se a fila está vazia.

Aplicações

Filas de impressão.
Gerenciamento de processos em sistemas operacionais (escalonamento).
Algoritmo de busca em largura (BFS) em grafos.
Buffers em comunicação de dados.

Uma implementação mais eficiente de fila utiliza o conceito de fila circular, onde o início e o fim são índices que se movem dentro de um array fixo, reaproveitando posições. A fila circular evita o deslocamento de elementos e garante operações O(1) no pior caso. Em Python, a classe collections.deque implementa uma deque (fila de duas pontas) que pode ser usada como fila ou pilha com desempenho O(1) para inserções e remoções em ambas as extremidades.

Implementação Simples em Python

class Fila:
    def __init__(self):
        self.itens = []
    def enqueue(self, item):
        self.itens.append(item)
    def dequeue(self):
        if not self.esta_vazia():
            return self.itens.pop(0)
    def front(self):
        if not self.esta_vazia():
            return self.itens[0]
    def esta_vazia(self):
        return len(self.itens) == 0

Nota: usar pop(0) em listas Python é ineficiente (O(n)); para uso real prefira collections.deque.

Comparação entre Pilhas e Filas

Característica	Pilha	Fila
Princípio	LIFO	FIFO
Inserção	No topo (push)	No final (enqueue)
Remoção	Do topo (pop)	Do início (dequeue)
Complexidade típica	O(1) (push/pop)	O(1) (enqueue/dequeue)
Aplicações comuns	Undo, call stack, parser	Escalonamento, BFS, buffers

Deques (Double-Ended Queues)

Um deque é uma generalização de pilha e fila que permite inserção e remoção tanto no início quanto no final, com complexidade O(1) para ambas as operações (em implementações adequadas). Em Python, collections.deque é a implementação recomendada para uso como fila ou pilha quando o desempenho é crítico. Deques são úteis em algoritmos que exigem acesso rápido a ambas as extremidades, como na implementação de janelas deslizantes (sliding window) ou em algoritmos de cache.

Perguntas Frequentes (FAQ)

1. Qual a principal diferença entre pilha e fila?
Pilha utiliza LIFO (último a entrar, primeiro a sair), enquanto fila utiliza FIFO (primeiro a entrar, primeiro a sair). Na pilha, a inserção e remoção ocorrem na mesma extremidade (topo); na fila, a inserção ocorre no final e a remoção no início.

2. É possível implementar uma fila usando pilhas?
Sim, usando duas pilhas: uma para enfileirar (enqueue) e outra para desenfileirar (dequeue). Quando a pilha de dequeue estiver vazia, transferimos todos os elementos da pilha de enqueue para ela, invertendo a ordem. Essa implementação tem complexidade amortizada O(1) por operação.

3. O que é uma fila circular e por que é útil?
Uma fila circular reaproveita os espaços liberados ao remover elementos do início, evitando desperdício de memória. Em vez de deslocar todos os elementos, mantém índices de início e fim que avançam circularmente.

4. Qual a importância de pilhas em compiladores?
Pilhas são usadas para analisar a sintaxe da linguagem (parsing), avaliar expressões (notação polonesa reversa) e gerenciar escopos de variáveis durante a compilação.

5. O que causa um stack overflow?
Stack overflow ocorre quando a pilha de chamadas de funções ultrapassa o limite de memória alocada para ela. Isso pode acontecer devido a recursão infinita, recursão muito profunda sem otimização, ou alocação excessiva de variáveis locais grandes na pilha. Quando ocorre, o programa geralmente é encerrado com um erro de segmentação ou estouro de pilha.

6. Qual a relação entre pilhas e recursão?
A recursão depende intrinsecamente da pilha de chamadas (call stack). Cada chamada recursiva empilha um novo quadro (stack frame) contendo variáveis locais e o ponto de retorno. Quando a condição de base é atingida, as chamadas começam a retornar e os quadros são desempilhados. Por isso, recursões muito profundas podem causar stack overflow. Linguagens como Scheme otimizam a recursão em cauda (tail call optimization) para reaproveitar o quadro atual e não aumentar a pilha.

Conclusão

Pilhas e filas são estruturas de dados linear essenciais na computação. Dominar seus conceitos, operações e implementações permite resolver problemas clássicos de forma eficiente e compreender sistemas mais complexos, como escalonadores, navegadores e interpretadores de linguagens. Continuaremos explorando variações como deques e filas de prioridade nas próximas aulas.