Ciências da computação dia 151

Nesta aula de Ciências da Computação, mergulhamos em duas estruturas de dados lineares fundamentais: pilhas (stacks) e filas (queues). Tanto pilhas quanto filas são utilizadas em uma infinidade de algoritmos e sistemas, e entendê-las é essencial para construir software eficiente. A principal diferença entre elas está na ordem de remoção dos elementos: enquanto a pilha segue o princípio LIFO (Last In, First Out), a fila segue o FIFO (First In, First Out). Vamos explorar cada uma em detalhes, incluindo suas operações, implementações e aplicações práticas.

1. Pilhas (Stack)

Uma pilha é uma estrutura que permite inserir e remover elementos apenas pelo topo. O último elemento inserido é o primeiro a ser removido (LIFO). As operações básicas são:

• push(item): adiciona um item ao topo.
• pop(): remove e retorna o item do topo.
• peek(): retorna o item do topo sem remover.
• isEmpty(): verifica se a pilha está vazia.

Essas operações têm complexidade O(1) quando implementadas com array ou lista encadeada com referência ao topo. A pilha pode ser implementada facilmente em Python:

class Pilha:
    def __init__(self):
        self.itens = []
    def push(self, item):
        self.itens.append(item)
    def pop(self):
        return self.itens.pop()
    def peek(self):
        return self.itens[-1]
    def vazia(self):
        return len(self.itens) == 0

As pilhas são amplamente usadas: reversão de strings, avaliação de expressões (notação polonesa inversa), mecanismo de desfazer (undo) em editores, e na pilha de chamadas de funções (call stack) das linguagens de programação.

Exemplo prático: verificação de parênteses balanceados

Um uso clássico de pilha é verificar se uma string com parênteses, colchetes e chaves está balanceada. Percorremos a string e, para cada caractere de abertura, inserimos na pilha; para cada fechamento, verificamos se o topo coincide. Se ao final a pilha estiver vazia, a expressão está correta.

2. Filas (Queue)

Uma fila segue a regra FIFO: o primeiro elemento inserido é o primeiro a ser removido. As operações principais são:

• enqueue(item): insere no final.
• dequeue(): remove do início.
• front(): consulta o início.
• isEmpty(): verifica se está vazia.

Implementação simples em Python (com lista, mas pop(0) é O(n)):

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

Para obter O(1) em ambas operações, utiliza-se uma fila circular com array ou collections.deque do Python.

Aplicações: filas de impressão, escalonamento de processos (round-robin), buffers de dados, busca em largura (BFS) em grafos, sistemas de mensageria.

3. Implementações e Comparação

Podemos implementar pilhas e filas usando arrays (estáticos ou dinâmicos) ou listas encadeadas. Cada abordagem tem vantagens:

A escolha depende do contexto. Em geral, arrays são mais rápidos e com menor uso de memória, mas listas encadeadas oferecem flexibilidade.

4. Filas vs Pilhas

5. Aplicações Reais

• Pilhas: Navegação em browsers (back/forward), undo/redo, compiladores (análise sintática), execução de funções recursivas.
• Filas: Sistemas de mensagens (RabbitMQ, Kafka), escalonamento de processos (Round Robin), fila de impressão, busca BFS, buffers de streaming.

Em sistemas operacionais, por exemplo, a fila de processos prontos é implementada como uma fila. A pilha de chamadas é crucial para o funcionamento de funções e recursão.

Perguntas Frequentes (FAQ)

Como verificar se uma string de parênteses está balanceada?

Use uma pilha: para cada caractere de abertura, empilhe; para fechamento, desempilhe e verifique correspondência. Se ao final a pilha estiver vazia, está balanceada.

Qual a diferença entre uma fila simples e uma fila circular?

Na fila simples com array, após várias inserções e remoções, o início se desloca, desperdiçando espaço no início. A fila circular reutiliza as posições, mantendo O(1) em ambas operações.

É possível implementar uma fila usando duas pilhas?

Sim, uma pilha para enqueue e outra para dequeue. Quando a pilha de dequeue estiver vazia, despeje a pilha de enqueue na de dequeue. Essa estrutura tem custo amortizado O(1).

O que é deque?

Deque (double-ended queue) é uma fila dupla, onde podemos inserir e remover tanto do início quanto do final. Combina características de pilha e fila.

Conclusão

Pilhas e filas são estruturas de dados elementares, mas extremamente versáteis. Dominá-las é o primeiro passo para entender estruturas mais complexas e para projetar soluções eficientes. Recomendo que você implemente essas estruturas em pelo menos uma linguagem e resolva problemas clássicos como reverse polish notation, simulação de fila de banco e BFS. Continue estudando com os outros posts da série Ciências da Computação ou explore temas específicos por tags no blog.