Queue (Filas) em JavaScript

NOTA: os conceitos aqui mostrados são válidos em qualquer linguagem de programação.

Queue é um tipo de estrutura de dados abstracto que segue a regra FIFO (First In, First Out) em português Primeiro Dentro, Primeiro Fora, filas são muito usadas na computação.

Queues fazem parte das estruturas de dados lineares juntamente com: Array, Linked List, Stacks

Existem vários tipos de filas, dentre as quais, as duas mais usadas são:

• Linear
• Circular

Neste artigo, focaremo-nos simplesmente na fila linear.

Fila Linear

Numa fila linear, a adição de novos elementos é sempre feita no final da mesma e os primeiros da fila serão os primeiros a serem "atendidos".

Ao usarmos uma impressora por exemplo, ela faz uma lista de páginas à serem imprimidas, em seguida estas páginas são colocadas numa fila onde a impressão é feita por ordem de chegada.

Propriedades de uma Queue:

• Size: corresponde ao tamanho da fila, este valor é estáticamente definido na criação da mesma
• Head: corresponde ao índice do primeiro elemento da fila
• Tail: corresponde ao índice do último elemento da fila

Métodos de uma Queue:

• Enqueue: método para adicionar elementos na fila
• Dequeue: método para remover elementos da fila
• Peek: método para mostrar o primeiro elemento da fila
• IsEmpty: método que informa se a fila está vazia
• IsFull: método que informa se a fila está cheia
• DeleteQueue: método para apagar uma fila

Implementado uma fila

Existem duas opções para a implementação de uma fila.

• Usando um Array
• Usando uma Linked List

Neste artigo veremos simplesmente a implementação via Array.

Criando uma fila

Criaremos uma fila que poderá apenas ter conter 6 elementos e nela iremos armazenar as seis primeiras letras do alfabeto

Adicionando elementos na fila

Como foi dito acima, a adição de novos elementos na fila é sempre feito no final da mesma(no primeiro espaço livre encontrado).

Removendo elementos da fila

A remoção de elementos na fila é sempre feito à partir do primeiro elemento na mesma.

Implementando uma fila em JavaScript

Criação da fila

class Fila {
  constructor(size /*tamanho*/) {
    this.queue = new Array(size);
    this.size = size; // tamanho da fila
    this.head = 0; // começo
    this.tail = 0; // final
  }
}

const fila = new Fila(6);

No código acima, podemos ver como é feita a criação de uma fila usando uma class do JavaScript e a instanciação da mesma. Usaremos a varíavel fila para referências posteriores.

Verificando se a fila está completa

class Fila {
  // ... código anterior ocultado aqui
  isFull() {
    return this.size === this.tail;
  }
}

Visto que a varíavel tail indica o índice do último elemento da fila, podemos então deduzir que a fila está completa caso o seu valor seja igual ao do tamanho inicial da fila. Esta operação retorna um booleano.

Verificando se a fila está vazia

class Fila {
  // ... código anterior ocultado aqui
  isEmpty() {
    return this.head === this.tail;
  }
}

Visto que a varíavel tail indica o índice do último elemento da fila, podemos então deduzir que a fila está vazia caso o seu valor seja igual ao do primeiro elemento da fila. Esta operação retorna um booleano.

Mostrando o primeiro elemento da fila

class Fila {
  // ... códigos anteriores ocultados aqui
  peek() {
    return this.queue[this.head];
  }
}

Uma vez que a varíavel tail indica o índice do primeiro elemento da fila, isto quer dizer que podemos usar a mesma para nos retornar o elemento.

Adicionando novos elementos à fila

class Fila {
  // ... códigos anteriores ocultados aqui
  enqueue(elemento) {
    if (this.isFull()) {
      return "Infelizmente a fila está completa";
    } else {
      this.queue[this.tail] = elemento;
      this.tail++;
      return `O valor ${elemento} foi adicionado à fila`;
    }
  }
}

Vamos lá analisar o código acima escrito.

Ao adicionarmos novos elementos à fila, a primeira coisa à fazer é saber se a mesma está cheia, caso esteja, a adição de novos elementos não será efectuada e informaremos o utilizador. Caso ainda haja espaço na fila, podemos então efectuar a adição e informar o utilizador.

À cada vez que adicionamos um novo elemento à fila, incrementamos o valor de tail para indicar o novo indíce de onde encontra-se o último elemento da fila.

Adicionemos as seis primeiras letras do alfabeto

fila.enqueue("A");
fila.enqueue("B");
fila.enqueue("C");
fila.enqueue("D");
fila.enqueue("E");
fila.enqueue("F");

// para cada valor adicionado, teremos a seguinte
// mensagem "O valor ${valor} foi adicionado à fila"

Imprimindo o valor do primeiro elemento da fila.

fila.peek(); // A

Removendo elementos da fila

Este é o estado actual da nossa fila.

Queremos remover os dois primeiros elementos da fila.

Para efectuarmos a remoção devemos em primeiro lugar, verificar se existem elementos na lista. Caso existam, procedemos com a acção, caso contrário, informamos o utilizador dizendo que a lista está vazia.

class Fila {
  // ... códigos anteriores ocultados aqui
  dequeue() {
    if (this.isEmpty()) {
      return "Esta fila não contém elementos";
    } else {
      this.head++;
      return this.queue.shift();
    }
  }
}

// invocando a função de remoção
fila.dequeue();
fila.dequeue();

Analisemos o código acima. Como não tivéramos efectuado nenhuma remoção antes da primeira invocação da função dequeue(), a varíavel head aponta actualmente para a posição 0, então, apagaremos o elemento que se encontra nesta posição. Após esta operação, o primeiro espaço da nossa fila ficará vazío pois acabamos de remover a letra A na nossa lista, neste caso teremos de incrementar a varíavel head para apontar para a letra B, o valor de head agora é 1, repetimos a mesma lógica sucessivamente.