Ciências da computação dia 195

Hoje vamos estudar duas estruturas de dados fundamentais: pilhas e filas. Essas estruturas são usadas em diversas aplicações, desde a execução de funções em programação até o gerenciamento de tarefas em sistemas operacionais. Vamos entender o funcionamento, as operações básicas e as implementações mais comuns.

O que é uma Pilha?

Uma pilha (stack) é uma estrutura de dados que segue o princípio LIFO (Last In, First Out). Isso significa que o último elemento adicionado é o primeiro a ser removido. Imagine uma pilha de pratos: você coloca pratos um sobre o outro e só pode retirar o prato do topo.

Operações principais de uma pilha:

• push – adiciona um elemento ao topo.
• pop – remove o elemento do topo.
• top (ou peek) – consulta o elemento do topo sem removê-lo.
• isEmpty – verifica se a pilha está vazia.

Implementação de Pilha com Array (Python)

class Stack:
    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()
        return None

    def top(self):
        if not self.is_empty():
            return self.items[-1]
        return None

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

Essa implementação tem complexidade O(1) amortizado para push e pop (o redimensionamento do array pode tornar push O(n) ocasionalmente).

Implementação de Pilha com Lista Encadeada

Podemos também implementar a pilha usando uma lista encadeada (linked list), onde a cabeça da lista representa o topo. Todas as operações permanecem O(1).

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class StackLinkedList:
    def __init__(self):
        self.head = None

    def push(self, item):
        self.head = Node(item, self.head)

    def pop(self):
        if self.head is None:
            return None
        value = self.head.value
        self.head = self.head.next
        return value

    def top(self):
        if self.head is None:
            return None
        return self.head.value

    def is_empty(self):
        return self.head is None

O que é uma Fila?

Uma fila (queue) segue o princípio FIFO (First In, First Out). O primeiro elemento adicionado é o primeiro a ser removido. Funciona como uma fila de pessoas em um banco ou supermercado.

Operações principais de uma fila:

• enqueue – adiciona um elemento ao final (tail).
• dequeue – remove o elemento do início (head).
• front – consulta o primeiro elemento.
• isEmpty – verifica se a fila está vazia.

Implementação de Fila com Lista (Python)

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

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

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

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

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

Note que usar pop(0) em listas dinâmicas tem complexidade O(n) (porque todos os elementos são deslocados). Para uma fila eficiente, usamos uma lista encadeada ou uma fila circular com array.

Implementação de Fila com Lista Encadeada

Com uma lista encadeada simples, podemos obter O(1) para enqueue e dequeue se mantivermos ponteiros para head e tail.

class QueueLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, item):
        node = Node(item)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        if self.head is None:
            return None
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return value

    def front(self):
        if self.head is None:
            return None
        return self.head.value

    def is_empty(self):
        return self.head is None

Comparação entre Pilha e Fila

Aplicações Práticas

Pilhas

• Desfazer/Refazer (undo/redo) em editores de texto.
• Navegação no browser – o botão "voltar" empilha as páginas visitadas.
• Chamada de funções – a pilha de execução (call stack) gerencia chamadas recursivas.
• Avaliação de expressões – conversão de infixa para pós-fixa (notação polonesa inversa).

Filas

• Fila de impressão – documentos são processados na ordem de chegada.
• Escalonamento de processos – sistemas operacionais usam filas para gerenciar processos prontos.
• Buffer de dados – streaming de áudio/vídeo usa filas para armazenar pacotes.
• Busca em largura (BFS) – em grafos, a BFS utiliza uma fila para explorar vértices.

Fila Circular

Uma fila implementada com array de tamanho fixo pode reutilizar espaços usando a técnica de fila circular. Em vez de mover elementos, mantemos índices de início e fim. Quando o índice atinge o final do array, ele "dá a volta" usando aritmética modular. Isso evita desperdício de memória e mantém as operações em O(1).

Resumo dos Pontos Principais

• Pilha: LIFO, acesso apenas ao topo; operações push, pop e top O(1).
• Fila: FIFO, acesso ao início e ao final; operações enqueue, dequeue e front O(1).
• Ambas são estruturas lineares fundamentais em ciência da computação.
• Implementações eficientes usam listas encadeadas ou arrays circulares.
• A escolha entre pilha e fila depende da ordem de processamento desejada.

Perguntas Frequentes (FAQ)

Qual a diferença entre pilha e fila?

Pilha segue LIFO (o último a entrar é o primeiro a sair). Fila segue FIFO (o primeiro a entrar é o primeiro a sair).

Quando usar pilha em vez de fila?

Use pilha quando você precisar acessar o elemento mais recente (como em undo/redo, backtracking, recursão). Use fila quando a ordem de chegada deve ser preservada (como em buffers, filas de impressão, escalonamento).

O que é uma fila circular?

É uma implementação de fila com array fixo que reutiliza posições através de aritmética modular. Quando o índice de final chega ao limite, ele retorna ao início, desde que haja espaço. Isso evita cópias e mantém eficiência O(1).

Como implementar uma fila usando duas pilhas?

Para enfileirar, empilhamos na pilha1. Para desenfileirar, transferimos todos os elementos da pilha1 para a pilha2 (invertendo a ordem) e depois removemos o topo da pilha2. Essa implementação tem custo amortizado O(1) por operação.