Fila Python: exemplo FIFO, LIFO

O que é fila Python?

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 funciona a fila Python?

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:

Trabalho de fila Python

A Traseiro representa o ponto onde os itens são inseridos dentro da fila. Neste exemplo, 7 é o valor para isso.

A 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)

Trabalho de fila Python

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.

Instalação da fila Python

É 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

Following sã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, outrowise falsa

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 seguintewing exemplo 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

Following O exemplo 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

Fila reversa

Para reverter a fila, você pode usar outra fila e recursão.

O seguintewing O exemplo 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.