Estrutura de dados Fila

Uma Fila é uma coleção ordenada de itens baseada em FIFO (First In First Out),

isto é, o primeiro que entra é o primeiro a sair, também conhecido como princípio do

first-come first-served (o primeiro a chegar é o primeiro a ser servido)

A adição de novos elementos em uma fila é feita na cauda (tail) e a remoção, na frente

O elemento mais recente adicionado a fila deve esperar no final dela

Criando a classe Queue

Criaremos agora a nossa própria classe para representar uma fila

Vamos começar pelo básico e declarar a nossa classe:

class Queue() {
  constructor() {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }
}

Inicialmente, precisamos ter uma estrutura de dados que armazenará os elementos da fila,

podemos usar um array para isso

No entanto, vamos usar um objeto para armazenar nossos elementos, isso nos permitirá escrever uma estrutura de dados mais eficiente para acessar seus elementos

Caso você tenha visto o post sobre como implementar uma Stack em Javascript

irá notar certa semelhança entre as classes Stack e Queue somente os princípios para adição e remoção de elementos que são diferentes

Para nos ajudar a controlar o tamanho da fila, declaramos uma propriedade count também

E, como removeremos os elementos da frente da fila, também precisamos de uma variável para nos ajudar a manter o controle do primeiro elemento, para isso declaramos a variável lowestCount

Em seguida, vamos implementar os métodos que vão ser utilizados na nossa classe Queue

• enqueue(element): esse método adiciona um novo elemento no final da fila

• dequeue(): esse método remove o primeiro elemento da fila (o item que está na frente) e também devolve o elemento removido

• peek(): esse método devolve o primeiro elemento da fila, é o primeiro item adicionado e o primeiro que será removido da fila, A fila não é modificada (o elemento não é removido, mas será devolvido apenas como informação)

• isEmpty(): esse método devolve true se a fila não contiver nenhum elemento, e false se o tamanho for maior que 0

• size(): esse método devolve o número de elementos contidos na fila. É semelhante à propriedade length do array

Inserção de elementos na fila

O primeiro método que vamos implementar é o método enqueue

Esse método será responsável pela adição de novos elementos na fila, com um detalhe muito importante: só podemos adicionar novos itens no final da fila

enqueue(element) {
  this.items[this.count] = element
  this.count++
}

O método enqueue tem a mesma implementação que o método push da classe Stack que você pode ver nesse post

Como a propriedade items é um objeto Javascript, ela é uma coleção de pares chave e valor

Para adicionar um elemento à fila, usaremos a variável count como chave do objeto items,

e element será o seu valor

Depois de inserir o elemento na fila, incrementaremos count

Remoção de elementos da fila

Vamos agora implementar o método dequeue, responsável pela remoção de itens da fila

Como a fila utiliza o princípio FIFO, o primeiro item adicionado na fila será o item a ser removido

dequeue() {
  if (this.isEmpty()) {
    return undefined
  }
  const result = this.items[this.lowestCount]
  delete this.items[this.lowestCount]
  this.lowestCount++
  return result
}

Inicialmente devemos verificar se a fila está vazia e, em caso afirmativo, devolveremos o valor undefined

Se a fila não estiver vazia, armazenaremos o valor da frente da fila para que possamos devolvê-lo depois que o elemento tiver sido removido

Também precisamos incrementar a propriedade lowestCount de 1

Vamos usar os valores internos a seguir para emular a ação de remoção da fila:

items = {
  0: 5,
  1: 8
}

Para acessar o elemento da frente da fila (o primeiro elemento adicionado: 5), precisamos acessar a chave com valor 0

Podemos acessar items[0], apagá-lo e devolver o seu valor

Neste cenário, depois de remover o primeiro elemento, a propriedade items conterá somento um elemento (1: 8), que será o próximo a ser removido se o método dequeue for chamado

Assim, incrementamos a variável lowestCount de 0 para 1

Como os métodos enqueue e dequeue são os únicos métodos disponíveis para adição e remoção de itens na fila, garantimos que o princípio FIFO será aplicado em nossa classe Queue

Dando uma espiada no elemento que está na frente da fila

Vamos agora implementar alguns métodos auxiliares adicionais em nossa classe Queue

Se quisermos saber qual é o elemento que está na frente em nossa fila, podemos usar o método peek

Esse método devolverá o item que está na frente da fila usando lowestCount como chave para obter o valor do elemento

peek() {
  if (this.isEmpty()) {
    return undefined
  }
  return this.items[this.lowestCount]
}

Verificando se a fila está vazia e o seu tamanho

O próximo método é isEmpty, que devolverá true se a fila estiver vazia, e false caso contrário

isEmpty() {
  return this.count - this.lowestCount === 0
}

Para calcular quantos elementos há na fila, basta calcular a diferença entre as chaves count e lowestCount

Suponha que a propriedade count tenha o valor 2 e lowestCount seja igual a 0

Isso significa que temos dois elementos na fila. Em seguida, removemos um elemento dela

A propriedade lowestCount será atualizada com o valor 1 e count continuará com o valor igual a 2

Agora a fila terá somente um elemento, e assim por diante

Assim, para implementar o método size, basta devolver esta diferença

size() {
  return this.count - this.lowestCount
}

Também podemos escrever o método isEmpty assim:

isEmpty() {
  return this.size() === 0
}

Limpando a fila

Para limpar todos os elementos da fila, podemos chamar o método dequeue até que ele devolva undefined, ou podemos simplesmente reiniciar o valor das propriedades da classe Queue com os memos valores declarados no seu construtor

clear() {
  this.count = 0
  this.items = {}
  this.lowestCount = 0
}

Criando o método toString

Assim como fizemos na implementação da estrutura de dados Pilha, que você pode ver nesse post

também podemos acrescentar o método toString

toString() {
  if (this.isEmpty()) {
    return undefined
  }
  let objString = `${this.items[this.lowestCount]}`
  for (let i = this.lowestCount + 1; i < this.count; i++) {
    objString = `${objString},${this.items[i]}`
  }
  return objString
}

Na classe Stack que foi implementada no post que mencionei, começamos a iterar pelos valores dos itens a partir do índice zero

Como o primeiro índice da classe Queue pode não ser zero, começamos iterando a partir do índice lowestCount

As estruturas de dados Queue e Stack (Fila e Pilha) são muito parecidos

A única diferença está nos métodos dequeue e peek, que se deve à distinção entre os princípios LIFO e FIFO