Fila

7.1 Definição de fila e suas propriedades

Fila é uma estrutura de dados abstrata que representa uma coleção ordenada de elementos, organizada pelo princípio "primeiro a entrar, primeiro a sair" (First In, First Out, FIFO). A fila pode ser imaginada como uma fila de pessoas em uma loja: a primeira pessoa na fila é atendida primeiro.

Propriedades da fila:

• FIFO (First In, First Out): O primeiro elemento adicionado será o primeiro removido.
• Operações limitadas: A fila suporta um conjunto limitado de operações — adicionar (enqueue), remover (dequeue) e visualizar (peek) o elemento na posição frontal.
• Acesso unidirecional: O acesso aos elementos é possível apenas pelas extremidades frontal (front) e traseira (rear).
• Facilidade de implementação: A fila pode ser facilmente implementada usando um array ou lista encadeada.

Princípio de funcionamento FIFO:

• Adição de elemento (enqueue): Um novo elemento é adicionado ao fim da fila.
• Remoção de elemento (dequeue): O primeiro elemento adicionado é removido do início da fila.
• Visualização do elemento frontal (peek): Permite ver o elemento na posição frontal da fila sem removê-lo.

Os elementos da fila são adicionados por um lado (parte traseira) e removidos do outro lado (parte frontal). Assim, o primeiro elemento adicionado é o primeiro removido.

7.2 Operações principais

Operações principais: enqueue, dequeue, peek

Operação enqueue: Adiciona um novo elemento ao fim da fila.

Complexidade de tempo: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Saída: deque([10, 20])

Operação dequeue: Remove e retorna o elemento do início da fila.

Complexidade de tempo: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Saída: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Saída: 10
print(queue)  # Saída: deque([20])

Operação peek: Retorna o elemento na posição frontal da fila sem removê-lo.

Complexidade de tempo: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Saída: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Saída: 10

7.3 Exemplos de uso da fila

Vamos ver alguns exemplos de uso de fila.

1 Gerenciamento de trabalhos de impressão

A fila é usada para gerenciar trabalhos de impressão, onde documentos são adicionados à fila e impressos na ordem de chegada.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job}")

# Exemplo de uso:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Saída: Printing: Document1.pdf
printer_queue.print_job()  # Saída: Printing: Document2.pdf

2 Processamento de solicitações em servidor web

A fila é usada para gerenciar solicitações de clientes que chegam ao servidor web. As solicitações são processadas na ordem de chegada.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Processing request: {request}")

# Exemplo de uso:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Saída: Processing request: GET /index.html
request_queue.process_request()  # Saída: Processing request: POST /submit-form

3 Fila de mensagens em sistemas de mensageria

A fila é usada para gerenciar mensagens em sistemas de troca de informações (por exemplo, em brokers de mensagens). As mensagens são processadas na ordem de chegada.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Received message: {message}")

# Exemplo de uso:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Saída: Received message: Hello
message_queue.receive_message()  # Saída: Received message: World