Implementando as estruturas FIFO e LIFO em Javascript

Veja neste artigo como desenvolver classes para a implementação das estruturas de dados FIFO (First-In, First-Out) e LIFO (First-In, Last-Out) na linguagem Javascript.

por Joel Rodrigues

Introdução

As estruturas de dados FIFO e LIFO são duas das mais comumente utilizadas na computação devido à funcionalidade que implementam. A compreensão desses modelos torna-se bastante simples quando são feitas alusões a situações reais do cotidiano, como veremos a seguir.

Neste artigo apresentarei uma solução simples e de fácil para o desenvolvimento de classes em Javascript que implementem esses conceitos. As classes se chamarão Queue (fila em inglês) e Stack (pilha em inglês), pois na maioria das linguagens que as implementam, elas são chamadas assim.

Porém, antes de prosseguirmos é preciso compreender o funcionamento dessas estruturas.

Pilha

A pilha implementa o conceito de FILO (First-In, Last-Out) ou “Primeiro a Entrar, Último a Sair”. O último elemento a ser inserido na pilha é o primeiro a ser removido, enquanto o primeiro a ser inserido é o último que sai.

Imagine que você deve organizar vários livros que encontram-se espalhados para depois distribuí-los ordenadamente. Primeiramente você juntará todos os livros em uma pilha, um sobre o outro, como mostra a Figura 1.

Figura 1: Ilustração da inserção de itens na pilha

Feito isso, você passará a distribuí-los um a um. O primeiro livro a ser removido da pilha para ser entregue é aquele que se encontra no topo, ou seja, o último que foi inserido. A figura a seguir ilustra esse processo, inverso ao anterior.

Figura 2: Ilustração do processo de remoção de itens da pilha

A nossa classe Stack possuirá apenas três métodos:

• Inserir(obj): insere o elemento recebido como parâmetro no final da lista.
• RemoverUltimo(): retorna o valor do último elemento inserido e o remove da lista. Este método é o mais utilizado nesse contexto, o próximo (LerUltimo) foi criado apenas como auxiliar.
• LerUltimo(): retorna o valor do último elemento inserido, o do topo da pilha.

Vamos então ao código da classe Stack.

Listagem 1: Classe Stack

function Stack(){
	this.lista = new Array();

	this.Inserir = function(obj){
		this.lista[this.lista.length] = obj;		
	}

	this.RemoverUltimo = function(){
		if(this.lista.length > 0){
			var obj = this.lista[this.lista.length - 1];
			this.lista.splice(this.lista.length - 1,1);
			return obj;		
		}else{
			alert("Não há objetos na pilha.")
		}
	}

	this.LerUltimo = function(){
		if(this.lista.length > 0){
			return this.lista[this.lista.length - 1];
		}else{
			alert("Não há objetos na pilha.")
		}
	}	
}

Apesar de Javascript não ser uma linguagem orientada a objetos, ela é bastante flexível com relação aos tipos de dados. Podemos utilizar o conceito de classes trabalhando apenas com funções, como se vê acima.

A lista em si é mantida em um vetor e os métodos basicamente inserem e removem elementos nele, considerando as regras de funcionamento citadas.

Fila

A fila, ou queue como também é conhecida é uma estrutura de dados que implementa o conceito de FIFO (First-In, First-Out) ou “Primeiro a Entrar, Primeiro a Sair”.

Essa situação é semelhante, por exemplo a uma fila de supermercado ou banco, onde o primeiro usuário a entrar na fila é também o primeiro a ser atendido e sair dela. Nesse caso, ilustrações são dispensadas pois trata-se de um conceito ainda mais simples que o anterior.

Nesta estrutura temos dois métodos principais, um para inserir um item na fila e outro para ler e remover o primeiro elemento. Vale salientar que este segundo método sempre retornará o elemento de índice zero, ou seja, o primeiro.

De forma complementar, a classe que será apresentada aqui terá um método a mais, que permitirá a leitura do primeiro elemento sem que este seja removido da coleção. Em suma, os métodos são os seguintes:

• Inserir(obj): insere um item no final da fila.
• RemoverPrimeiro: retorna o valor do primeiro elemento da fila, o de índice zero, e o remove.
• LerPrimeiro: retorna o valor do primeiro elemento da lista, mas sem que este seja removido.

Abaixo segue a implementação da classe Queue.

Listagem 2: Classe Queue

function Queue(){
	this.lista = new Array();

	this.Inserir = function(obj){
		this.lista[this.lista.length] = obj;
	}

	this.RemoverPrimeiro = function(){
		if(this.lista.length > 0){
			var obj = this.lista[0];
			this.lista.splice(0,1);
			return obj;		
		}else{
			alert("Não há objetos na fila.")
		}
	}

	this.LerPrimeiro = function(){
		if(this.lista.length > 0){
			return this.lista[0];
		}else{
			alert("Não há objetos na fila.")
		}
	}
}

Como se vê, o código é bastante semelhante ao da classe Stack, mudando apenas a lógica de funcionamento.

Testando as classes

Vamos então realizar alguns testes com as classes criadas, para demonstrar o funcionamento delas na prática. Nos exemplos abaixo, as classes foram salvas nos arquivos Stack.js e Queue.js, mantidos no mesmo diretório do arquivo HTML apresentado a seguir.

Listagem 3: Testando a clase Stack

<html>
<head>	
	<script type="text/javascript" src="Stack.js"></script>
	<script type="text/javascript"/>
		var pilha = new Stack();

		pilha.Inserir(1);
		pilha.Inserir(2);
		pilha.Inserir(3);

		var item = pilha.RemoverUltimo();
		alert(item);
	</script>
</head>
<body>
	<h1 id="txt"></h1>
</body>
</html>

Inicialmente inserimos três elementos de valores 1, 2 e 3 na pilha. Em seguida obtemos o valor do elemento do topo através do método RemoverUltimo e o exibimos em uma caixa de mensagem. O valor exibido é, como esperado, “3”.

Figura 3: Resultado do uso da classe Stack

Se chamássemos novamente esse método, o resultado seria “2”, pois esse é o próximo elemento no topo, após a remoção do “3”.

A próxima listagem mostra um exemplo semelhante, mas utilizando a classe Queue.

Listagem 4: Exemplo de uso da classe Queue

Nesse caso o valor exibido é “1”, por ser esse o primeiro elemento da fila.

Figura 4: Resultado do uso da classe Queue

Conclusão

Como já foi dito, a fila e pilha são duas das estruturas de dados mais comuns na informática e, por tanto, é importante conhecer seu funcionamento. Este artigo teve o objetivo de apresentar, além das definições teóricas de FIFO e LIFO, implementações práticas e de simples compreensão utilizando a linguagem Javascript.

Espero que tenham gostado. Até o próximo artigo.

Clique aqui para conhecer como trabalhar com FIFO e LIFO em .NET