Introdução
As filas são uma estrutura de dados que organiza elementos em uma ordem específica, seguindo a abordagem “primeiro a entrar, primeiro a sair” (FIFO – First-In-First-Out). Funciona da mesma forma que uma fila de pessoas, onde a pessoa que chega primeiro é atendida primeiro e sai da fila.
Na vida real, temos vários exemplos de filas, como, fila do caixa eletrônico, fila do supermercado, etc.
Na computação, é possível ter uma fila de mensagens, como, por exemplo, para o envio de e-mails, onde adicionamos vários e-mails ao final da fila e enviamos e removemos o primeiro e-mail que chegou.
Criando a classe Queue (Fila)
Antes de tudo, é necessário criar uma estrutura de dados primitiva para armazenar os elementos da fila. De forma semelhante ao que fizemos no exemplo de pilhas (stacks). Você pode baixar o código desse artigo clicando aqui!
Porém, aqui usaremos um objeto nossa estrutura de dados para armazenar os elementos da fila.
Os métodos que nossa classe deverá conter são:
- enqueue: esse método adicionará um elemento ao final da fila.
- dequeue: esse método removerá o elemento que estiver no início da fila.
- peek: o método retornará o primeiro elemento da fila, em outras palavras, o elemento presente na primeira posição.
- isEmpty: esse método verifica se a fila está vazia.
- size: esse método devolve o tamanho da fila.
Cirando a classe Queue (Fila)
export class Queue {
readonly _items: object
private _count: number
private _firstElement: number
constructor(items: object = {}) {
this._items = items
this._count = 0
this._firstElement = 0
}
enqueue(item: any) {
this._items[this._count] = item
this._count++
}
dequeue() {
if(this.isEmpty()) return
const result = this._firstElement[this._firstElement]
delete this._items[this._firstElement]
this._firstElement++
return result
}
peek() {
if(this.isEmpty()) return
return this._items[this._firstElement]
}
isEmpty() {
return this._count - this._firstElement === 0
}
size() {
return this._count - this._firstElement
}
}Podemos perceber que implementar uma fila não é tão difícil, na verdade, é bem simples depois que você entende o conceito básico do funcionamento de uma fila.
Usando a classe Queue (Fila)
Primeiramente, precisamos instanciar a classe Queue, e logo em seguida, podemos começar a chamar os métodos que definimos anteriormente.
Verificando se a fila está vazia:
Vamos adicionando 4 elementos a fila e visualizá-los:
Podemos ver que adicionamos os itens na ordem correta (ao final da fila), mas agora vamos verificar se o método dequeue está funcionando corretamente.
Removendo itens da fila:
Agora, podemos perceber que somente 2 elementos estão na fila.
Espiando o início da fila e verificando o tamanho da fila:
Como esperado, temos o e-mail bia@zmail.com como senod o primeiro elemento da fila, já que iniciamos com 4 elementos e removemos dois durante nossos testes.
Para facilitar ainda mais o entendimento, o diagrama a seguir representa as operações de enfileiramento e desenfileiramento feitas na fila:
Conclusão
Neste artigo, entendemos em detalhes como a estrutura de dados fila (queue) funciona, e se você chegou até aqui, tenho certeza que será capaz de implementar sua versão.
Fique a vontade para fazer modificações e melhorias. Obrigado por chegar até aqui, um abraço e até a próxima. 👾
Saiba mais
Estrutura de dados pilha – stack
