Fila JavaScript

Resumo : neste tutorial, você aprenderá sobre a estrutura de dados da fila e como implementar uma fila JavaScript.

Introdução à estrutura de dados da fila

Uma fila é uma lista ordenada de elementos onde um elemento é inserido no final da fila e removido do início da fila.

Uma fila funciona com base no princípio primeiro a entrar, primeiro a sair (FIFO), que é diferente de uma pilha , que funciona com base no princípio último a entrar, primeiro a sair (LIFO).

Uma fila tem duas operações principais:

• Insira um novo elemento no final da fila, que é chamado de enfileiramento.
• Remove um elemento do início da fila, que é chamado de desenfileiramento.

A imagem a seguir ilustra uma fila:

Outra operação importante de uma fila é obter o elemento da frente chamado peek . Diferente da operação de desenfileiramento , a operação peek retorna o elemento na frente sem modificar a fila.

O nome  fila vem da analogia com uma fila de clientes em um banco. O cliente que chegar primeiro será atendido primeiro, e o que chegar depois ficará no final da fila e será atendido posteriormente.

Implementando uma fila JavaScript usando um objeto

Veja a seguir como implementar a estrutura de dados da fila usando um objeto:

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}Linguagem de código:  JavaScript  ( javascript )

Como funciona.

Primeiro, inicialize o objeto que armazena os elementos da fila ( elements) e duas variáveis ​​para rastrear o início e o fim no construtor:

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  //...
}Linguagem de código:  JavaScript  ( javascript )

Segundo, enfileire um elemento adicionando-o ao objeto de elementos no final da fila:

class Queue {
  //...
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }

  //...
}Linguagem de código:  JavaScript  ( javascript )

Terceiro, remova um elemento do início da fila:

class Queue {

  // ...
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }

  //...
}Linguagem de código:  JavaScript  ( javascript )

Quarto, defina o método peek() que acessa o elemento no início da fila:

class Queue {
  //...
  peek() {
    return this.elements[this.head];
  }
  //...  
}Linguagem de código:  JavaScript  ( javascript )

Quinto, obtenha o comprimento da fila:

class Queue {
  //...
  get length() {
    return this.tail - this.head;
  }
  //...
}Linguagem de código:  JavaScript  ( javascript )

A fila está vazia quando o comprimento é zero.

Finalmente, defina o método isEmpty() que retorna true se a fila estiver vazia:

class Queue {
  // ...
  get isEmpty() {
    return this.tail - this.head;
  }
  // ... 
}Linguagem de código:  JavaScript  ( javascript )

Para criar uma nova fila a partir da Queue()função construtora, use a palavra-chave new da seguinte maneira:

let q = new Queue();Linguagem de código:  JavaScript  ( javascript )

Para enfileirar números de 1 a 7, você usa o código a seguir.

for (let i = 1; i <= 7; i++) {
    q.enqueue(i);
}Linguagem de código:  JavaScript  ( javascript )

Para obter o número no início da fila, você usa o peek()método.

console.log(q.peek()); // 1Linguagem de código:  JavaScript  ( javascript )

Para obter o comprimento atual da fila, você usa o length()método como no exemplo a seguir.

console.log(q.length); // 7Linguagem de código:  JavaScript  ( javascript )

Para remover o elemento do início da fila, você usa o dequeue()método a seguir:

// dequeue all elements
while (!q.isEmpty()) {
    console.log(q.dequeue());
}Linguagem de código:  JavaScript  ( javascript )

Junte tudo:

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

let q = new Queue();
for (let i = 1; i <= 7; i++) {
  q.enqueue(i);
}
// get the current item at the front of the queue
console.log(q.peek()); // 1

// get the current length of queue
console.log(q.length); // 7

// dequeue all elements
while (!q.isEmpty) {
  console.log(q.dequeue());
}Linguagem de código:  JavaScript  ( javascript )

Resumo

• Uma fila é uma estrutura de dados que funciona com base no princípio FIFO.