Filas

Tirar o primeiro de 1000 valores de um array de JavaScript com shift move os outros 999; um buffer circular faz o mesmo trabalho em um passo.

Primeiro a entrar, primeiro a sair

Uma fila é uma fila no balcão de uma loja. As pessoas entram pelo fim e são atendidas pela frente, então quem chegou primeiro sai primeiro. A regra é primeiro a entrar, primeiro a sair (FIFO). As duas operações são enqueue (enfileirar), que acrescenta um valor no fim, e dequeue (desenfileirar), que remove o valor da frente. Nas notas do 6.006 do MIT, uma fila é a interface de sequência limitada a insert last(x) e delete first().

As filas aparecem em todo lugar em que o trabalho precisa ser tratado na ordem de chegada: documentos esperando uma impressora, teclas apertadas esperando um programa, mensagens esperando um servidor. A busca em largura, do curso de algoritmos, guarda numa fila os quadrados que ainda precisa visitar, e é exatamente por isso que ela explora em anéis de mesma distância.

O jeito fácil e o seu custo escondido

Em JavaScript, a fila óbvia é um array: push para enfileirar no fim e shift para desenfileirar da frente. Funciona, e para filas curtas está bom. Mas veja o que o shift faz. O MDN diz que ele "desloca todos os valores 1 posição para a esquerda", e a especificação ECMAScript o escreve como um laço que copia o elemento k para a posição k − 1, para todo k. A frente de um array é a ponta cara, como a primeira unidade mostrou. Desenfileirar de uma fila de n valores custa 1 leitura mais n − 1 movimentos, então uma fila de 1000 valores custa 1000 passos por desenfileiramento. (Os motores podem usar atalhos internos, mas a especificação não promete nada.)

Se você enfileira 5 valores num array vazio e depois desenfileira os 5, os enfileiramentos custam 5 passos e os desenfileiramentos custam 5 + 4 + 3 + 2 + 1 = 15, 20 no total. A maior parte disso é mover valores que nem estão sendo removidos.

Não mova os valores, mova a frente

A solução é parar de mover os valores e, em vez disso, lembrar onde está a frente. Guarde um índice chamado head. O dequeue lê o valor em head e soma 1 a head; nada mais se move. O porém é que as células antes de head ficam desperdiçadas. Um buffer circular (ring buffer) as reaproveita: o array tem um número fixo de células, digamos 8, e as posições dão a volta, então a célula depois da 7 é a 0. Guarde head e size. O próximo enqueue vai para a célula (head + size) mod 8, e um dequeue pega a célula head e passa head para (head + 1) mod 8. As duas operações custam 1 passo. O preço é uma capacidade fixa: quando size chega a 8 a fila está cheia, a menos que você copie tudo para um anel maior, como faria um array dinâmico.

Qual usar? Para uma fila que nunca tem mais que algumas dezenas de valores, push e shift é curto e claro, e a movimentação quase não custa nada. Para uma fila por onde passam milhares de itens, como os quadrados de uma busca em largura grande, um índice head ou um buffer circular mantém cada desenfileiramento em um passo, e a diferença cresce com o comprimento da fila.