Python Fila: Exemplo FIFO, LIFO
Logan Jovem
O que é a Python Fila?
Uma fila é um contêiner que contém dados. Os dados inseridos primeiro serão removidos primeiro e, portanto, uma fila também é chamada de “Primeiro a entrar, primeiro a sair” (FIFO). A fila tem duas extremidades dianteira e traseira. Os itens são inseridos pela parte traseira e removidos pela parte frontal.
Como a Python Fila de trabalho?
A fila pode ser facilmente comparada com o exemplo do mundo real: a fila de pessoas esperando na fila do balcão, a pessoa que ficar primeiro receberá o ingresso primeiro, seguida pela próxima pessoa e assim por diante. A mesma lógica vale para a estrutura de dados da fila.
Aqui está uma representação diagramática da fila:
O método da Traseiro representa o ponto onde os itens são inseridos dentro da fila. Neste exemplo, 7 é o valor para isso.
O método da Frente representa o ponto onde os itens da fila serão removidos. Se você remover um item da fila, o primeiro elemento obtido será 1, conforme mostrado na figura.
O item 1 foi o primeiro a ser inserido na fila, e ao removê-lo é o primeiro a sair. Portanto, a fila é chamada FIRST IN FIRST OUT (FIFO)
Em uma fila, os itens são removidos em ordem e não podem ser removidos no meio. Você simplesmente não pode remover o item 5 aleatoriamente da fila, para isso você terá que remover todos os itens anteriores ao 5. Os itens da fila serão removidos na ordem em que forem inseridos.
Tipos de fila em Python
Existem basicamente dois tipos de fila em Python:
- Fila Primeiro a Entrar, Primeiro a Sair: Para isso, o elemento que sair primeiro será o primeiro a sair. Para trabalhar com FIFO, é necessário chamar Fila() classe do módulo de fila.
- Último a entrar, primeiro a sair: Aqui, o elemento que for inserido por último será o primeiro a sair. Para trabalhar com LIFO, você deve chamar LifoQueue() classe do módulo de fila.
Python fila de instalação
É muito fácil trabalhar com fila em python. Aqui estão as etapas a seguir para usar a fila em seu código.
Passo 1) Basta importar o módulo queue, conforme mostrado abaixo:
import queue
O módulo está disponível por padrão com python e você não precisa de nenhuma instalação adicional para começar a trabalhar com a fila. Existem 2 tipos de fila FIFO (primeiro a entrar, primeiro a sair) e LIFO (último a entrar, primeiro a sair).
Passo 2) Para trabalhar com fila FIFO, chame a classe Queue usando o módulo queue importado conforme mostrado abaixo:
import queue q1 = queue.Queue()
Passo 3) Para trabalhar com a fila LIFO, chame a classe LifoQueue() conforme mostrado abaixo:
import queue q1 = queue.LifoQueue()
Métodos disponíveis nas classes Queue e LifoQueue
A seguir estão os métodos importantes disponíveis nas classes Queue e LifoQueue:
- colocar(item): Isso colocará o item dentro da fila.
- pegar(): Isso retornará um item da fila.
- vazio(): Ele retornará verdadeiro se a fila estiver vazia e falso se houver itens presentes.
- qtamanho(): retorna o tamanho da fila.
- completo(): retorna verdadeiro se a fila estiver cheia, caso contrário, falso.
Exemplo de fila primeiro a entrar, primeiro a sair
No caso do primeiro a entrar, primeiro a sair, o elemento que sai primeiro será o primeiro a sair.
Adicionar um item em uma fila
Vamos trabalhar em um exemplo para adicionar um item em uma fila. Para começar a trabalhar com a fila, primeiro importe o módulo queue, conforme mostrado no exemplo abaixo.
Para adicionar um item, você pode usar o método put() conforme mostrado no exemplo:
import queue q1 = queue.Queue() q1.put(10) #this will additem 10 to the queue.
Por padrão, o tamanho da fila é infinito e você pode adicionar qualquer número de itens a ela. Caso queira definir o tamanho da fila o mesmo pode ser feito da seguinte forma
import queue q1 = queue.Queue(5) #The max size is 5. q1.put(1) q1.put(2) q1.put(3) q1.put(4) q1.put(5) print(q1.full()) # will return true.
Saída:
True
Agora o tamanho da fila é 5 e não levará mais de 5 itens, e o método q1.full() retornará verdadeiro. Adicionar mais itens não executará mais o código.
Remover um item da fila
Para remover um item da fila, você pode usar o método chamado get(). Este método permite itens da fila quando chamados.
O exemplo a seguir mostra como remover um item da fila.
import queue
q1 = queue.Queue()
q1.put(10)
item1 = q1.get()
print('The item removed from the queue is ', item1)
Saída:
The item removed from the queue is 10
Exemplo de fila Last In First Out
No caso de último na fila primeiro a sair, o elemento que for inserido por último será o primeiro a sair.
Para trabalhar com LIFO, ou seja, último na fila de saída, precisamos importar o módulo de fila e utilizar o método LifoQueue().
Adicionar um item em uma fila
Aqui entenderemos como adicionar um item à fila LIFO.
import queue q1 = queue.LifoQueue() q1.put(10)
Você deve usar o método put() em LifoQueue, conforme mostrado no exemplo acima.
Remover um item da fila
Para remover um item do LIFOqueue você pode usar o método get().
import queue
q1 = queue.LifoQueue()
q1.put(10)
item1 = q1.get()
print('The item removed from the LIFO queue is ', item1)
Saída:
The item removed from the LIFO queue is 10
Adicione mais de 1 item em uma fila
Nos exemplos acima, vimos como adicionar um único item e remover o item FIFO e LIFOqueue. Agora veremos como adicionar mais de um item e também removê-lo.
Adicionar um item em uma FIFOqueue
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Remover um item da FIFOqueue
import queue
q1 = queue.Queue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Saída:
The value is 0 The value is 1 The value is 2 The value is 3 The value is 4 The value is 5 The value is 6 The value is 7 The value is 8 The value is 9 The value is 10 The value is 11 The value is 12 The value is 13 The value is 14 The value is 15 The value is 16 The value is 17 The value is 18 The value is 19
Adicionar um item em uma fila LIFO
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
Remover um item da fila LIFO
import queue
q1 = queue.LifoQueue()
for i in range(20):
q1.put(i) # this will additem from 0 to 20 to the queue
while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.
Saída:
The value is 19 The value is 18 The value is 17 The value is 16 The value is 15 The value is 14 The value is 13 The value is 12 The value is 11 The value is 10 The value is 9 The value is 8 The value is 7 The value is 6 The value is 5 The value is 4 The value is 3 The value is 2 The value is 1 The value is 0
Classificando fila
O exemplo a seguir mostra a classificação da fila. O algoritmo usado para classificação é a classificação por bolha.
import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
#using bubble sort on the queue
n = q1.qsize()
for i in range(n):
x = q1.get() # the element is removed
for j in range(n-1):
y = q1.get() # the element is removed
if x > y :
q1.put(y) #the smaller one is put at the start of the queue
else:
q1.put(x) # the smaller one is put at the start of the queue
x = y # the greater one is replaced with x and compared again with nextelement
q1.put(x)
while (q1.empty() == False):
print(q1.queue[0], end = " ")
q1.get()
Saída:
3 4 5 10 11 21
Reversing Queue
Para reverter a fila, você pode usar outra fila e recursão.
O exemplo a seguir mostra como reverter a fila.
Exemplo:
import queue
q1 = queue.Queue()
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
def reverseQueue (q1src, q2dest) :
buffer = q1src.get()
if (q1src.empty() == False) :
reverseQueue(q1src, q2dest) #using recursion
q2dest.put(buffer)
return q2dest
q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)
while (qReversed.empty() == False):
print(qReversed.queue[0], end = " ")
qReversed.get()
Saída:
10 3 21 4 5 11
Resumo
- Uma fila é um contêiner que contém dados. Existem dois tipos de fila, FIFO e LIFO.
- Para um FIFO (First in First out Queue), o elemento que sai primeiro será o primeiro a sair.
- Para um LIFO (Last in First out Queue), o elemento que for inserido por último será o primeiro a sair.
- Um item em uma fila é adicionado usando o método put(item).
- Para remover um item, o método get() é usado.
