As estruturas de dados são essenciais na programação, auxiliando na organização eficiente das informações. A fila, em particular, destaca-se como uma das estruturas mais simples e fundamentais.
Neste artigo, vamos explorar o conceito de fila e como implementá-la utilizando a linguagem Python.
O que Define uma Fila?
Uma fila é uma estrutura de dados linear que opera sob o princípio FIFO (First In, First Out), ou seja, “o primeiro a entrar é o primeiro a sair”. Ela se contrapõe à estrutura de dados pilha.
Para ilustrar, imagine uma fila de pessoas esperando para comprar ingressos no cinema. A ordem em que as pessoas chegam é a ordem em que elas são atendidas.
Nessa analogia, a primeira pessoa da fila será atendida primeiro, seguida pela segunda e assim por diante, respeitando o princípio FIFO. Este mesmo princípio é aplicado na estrutura de dados fila, comum em diversas situações cotidianas.
Agora que você entende o conceito e o princípio de funcionamento, vamos explorar as operações que podemos realizar em uma fila.
Operações Fundamentais em Filas
Semelhante a uma pilha, as filas possuem duas operações principais:
enfileirar(dados)
Adiciona um novo elemento ao final da fila. Este lado da fila é denominado “traseira”.
desenfileirar()
Remove o elemento localizado no início da fila, conhecido como “frente”.
A visualização dessas operações pode facilitar a compreensão. Uma imagem pode valer mais que mil palavras, então observe a ilustração abaixo.
Além das operações essenciais, podemos implementar funções auxiliares para obter informações adicionais sobre a fila. Embora o número dessas funções possa variar, vamos nos concentrar nas mais importantes:
traseira()
Retorna o último elemento da fila.
frente()
Retorna o primeiro elemento da fila.
está_vazia()
Verifica se a fila está vazia, retornando verdadeiro ou falso.
A parte teórica pode parecer um pouco maçante, mas é essencial para a compreensão antes da implementação. Vamos, então, sujar as mãos com um pouco de código.
Assumindo que você já tem o Python instalado, vamos começar a implementar a fila.
Implementando a Fila em Python
A implementação da fila é relativamente simples. Em poucos minutos, você poderá criar a sua própria implementação. Existem várias formas de implementar uma fila em Python; vamos explorar algumas delas passo a passo.
#1. Utilizando Listas
As listas são estruturas de dados nativas do Python. Vamos usá-las para criar uma fila dentro de uma classe. O objetivo é construir a estrutura de dados desde o início, sem depender de nenhum módulo externo.
Passo 1: Criar uma classe chamada “Fila”.
class Fila:
pass
Passo 2: Definir uma variável para armazenar os dados da fila. Essa variável será uma lista, que chamaremos de “elementos”.
class Fila:
def __init__(self):
self.elementos = []
Passo 3: Implementar o método para adicionar dados à fila, chamado “enfileirar”. Este método recebe um dado e o adiciona à lista “elementos” usando o método “append”, que adiciona o elemento ao final da lista.
class Fila:
# ...
def enfileirar(self, dado):
self.elementos.append(dado)
return dado
Passo 4: Implementar o método para remover dados da fila, chamado “desenfileirar”. Este método utiliza o método “pop” da lista para remover o primeiro elemento, que corresponde ao elemento no índice 0.
class Fila:
# ...
def desenfileirar(self):
return self.elementos.pop(0)
Com isso, já temos uma fila funcional. No entanto, para verificar se tudo está funcionando corretamente, vamos implementar também as funções auxiliares.
Passo 5: Implementar o método “traseira”, que retorna o último elemento da fila. Utilizamos indexação negativa para acessar o último elemento da lista.
class Fila:
# ...
def traseira(self):
return self.elementos[-1]
Passo 6: Implementar o método “frente”, que retorna o primeiro elemento da fila, acessando-o através do índice 0 da lista.
class Fila:
# ...
def frente(self):
return self.elementos[0]
Passo 7: Implementar o método “esta_vazia”, que verifica se a fila está vazia, comparando o tamanho da lista com 0.
class Fila:
# ...
def esta_vazia(self):
return len(self.elementos) == 0
Terminamos a implementação da estrutura de dados fila. Agora, vamos criar um objeto da classe para utilizá-la.
class Fila:
# ...
if __name__ == '__main__':
fila = Fila()
Com o objeto “fila” criado, vamos testar o funcionamento da implementação:
- Verificar se a fila está vazia usando “esta_vazia()”. O resultado esperado é True.
- Adicionar os números 1, 2, 3, 4 e 5 à fila usando “enfileirar()”.
- Verificar novamente “esta_vazia()”. O resultado esperado é False.
- Imprimir o primeiro e o último elemento usando “frente()” e “traseira()”.
- Remover o primeiro elemento usando “desenfileirar()”.
- Verificar novamente o primeiro elemento usando “frente()”. O resultado esperado é o número 2.
- Remover todos os elementos da fila.
- Verificar novamente “esta_vazia()”. O resultado esperado é True.
Vamos verificar o código:
class Fila:
def __init__(self):
self.elementos = []
def enfileirar(self, dado):
self.elementos.append(dado)
return dado
def desenfileirar(self):
return self.elementos.pop(0)
def traseira(self):
return self.elementos[-1]
def frente(self):
return self.elementos[0]
def esta_vazia(self):
return len(self.elementos) == 0
if __name__ == '__main__':
fila = Fila()
## Verificando se a fila está vazia -> True
print(fila.esta_vazia())
## Adicionando elementos
fila.enfileirar(1)
fila.enfileirar(2)
fila.enfileirar(3)
fila.enfileirar(4)
fila.enfileirar(5)
## Verificando novamente se a fila está vazia -> False
print(fila.esta_vazia())
## Imprimindo o primeiro e último elemento -> 1, 5
print(fila.frente(), end=' ')
print(fila.traseira())
## Removendo o primeiro elemento -> 1
fila.desenfileirar()
## Imprimindo o primeiro e último elemento -> 2, 5
print(fila.frente(), end=' ')
print(fila.traseira())
## Removendo todos os elementos
fila.desenfileirar()
fila.desenfileirar()
fila.desenfileirar()
fila.desenfileirar()
## Verificando pela última vez se a fila está vazia -> True
print(fila.esta_vazia())
Ao executar o código, você deve obter um resultado similar a este:
True False 1 5 2 5 True
Podemos utilizar listas diretamente como uma estrutura de dados de fila. No entanto, a implementação acima ajuda a entender melhor o funcionamento da fila em outras linguagens de programação. Você pode reutilizar esta classe em outros projetos, basta criar um novo objeto, como fizemos anteriormente.
Implementamos a fila do zero usando listas. Mas existem módulos que já oferecem a funcionalidade de filas? Sim, vamos explorar algumas opções.
#2. Usando deque de collections
O deque é uma estrutura de dados que implementa uma fila de duas pontas, permitindo adicionar e remover elementos de ambas as extremidades. Isso a torna útil tanto para filas quanto para pilhas. Vamos verificar como usar o deque para implementar uma fila.
O deque é implementado usando listas duplamente encadeadas, o que garante um desempenho consistente para inserção e remoção de elementos, mas o acesso a elementos no meio da lista pode levar tempo O(n). No contexto de uma fila, não é necessário acessar os elementos intermediários, então o deque funciona perfeitamente.
Vejamos os métodos que o deque oferece:
- append(dado) – adiciona o dado ao final da fila
- popleft() – remove o primeiro elemento da fila
Para emular as funções “frente”, “traseira” e “esta_vazia”, podemos imprimir a fila inteira para verificar o primeiro e o último elemento, e usar “len()” para verificar se ela está vazia.
Vamos repetir os passos anteriores para testar a implementação:
from collections import deque ## Criando objeto deque fila = deque() ## Verificando se a fila está vazia -> True print(len(fila) == 0) ## Adicionando elementos fila.append(1) fila.append(2) fila.append(3) fila.append(4) fila.append(5) ## Verificando novamente se a fila está vazia -> False print(len(fila) == 0) ## Imprimindo a fila print(fila) ## Removendo o primeiro elemento -> 1 fila.popleft() ## Imprimindo a fila print(fila) ## Removendo todos os elementos fila.popleft() fila.popleft() fila.popleft() fila.popleft() ## Verificando pela última vez se a fila está vazia -> True print(len(fila) == 0)
O resultado da execução do código será similar a este:
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Utilizando Queue de queue
O módulo “queue” do Python oferece uma classe chamada “Queue” para a implementação de filas, semelhante à nossa primeira implementação. Vamos explorar os métodos disponíveis:
- put(dado) – adiciona o dado ao final da fila
- get() – remove e retorna o primeiro elemento da fila
- empty() – verifica se a fila está vazia
- qsize() – retorna o tamanho da fila
Vamos implementar a fila utilizando esses métodos:
from queue import Queue
## Criando objeto Queue
fila_objeto = Queue()
## Verificando se a fila está vazia -> True
print(fila_objeto.empty())
## Adicionando elementos
fila_objeto.put(1)
fila_objeto.put(2)
fila_objeto.put(3)
fila_objeto.put(4)
fila_objeto.put(5)
## Verificando novamente se a fila está vazia -> False
print(fila_objeto.empty())
## Removendo elementos e imprimindo
print(fila_objeto.get())
print(fila_objeto.get())
print(fila_objeto.get())
## Verificando o tamanho da fila
print("Tamanho", fila_objeto.qsize())
print(fila_objeto.get())
print(fila_objeto.get())
## Verificando pela última vez se a fila está vazia -> True
print(fila_objeto.empty())
A saída do código será semelhante a:
True False 1 2 3 Tamanho 2 4 5 True
Existem outros métodos na classe “Queue” que você pode explorar utilizando a função “dir()”.
Conclusão
Espero que este artigo tenha esclarecido o conceito de filas e suas diferentes formas de implementação em Python. As filas são úteis em diversos cenários onde a ordem de processamento segue o princípio FIFO. Utilize-as sempre que necessário em seus projetos. Se você tem interesse em aprofundar seus conhecimentos em Python, confira os materiais de estudo disponíveis.
Bons estudos! 🙂 👨💻