1. Introdução
Durante nossa aula de hoje, demos início ao estudo das Estruturas de Dados Lineares, um dos pilares fundamentais da ciência da computação.
Uma estrutura de dados é uma maneira particular de organizar e armazenar dados em um computador para que possam ser acessados e modificados de forma eficiente. Estruturas lineares são aquelas onde os elementos estão dispostos em uma sequência, um após o outro. As duas estruturas mais fundamentais desse tipo são as Pilhas (Stacks) e as Filas (Queues), que veremos em detalhes a seguir com exemplos práticos em Python.
2. Pilhas (Stacks)
Uma pilha é uma estrutura de dados que segue a política LIFO (Last In, First Out) — o último elemento a entrar é o primeiro a sair. Imagine uma pilha de pratos: o último prato colocado no topo é o primeiro a ser removido.
As operações fundamentais de uma pilha são:
- push: Adicionar um elemento ao topo da pilha.
- pop: Remover o elemento do topo da pilha.
- peek (ou top): Consultar o elemento do topo sem removê-lo.
- is_empty: Verificar se a pilha está vazia.
Em Python, podemos implementar uma pilha de forma muito simples utilizando uma lista:
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 peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
# Exemplo de uso
minha_pilha = Stack()
minha_pilha.push(10)
minha_pilha.push(20)
minha_pilha.push(30)
print(minha_pilha.peek()) # 30
print(minha_pilha.pop()) # 30
print(minha_pilha.pop()) # 203. Filas (Queues)
Uma fila segue a política FIFO (First In, First Out) — o primeiro elemento a entrar é o primeiro a sair. É exatamente como uma fila de banco ou de supermercado: quem chega primeiro é atendido primeiro.
As operações fundamentais de uma fila são:
- enqueue: Adicionar um elemento ao final da fila.
- dequeue: Remover o elemento do início da fila.
- front: Consultar o elemento do início sem removê-lo.
- is_empty: Verificar se a fila está vazia.
Para uma implementação eficiente de fila em Python, o módulo collections.deque é o mais adequado, pois permite remoção rápida em ambas as pontas:
from collections import deque
class Queue:
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()
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
# Exemplo de uso
minha_fila = Queue()
minha_fila.enqueue("A")
minha_fila.enqueue("B")
minha_fila.enqueue("C")
print(minha_fila.front()) # A
print(minha_fila.dequeue()) # A
print(minha_fila.dequeue()) # B4. Aplicações Práticas
Tanto pilhas quanto filas são amplamente utilizadas em sistemas computacionais e algoritmos do dia a dia:
Aplicações de Pilhas:
- Histórico de navegação: O botão "Voltar" do navegador utiliza uma pilha para armazenar as páginas visitadas. Ao clicar em "Voltar", a página atual é desempilhada e a anterior é exibida.
- Função Undo (Ctrl+Z): Editores de texto e softwares gráficos armazenam as ações do usuário em uma pilha para permitir a reversão.
- Call Stack: A pilha de execução de programas (call stack) gerencia as funções chamadas durante a execução de um programa.
Aplicações de Filas:
- Buffers de dados: Filas são usadas para gerenciar o buffer de streaming de vídeo ou áudio, garantindo que os dados sejam processados na ordem correta.
- Agendamento de tarefas (Round Robin): Sistemas operacionais usam filas para gerenciar processos que aguardam o uso da CPU, garantindo que todos recebam tempo de processamento de forma justa.
- Filas de mensagens: Sistemas distribuídos utilizam filas (RabbitMQ, Apache Kafka) para comunicação assíncrona entre serviços.
5. Complexidade de Tempo
Uma das grandes vantagens de pilhas e filas (quando implementadas corretamente) é a eficiência de suas operações principais:
| Operação | Pilha (List/Deque) | Fila (Deque) |
|---|---|---|
| Inserção (push/enqueue) | O(1)* | O(1) |
| Remoção (pop/dequeue) | O(1)* | O(1) |
| Consulta (peek/front) | O(1) | O(1) |
* O(1) amortizado para listas Python.
6. Perguntas Frequentes (FAQ)
Qual a diferença fundamental entre pilha e fila?
A diferença é a política de acesso aos elementos. A pilha usa LIFO (Last In, First Out), enquanto a fila usa FIFO (First In, First Out).
O Python já possui implementação interna para pilhas e filas?
Sim. Uma lista Python pode funcionar como uma pilha com os métodos append() e pop(). Para filas, collections.deque é a escolha ideal por oferecer operações O(1) em ambas as pontas com append() e popleft().
Onde encontramos pilhas e filas no dia a dia da programação?
Pilhas estão presentes no sistema de Undo de editores, no histórico de navegação e na call stack de linguagens de programação. Filas são usadas em sistemas de fila de impressão, buffers de streaming, agendamento de processos (Round Robin) e filas de mensagens em arquiteturas de microsserviços.
Qual estrutura de dados devo usar para implementar um cache LRU?
Para um cache LRU (Least Recently Used), uma pilha ou fila simples não são suficientes. O ideal é uma combinação de um Mapa (Hash Table) com uma Lista Duplamente Encadeada, ou utilizar a estrutura collections.OrderedDict do Python, que faz exatamente isso internamente.
7. Conclusão
Nesta aula, vimos os conceitos fundamentais de pilhas e filas, duas das estruturas de dados mais importantes e versáteis da computação. Compreender seus princípios de funcionamento (LIFO e FIFO) e saber implementá-las corretamente em Python é essencial para qualquer pessoa que deseja se aprofundar em algoritmos e desenvolvimento de software. Nas próximas aulas, exploraremos variações como Deques, Filas de Prioridade e como estes conceitos se aplicam a problemas mais complexos.