FIFO — First In, First Out

Fila: entrada no back, saída no front

A fila é um tipo abstrato no qual somente o elemento inserido há mais tempo pode ser removido.

enqueue · dequeue · front

Contrato da fila

  • enqueue(valor) adiciona um elemento no back/tail.
  • dequeue() remove e retorna o elemento do front/head.
  • front() consulta o próximo elemento sem removê-lo.
  • FIFO preserva a ordem de chegada.

Implementações corretas

Uma fila pode usar um array circular ou uma lista encadeada com referências para as duas pontas.

Usar list.pop(0) em Python funciona logicamente, mas exige deslocar os demais elementos e custa O(n).

Laboratório: fila simplesmente encadeada

front aponta para a primeira célula e back para a última. Cada célula guarda o ID da próxima; a última aponta para None.

Enqueue no back e dequeue no front

Operação
Ordem do front ao back

    Python: collections.deque

    deque fornece inserções e remoções nas duas extremidades com desempenho aproximadamente O(1). Para fila, usamos somente o back para entrada e o front para saída.

    Pythonfila pronta
    from collections import deque

fila = deque([2, 3, 4])

fila.append(5)       # enqueue no back
proximo = fila[0]    # consulta o front
saiu = fila.popleft()# dequeue no front

print(saiu)          # 2
print(list(fila))    # [3, 4, 5]

    Fila encadeada

    Manter front e back permite enqueue e dequeue em O(1), inclusive quando a fila tem muitos elementos.

    Pythonligações essenciais
    class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.back = None

    def enqueue(self, value):
        node = Node(value)

        # Na primeira inserção, front e back apontam para o mesmo nó.
        if self.back is None:
            self.front = self.back = node
            return

        # Nas demais, o back antigo aponta para o novo último nó.
        self.back.next = node
        self.back = node

    def dequeue(self):
        if self.front is None:
            raise IndexError("fila vazia")

        # Retiramos sempre do front para preservar a ordem FIFO.
        value = self.front.value
        self.front = self.front.next

        # Ao remover o último nó, as duas extremidades voltam a ser None.
        if self.front is None:
            self.back = None
        return value

    Referências usadas