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()); // 1
Linguagem 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); // 7
Linguagem 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.