As estruturas de dados desempenham um papel fundamental no mundo da programação. Eles nos ajudam a organizar nossos dados de forma que possam ser usados de forma eficiente. A Fila é uma das estruturas de dados mais simples disponíveis.
Neste artigo, aprenderemos sobre a Queue e sua implementação em Python.
últimas postagens
O que é uma Fila?
Uma Fila é uma estrutura de dados linear que segue o princípio Primeiro a Entrar/Primeiro a Sair (FIFO). É o oposto da estrutura de dados Stack.
Podemos comparar a fila com uma fila real na bilheteria do cinema. Vejamos a ilustração de uma fila a seguir.
Se você observar a fila no balcão, a segunda pessoa poderá ir ao balcão somente depois que a primeira terminar seu trabalho. Aqui a primeira pessoa vem ao balcão e depois a segunda pessoa. Então, aqui as pessoas estão seguindo o princípio FIFO (First In/First Out). Quem vier primeiro, terminará o trabalho primeiro. Podemos ver um tipo semelhante de filas em nosso dia-a-dia.
A estrutura de dados Queue também segue o mesmo princípio. Agora, você sabe o que são filas e seu princípio. Vamos ver as operações que podem ser executadas em uma estrutura de dados de fila.
Operações em Fila
Semelhante à pilha, encontraremos duas operações principais em uma estrutura de dados de fila.
enfileirar(dados)
Adiciona novos dados à fila no final. O lado é chamado de traseiro.
desenfileirar()
Remove os dados da frente da fila. O lado é chamado de frente.
Vamos ver as ilustrações das operações da fila para melhor entendimento. Uma imagem fala mais que mil palavras.
Podemos escrever algumas funções auxiliares para obter mais informações sobre a fila. Não há limite para o número de funções auxiliares que você terá. Vamos nos ater ao mais importante, uma vez mencionado abaixo, por enquanto.
traseira()
Retorna o primeiro elemento do final da fila.
frente()
Retorna o primeiro elemento desde o início da fila.
está vazia()
Retorna se a fila está vazia ou não.
Não é chato para você? Refiro-me aos tópicos conceituais.
Para mim sim!
Mas, não podemos fazer nada sem conhecer os conceitos. Temos que conhecê-lo antes da implementação. Não se preocupe, é hora de sujar as mãos com algum código.
Presumo que você tenha o python instalado no seu PC, caso contrário, você também pode tentar o compilador online.
Implementação de Fila
A implementação de uma fila não levará mais de 15 minutos para um programador. Depois de aprender, você dirá. Talvez você possa implementá-lo em minutos após este tutorial.
Existem várias maneiras de implementar a fila em Python. Vamos ver diferentes implementações de fila passo a passo.
#1. Lista
A lista é um tipo de dados embutido em Python. Vamos usar o tipo de dados list para implementar uma fila em uma classe. Orientaremos você por diferentes etapas para implementar a estrutura de dados da fila desde o início, sem nenhum módulo. Vamos pular nisso.
Passo 1:
Escreva uma classe chamada Fila.
class Queue: pass
Passo 2:
Tem que haver alguma variável para armazenar os dados da fila na classe. Vamos nomeá-lo elementos. E é uma lista, claro.
class Queue: def __init__(self): self.elements = []
Etapa 3:
Para inserir dados na fila, precisamos de um método na classe. O método é chamado enqueue como já discutimos na seção anterior do tutorial.
O método pega alguns dados e os adiciona à fila (elementos). Podemos usar o método append do tipo de dados list para adicionar dados no final da fila.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Passo 4:
A fila precisa ter uma saída. E isso se chama desenfileiramento. Acho que você já adivinhou que vamos usar o método pop do tipo de dados da lista. Se você adivinhou ou não, felicidades!
O método pop do tipo de dados list exclui um elemento da lista do índice fornecido. Se não fornecemos nenhum índice, ele exclui o último elemento da lista.
Aqui, precisamos excluir o primeiro elemento da lista. Então, temos que passar o índice 0 para o método pop.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Isso é o suficiente para uma fila. Porém, precisamos das funções auxiliares para testar se as operações da fila estão funcionando corretamente ou não. Vamos escrever as funções auxiliares também.
Passo 5:
O método rear() é usado para obter o último elemento da fila. A indexação negativa no tipo de dados de lista nos ajuda a obter o último elemento da fila.
class Queue: # ... def rear(self): return self.elements[-1]
Passo 6:
O método front() é usado para obter o primeiro elemento da fila. Podemos obter o primeiro elemento da fila usando o índice da lista.
class Queue: # ... def front(self): return self.elements[0]
Passo 7:
O método is_empty() é usado para verificar se a fila está vazia ou não. Podemos verificar o comprimento da lista.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Ufa! concluiu a parte de implementação da estrutura de dados da fila. Precisamos criar um objeto para a classe Queue usar.
Vamos fazer isso.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Agora, temos um objeto Queue. Vamos testá-lo com algumas séries de operações.
- Verifique se a fila está vazia ou não usando o método is_empty. Deve retornar True.
- Adicione os números 1, 2, 3, 4, 5 à fila usando o método enqueue.
- O método is_empty deve retornar False. Confira.
- Imprima os elementos frontal e traseiro usando os métodos frontal e traseiro, respectivamente.
- Remova o elemento da fila usando o método dequeue.
- Verifique o elemento frontal. Deve retornar o elemento 2.
- Agora, remova todos os elementos da fila.
- O método is_empty deve retornar True. Confira.
Acho que é o suficiente para testar nossa implementação de fila. Escreva o código para cada etapa mencionada acima para testar a fila.
Você escreveu o código?
Não, não se preocupe.
Verifique o código abaixo.
class Queue: def __init__(self): self.elements = [] def enqueue(self, data): self.elements.append(data) return data def dequeue(self): return self.elements.pop(0) def rear(self): return self.elements[-1] def front(self): return self.elements[0] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': queue = Queue() ## checking is_empty method -> True print(queue.is_empty()) ## adding the elements queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) ## again checking is_empty method -> False print(queue.is_empty()) ## printing the front and rear elements using front and rear methods respectively -> 1, 5 print(queue.front(), end=' ') print(queue.rear()) ## removing the element -> 1 queue.dequeue() ## checking the front and rear elements using front and rear methods respectively -> 2 5 print(queue.front(), end=' ') print(queue.rear()) ## removing all the elements queue.dequeue() queue.dequeue() queue.dequeue() queue.dequeue() ## checking the is_empty method for the last time -> True print(queue.is_empty())
Acho que você executou o programa acima. Você pode obter uma saída semelhante ao seguinte resultado.
True False 1 5 2 5 True
Podemos usar diretamente o tipo de dados de lista como uma estrutura de dados de fila. A implementação da fila acima ajuda você a entender melhor a implementação da fila em outras linguagens de programação.
Você também pode usar a implementação de classe acima de uma fila em um programa diferente de um projeto simplesmente criando o objeto como fizemos anteriormente.
Implementamos a fila do zero usando o tipo de dados de lista. Existem módulos integrados para a fila? Sim! temos implementações de fila integradas. Vamos vê-los.
#2. deque de coleções
É implementado como uma fila dupla. Como suporta a adição e remoção de elementos de ambas as extremidades, podemos usá-lo como pilha e fila. Vamos ver a implementação da fila usando dequeue.
Ela é implementada usando outras estruturas de dados chamadas de lista duplamente encadeada. Portanto, o desempenho da inserção e exclusão de elementos é consistente. Acessar elementos da lista encadeada do meio levou tempo O(n). Podemos usá-lo como uma fila, pois não há necessidade de acessar os elementos intermediários da fila.
Vamos verificar os diferentes métodos que o desenfileiramento nos oferece.
- append(data) – usado para adicionar os dados à fila
- popleft() – usado para remover o primeiro elemento da fila
Não há métodos alternativos para front, rear e is_empty. Podemos imprimir toda a fila no lugar dos métodos frontal e traseiro. Em seguida, podemos usar o método len para verificar se a fila está vazia ou não.
Seguimos uma série de etapas para testar a implementação da fila no anterior. Vamos seguir a mesma série de etapas aqui também.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
Você obterá um resultado semelhante à saída a seguir.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Fila da fila
Python tem um módulo interno chamado queue que atende a uma classe chamada Queue para a implementação da fila. É semelhante ao que implementamos antes.
Primeiro, vamos verificar diferentes métodos da classe Queue.
- put(data) – adiciona ou empurra os dados para a fila
- get() – remove o primeiro elemento da fila e o retorna
- empty() – retorna se a pilha está vazia ou não
- qsize() – retorna o comprimento da fila.
Vamos implementar a fila com os métodos acima.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Verifique a saída do código acima.
True False 1 2 3 Size 2 4 5 True
Existem alguns outros métodos na classe Queue. Você pode explorá-los usando a função interna dir.
Conclusão
Espero que você tenha aprendido sobre a estrutura de dados da fila e sua implementação. Isso é tudo para a fila. Você pode usar a fila em diferentes locais onde precisam ser processados na ordem FIFO (primeiro a entrar/primeiro a sair). Use a fila na resolução de problemas sempre que tiver o caso de usá-la.
Interessado em dominar o Python? Confira esses recursos de aprendizagem.
Boa codificação 🙂 👨💻