O que é a estrutura de dados da fila em Python?

Como você já estudou sobre a importância das estruturas de dados no artigo anterior, vamos mergulhar direto no tópico do artigo, ou seja, Estrutura de dados da fila. Discutirei os seguintes tópicos:

• Necessidade de estrutura de dados da fila
• Exemplos da vida diária de fila
• Criação de uma estrutura de dados de fila
• En-queue
• Retirar da fila
• Aplicações de Fila

Necessidade de estrutura de dados da fila

Suponha que você queira um filme um dia. No multiplex, os tíquetes eram emitidos por ordem de chegada e as pessoas ficavam atrás umas das outras esperando sua vez. Então o que você vai fazer?? Você deve ter ido para trás e ficado atrás da última pessoa que esperava pela passagem.

Aqui, as pessoas estão postas uma atrás da outra e são atendidas com base no Primeiro a entrar, primeiro a sair (FIFO) mecanismo. Tal arranjo é conhecido como Fila.

Exemplos da vida diária de fila

Vamos considerar alguns exemplos onde vemos o tipo de fila funcionando na vida diária:

código da série fibonacci em java

• Sistema de atendimento telefônico- A pessoa que ligar primeiro em seu gadget será atendida primeiro.
• Máquina de verificação de bagagem - Verifica a Bagagem que foi guardada primeiro na esteira.
• Veículos na ponte de pedágio - Os veículos que chegam cedo saem primeiro.
• Centro de Atendimento - os sistemas telefônicos usarão filas, para manter as pessoas que ligam para elas em ordem, até que um representante de serviço esteja disponível.

Todos esses exemplos seguem First-In-Last-Out estratégia.

Criação de uma estrutura de dados de fila

Além das operações complementares, posso dizer que as principais Operações possíveis na Fila são:

1. En-queue ou adicione um elemento ao final da fila.

2 Retirar da fila ou remova um elemento da frente da fila

Agora, vamos começar criando a classe Queue em Python:

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ traseiro = -1 self .__ front = 0

• tamanho máximo é o número máximo de elementos esperados na fila.
• Os elementos da fila são armazenados na lista python
• traseiro indica a posição do índice do último elemento na fila.
• A parte traseira é inicialmente considerada -1 porque a fila está vazia
• Frente indica a posição do primeiro elemento na fila.
• A frente é considerada 0 inicialmente porque sempre apontará para o primeiro elemento da fila

Enqueue

Agora, quando você está tentando enfileirar elementos na Fila, deve se lembrar dos seguintes pontos:

• Se há espaço restante na fila ou não, ou seja, se traseiro é igual a max_size -1
• A parte traseira apontará para o último elemento inserido na fila.

Então, qual será o algoritmo ??

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns valor bool se a fila estiver cheia ou não, True if full e False caso contrário def is_full (self): return self .__ rear == self .__ max_size-1 # insere / enfileira dados na fila se não estiver cheia def enqueue (self, data): if (self.is_full ()): print ('A fila está cheia. Não é possível enfileirar') else: self .__ rear + = 1 self. __elements [self .__ rear] = data #exibe todo o conteúdo da fila def display (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) #Você pode usar o abaixo de __str __ () para imprimir os elementos do objeto DS durante a depuração def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

Agora, quando você executa o seguinte:

queue1 = Queue (5)

#Enfileire todos os elementos necessários.

queue1.enqueue (“A”)

queue1.enqueue (“B”)

queue1.enqueue (“C”)

queue1.enqueue (“D”)

queue1.enqueue(“E”)

queue1.display ()

queue1.enqueue (“F”)

imprimir (fila1)

Resultado:

PARA

B

C

D

É

A fila está cheia. Não é possível enfileirar

Dados da fila (frente para trás): A B C D E

De-Queue

Agora, como você inseriu / enfileirou os elementos na fila, deseja desenfileirá-los / excluí-los da frente, portanto, tome os seguintes cuidados:

• Existem elementos na fila, ou seja, a parte traseira não deve ser igual a -1.
• Em segundo lugar, você precisa se lembrar que como os elementos são excluídos da frente, após a exclusão da frente deve ser incrementado para apontar a próxima frente.
• A frente não deve apontar para o fim da fila, ou seja, igual a max_size.

Então, qual será o algoritmo ??

