Fila

Conceito

Fila é a disciplina FIFO: o primeiro a entrar é o primeiro a sair. enqueue no fim, dequeue no início.

A dificuldade é que ela mexe nas duas pontas, e é aí que a implementação ingênua falha: remover do início de um array significa deslocar todos os outros elementos uma posição → O(n) por dequeue.

A solução é o buffer circular (ring buffer): um array de tamanho fixo com dois índices, head e tail, que avançam módulo a capacidade. As duas pontas passam a ser O(1) e nada desloca. O preço é capacidade fixa — ou realocação quando enche, o que recupera o amortizado O(1).

Variantes que não são fila e vivem sendo chamadas de fila:

A fila de prioridade é a confusão mais comum: ela não é uma fila com um extra, é uma estrutura diferente (heap), com O(log n) de inserção e remoção em vez de O(1).

Onde filas aparecem em sistemas reais: fila de tarefas, BFS em grafos, buffer entre produtor e consumidor, escalonador de processos, e — o caso que dominou a última década — filas de mensagens entre serviços. Em todos, a fila existe para desacoplar ritmos: quem produz e quem consome não precisam ir na mesma velocidade.

Em Go

Slice como fila é uma armadilha:

q = append(q, v) // enqueue: ok
v, q = q[0], q[1:] // dequeue: O(1) em tempo, mas...

q[1:] avança o ponteiro base do header. O elemento consumido fica inalcançável por você, mas continua vivo dentro do array de trás — e o array nunca encolhe. Uma fila de longa duração assim cresce para sempre. É vazamento, não desperdício.

O idioma de fila em Go é o channel. chan T é uma fila FIFO, com capacidade, segura para uso concorrente e com semântica de bloqueio embutida:

q := make(chan Tarefa, 100) // fila com capacidade 100
q <- t                      // enqueue (bloqueia se cheia)
t := <-q                    // dequeue (bloqueia se vazia)

Esse é o ponto em que Go difere estruturalmente das outras linguagens: a fila é uma primitiva da linguagem, não uma classe de biblioteca, porque ela é o mecanismo de comunicação entre goroutines. O bloqueio ao encher é backpressure de graça.

Quando você quer fila sem canal (single-thread, hot path), escreve um ring buffer. Para fila de prioridade, container/heap.

Respostas às perguntas-guia

1. Por que implementar fila sobre array simples degrada para O(n)?

Conceito: porque remover do início exige deslocar todos os elementos restantes.

Em Go, a variante q = q[1:] não desloca (é O(1)), mas troca o problema de tempo por um de memória: o array de trás nunca é liberado nem reusado, e a fila vaza.

2. O que um buffer circular resolve?

Conceito: elimina o deslocamento fazendo os índices darem a volta (módulo a capacidade). As duas pontas ficam O(1) e a memória é reusada.

Em Go: é o que o runtime usa por baixo do chan com buffer — o canal é essencialmente um ring buffer com mutex e filas de goroutines esperando.

3. Qual a diferença entre fila, deque e fila de prioridade?

Conceito: ordem de chegada; escolha de ponta; ordem de prioridade. A terceira é um heap e tem custo O(log n), não O(1).

Em Go: fila → chan ou ring buffer; deque → slice com as duas pontas, ou dois slices; prioridade → container/heap (você implementa a interface heap.Interface).

4. Onde filas aparecem em sistemas reais que você já usou?

Conceito: sempre que dois lados precisam trabalhar em ritmos diferentes — a fila absorve a diferença e transforma pico em atraso.

Em Go: worker pool é o padrão canônico — N goroutines lendo do mesmo canal. E a decisão de projeto mais importante é a capacidade: canal sem buffer sincroniza os dois lados; canal com buffer absorve rajada e esconde o problema até encher.

Trade-offs

Do conceito:

• Fila desacopla ritmos e transforma perda em latência — o que é melhor até a fila crescer sem limite, e então é pior.
• Ring buffer compra O(1) nas duas pontas e cobra capacidade fixa. Capacidade fixa é frequentemente a decisão certa: uma fila ilimitada é um vazamento com boa reputação.
• Fila de prioridade compra ordenação e cobra O(log n) por operação.

Em Go:

• chan compra segurança de concorrência, bloqueio e select; cobra alocação e um custo por operação bem maior que um append (há mutex e possível parada de goroutine).
• Canal sem buffer é sincronização, não fila. Canal com buffer grande esconde problema de capacidade até virar OOM.
• Slice como fila é o erro que passa em revisão de código porque parece O(1).

Exemplo prático

package main

import "fmt"

// Ring buffer: O(1) nas duas pontas, memória reusada.
type Fila[T any] struct {
	buf        []T
	head, tail int
	tam        int
}

func NovaFila[T any](cap int) *Fila[T] {
	return &Fila[T]{buf: make([]T, cap)}
}

func (f *Fila[T]) Enfileira(v T) bool {
	if f.tam == len(f.buf) {
		return false // cheia: capacidade fixa é decisão, não limitação
	}
	f.buf[f.tail] = v
	f.tail = (f.tail + 1) % len(f.buf) // <- a volta
	f.tam++
	return true
}

func (f *Fila[T]) Desenfileira() (T, bool) {
	var zero T
	if f.tam == 0 {
		return zero, false
	}
	v := f.buf[f.head]
	f.buf[f.head] = zero // libera a referência
	f.head = (f.head + 1) % len(f.buf)
	f.tam--
	return v, true
}

func main() {
	f := NovaFila[string](3)
	f.Enfileira("a")
	f.Enfileira("b")
	f.Enfileira("c")
	fmt.Println("cheia rejeita:", f.Enfileira("d")) // false

	v, _ := f.Desenfileira()
	fmt.Println("saiu:", v) // a — FIFO
	f.Enfileira("d")        // reusa o slot de "a", dando a volta

	for {
		v, ok := f.Desenfileira()
		if !ok {
			break
		}
		fmt.Print(v, " ") // b c d
	}
	fmt.Println()

	// O idioma Go: channel É uma fila FIFO
	ch := make(chan int, 3)
	ch <- 1
	ch <- 2
	close(ch)
	for v := range ch {
		fmt.Print(v, " ") // 1 2
	}
	fmt.Println()
}

Relacionado

• 4. Pilha — a disciplina oposta
• 4. Grafos — semana 3, BFS é uma fila; DFS é uma pilha
• 2. Array — o ring buffer é um array com aritmética modular
• 1. Notação Big-O — por que O(n) por dequeue é inaceitável

---

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação