Exemplos detalhados com imagens e textos para implementar filas em JavaScript

Recomendações relacionadas: tutorial de javascript

1. Estrutura de dados da fila

• A fila é um tipo de estrutura de dados "primeiro a entrar, primeiro a sair" (FIFO). O primeiro item enfileirado (entrada) é o primeiro retirado da fila (saída).
• A fila tem 2 ponteiros: cabeça e cauda. O item mais antigo na fila está no início e o item mais recente na fila está no final.
• A fila é como fazer fila no metrô. Os ​​passageiros próximos à porta estão no início da fila e os passageiros que acabaram de entrar na fila estão no final da fila.

De uma perspectiva de alto nível, uma fila é uma estrutura de dados que nos permite processar cada item de dados na ordem em que são armazenados no banco de dados.

2. Operações na fila

A fila suporta 2 operações principais: enfileirar e desenfileirar. Além disso, você pode achar útil executar operações de espiada e comprimento na fila.

• Operação de enfileiramento <br/>A operação de enfileiramento consiste em inserir um item no final da fila, e o item inserido se torna o final da fila.

A operação de enfileiramento na figura acima insere o item 8 no final e 8 se torna o final da fila.

queue.enqueue(8);

• Operação de desenfileiramento <br/> A operação de desenfileiramento consiste em extrair o item no início da fila, e o próximo item na fila se torna o item principal.

Na imagem acima, a operação de desenfileiramento retorna e remove o item 7 da fila. Após desenfileirar, o item 2 se torna o novo item principal.

queue.dequeue(); // => 7

• operação de inspeção <br/> A operação de inspeção lê o início da fila sem alterar a fila.

O item 7 é o início da fila da figura acima, e a operação de inspeção retorna apenas o cabeçalho (item) 7 sem modificar a fila.

queue.peek(); // => 7

• comprimento da fila A operação length calcula quantos itens a fila contém.

Existem 4 itens na fila da imagem: 4, 6, 2 e 7. Como resultado, o comprimento da fila é 4.

queue.length; // => 4

• Complexidade do tempo de operação da fila O importante para todas as operações de fila (enfileirar, desenfileirar, visualizar e comprimento) é que todas essas operações devem ser executadas em tempo fixo O(1).

O tempo constante O(1) significa que não importa o tamanho da fila (pode ter 10 ou 1 milhão de itens): as operações de enfileiramento, desenfileiramento, peek e comprimento devem ser realizadas simultaneamente.

3. Implementando filas em JavaScript

Vejamos uma possível implementação de uma estrutura de dados de fila, mantendo o requisito de que todas as operações devem ser executadas em tempo constante O(1).

classe Fila {
  construtor() {
    isto.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enfileirar(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  desenfileirar() {
    const item = this.items[this.headIndex];
    exclua this.items[this.headIndex];
    this.headIndex++;
    item de devolução;
  }

  espiar() {
    retornar este.items[este.headIndex];
  }

  obter comprimento() {
    retornar this.tailIndex - this.headIndex;
  }
}

fila const = new Queue();

fila.enqueue(7);
fila.enqueue(2);
fila.enqueue(6);
fila.enqueue(4);

fila.dequeue(); // => 7

fila.peek(); // => 2

queue.length; // => 3

const queue = new Queue() é como criar uma instância de uma fila.

Chame o método queue.enqueue(7) para colocar o item 7 na fila.

queue.dequeue() remove um item principal da fila, enquanto queue.peek() apenas espia desde o início.

Finalmente, queue.length mostra quantos itens restam na fila.

Quanto à implementação: Dentro da classe Queue, o objeto simples this.items contém os itens da fila por índice numérico. O índice do item principal é rastreado por this.headIndex, e o índice do item final é rastreado por this.tailIndex.

• Complexidade dos métodos de fila

Os métodos queue(), dequeue(), peek() e length() da classe Queue usam apenas:

acesso a atributos (como this.items[this.headIndex]),

ou realizar operações aritméticas (como this.headIndex++).

Portanto, a complexidade de tempo desses métodos é de tempo constante O(1).

4. Resumo

A estrutura de dados da fila é um tipo de "primeiro a entrar, primeiro a sair" (FIFO): o primeiro item a ser enfileirado é o primeiro item a ser retirado da fila.

As filas têm 2 operações principais: enfileirar e desenfileirar. Além disso, as filas podem ter operações auxiliares, como visualização e comprimento.

Todas as operações de fila devem realizar O(1) em tempo constante.

Recomendações relacionadas: Tutorial de aprendizagem de JavaScript

acima é uma explicação detalhada da implementação de filas em JavaScript com exemplos e imagens. Para obter mais informações, preste atenção a outros artigos relacionados no site PHP chinês!