#função para verificar se a fila está vazia ou não def is_empty (self): if (self .__ rear == - 1 ou self .__ front == self .__ max_size): return True else: return False #função para remover um elemento e retornar it def desenfileirar (self): if (self.is_empty ()): print ('a fila já está vazia') else: data = self .__ elements [self .__ front] self .__ front + = 1 dados de retorno # função para exibir elementos de frente para trás se a fila não estiver vazia def display (self): if (not self.is_empty ()): para i no intervalo (self .__ frontal, self .__ traseiro + 1): print (self .__ elements [i]) else : print ('fila vazia')

Agora, quando você executa o seguinte:

queue1 = Queue (5)

#Enfileirar todos os elementos necessários

queue1.enqueue (“A”)

queue1.enqueue (“B”)

queue1.enqueue (“C”)

queue1.enqueue (“D”)

queue1.enqueue(“E”)

imprimir (fila1)

#Dequeue todos os elementos necessários

print (“Desenfileirado:“, queue1.dequeue ())

print (“Desenfileirado:“, queue1.dequeue ())

print (“Desenfileirado:“, queue1.dequeue ())

print (“Desenfileirado:“, queue1.dequeue ())

print (“Desenfileirado:“, queue1.dequeue ())

print (“Desenfileirado:“, queue1.dequeue ())

#Exibe todos os elementos da fila.

queue1.display ()

Resultado:

Dados da fila (frente para trás): A B C D E

Retirado da fila: A

Retirado da fila: B

Desenfileirado: C

Retirado da fila: D

Retirado da fila: E

fila já está vazia

Desenfileirado: Nenhum

fila vazia

Aplicações de Fila

A partir de agora, você já entendeu os fundamentos da fila. Agora, para mergulhar mais fundo, examinaremos algumas de suas aplicações.

• Exemplo 1:

Fila de impressão no Windows usa uma fila para armazenar todos os trabalhos de impressão ativos e pendentes. Quando queremos imprimir documentos, emitimos comandos de impressão um após o outro. Com base nos comandos de impressão, os documentos serão alinhados na fila de impressão. Quando a impressora estiver pronta, o documento será enviado primeiro na ordem de saída para ser impresso.

Suponha que você tenha emitido comandos de impressão para 3 documentos na ordem doc1, seguidos por doc2 e doc3.
A fila de impressão será preenchida conforme mostrado abaixo:

doc-n, onde o doc é o documento enviado para impressão e n, é o número de páginas do documento. Por exemplo, doc2-10 significa que o doc2 deve ser impresso e possui 10 páginas. Aqui está um código que simula a operação da fila de impressão. Percorra o código e observe como a fila é usada nesta implementação.

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ posterior): return True return False def enqueue (self, data): if (self.is_full ()): print ('Queue is full !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Queue is empty! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): para o índice no intervalo (self .__ front, self .__ posterior + 1): print (self .__ elements [índice]) def get_max_size (self): return self .__ max_size #Você pode usar o seguinte __str __ () para imprimir os elementos do objeto DS enquanto #debugging def __str __ (self): msg = [] index = self .__ front while (índice<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()

Resultado:

doc 1-5 enviado para impressão

doc2-3 enviado para impressão

doc3-6 enviado para impressão

doc 1-5 impresso

Restante nº de páginas na impressora: 7

doc2-3 impresso

Restante nº de páginas na impressora: 4

Não foi possível imprimir o doc3. Páginas insuficientes na impressora

• Exemplo 2:

Vamos tentar entender outro exemplo que usa a estrutura de dados da fila. Você pode tentar entender o código e dizer o que a função a seguir faz?

1. def fun (n):
2. aqueue = Queue (100)
3. para num no intervalo (1, n + 1):
4. enqueue(num)
5. resultado = 1
6. while (not (aqueue.is_empty ())):
7. num = aqueue.dequeue()
8. resultado * = num
9. imprimir (resultado)

Quando a função fun () é invocada passando n,

• linhas 2 a 4 enfileira os elementos de 1 a n
• as linhas 5 a 8 encontram o produto desses elementos eliminando-o um por um

Com isso, chegamos ao fim deste artigo sobre Estrutura de dados de fila. Se você entendeu e executou os códigos com sucesso, não é mais um novato na Estrutura de Dados da Fila.

Tem alguma questão para nós? Mencione isso na seção de comentários deste artigo e entraremos em contato com você o mais breve possível.

Para obter conhecimento aprofundado sobre Python e seus vários aplicativos, você pode se inscrever para com suporte 24/7 e acesso vitalício.