Filas (Queue)

Uma fila (Queue) é uma estrutura de dados linear que segue o princípio FIFO (First In, First Out), ou seja, o primeiro elemento a entrar é também o primeiro a sair. Isso se assemelha a uma fila de pessoas em um banco: quem chega primeiro é atendido primeiro.

Operações Básicas

Uma fila suporta as seguintes operações fundamentais:

• Enqueue (Inserção): Adiciona um elemento ao final da fila.

• Dequeue (Remoção): Remove o elemento da frente da fila.

• Front (ou Peek): Retorna o primeiro elemento da fila sem removê-lo.

• isEmpty: Verifica se a fila está vazia.

• Size: Retorna o número de elementos na fila.

Implementação de uma Fila

Podemos implementar uma fila de diversas formas, sendo as mais comuns:

1. Usando uma Lista (Array ou Listas Ligadas)

Implementação em Python usando collections.deque

from collections import deque

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

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Empty")
        return self.queue.popleft()

    def front(self):
        if self.is_empty():
            return None
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

Tipos de Filas

Existem variações da estrutura de fila que atendem a diferentes necessidades:

1. Fila Simples

Segue a regra FIFO padrão, como visto anteriormente.

2. Fila Circular

Os elementos ocupam um espaço fixo e, quando o final da fila é atingido, os novos elementos são inseridos no início se houver espaço livre.

3. Fila Dupla (Deque - Double-Ended Queue)

Permite inserção e remoção de elementos tanto no início quanto no fim.

As filas são estruturas essenciais na computação, com aplicações em sistemas de alta performance, gerenciadores de tarefas e muito mais. A escolha da implementação correta pode impactar diretamente o desempenho do sistema. Por exemplo, ao utilizar listas em Python, a operação dequeue em uma lista comum (list) tem complexidade O(n), pois exige o deslocamento dos elementos, enquanto o uso de collections.deque reduz essa complexidade para O(1).