[download id=”589″]
Neste artigo estarei explicando o funcionamento das estruturas de dados conhecidas como Pilha e Fila. O código fonte JavaScript será deixado disponível e uma breve explicação junto com o uso serão dados para cada uma delas.
Pilha
Conceito Básico
A pilha é uma estrutura de dados básica que fornece a lógica conhecida por LIFO(Last In, First out). Isso significa que o ultimo dado adicionado a estrutura será o primeiro removido dela e por isso foca a entrada e saída de dados na mesma ponta do vetor/lista.
Na prática, a pilha como um controle para serviços que dependem da conclusão do ultimo recurso ativado antes de prosseguirem. Exemplos de rotinas que utilizam essa lógica são o “desfazer” do Word e o gerenciamento da execução de funções (de programação), que causa o conhecido erro de stackoverflow.
Código Fonte
O código fonte abaixo não vai usar o vetor do JavaScript simplesmente para podermos ver em mais detalhes o funcionamento desta estrutura de dados. não será uitlizado um vetor, mas sim nós (nodes) que se conectam uns aos outros.
function Pilha() {
var topo = null;
var quantidade = 0;
//Retorna o número de itens na Pilha
this.GetCount = function () {
return quantidade;
}
//Push: Adiciona itens ao topo da pilha
this.Push = function (dados) {
var node = {
dados: dados,
proximo: null
};
node.proximo = topo;
topo = node;
quantidade++;
}
//Pop: Remove itens do topo da pilha
this.Pop = function () {
if (topo === null) {
return null;
} else {
var removido = topo;
topo = topo.proximo;
if (quantidade > 0) {
quantidade--;
}
return removido.dados;
}
}
//Exibe o Item do topo da pilha
this.VerTopo = function () {
if (topo === null) {
return null;
} else {
return topo.dados;
}
}
//Retorna um vetor com todos iitens da Pilha
this.VerTodos = function () {
if (topo === null) {
return null;
} else {
var arr = new Array();
var current = topo;
for (var i = 0; i < quantidade; i++) {
arr[i] = current.dados;
current = current.proximo;
}
return arr;
}
}
}
Fila
Conceito Básico
Fila é um tipo de estrutura de dados com um controle definido pela lógica FIFO (do inglês first in, last out). Esse controle quer dizer que os dados contidos nela são podem entrar apenas por uma ponta e deverão sair pela outra. Com isso, garante-se que o primeiro dado que entrou será o primeiro a sair da fila.
A fila é uma estrutura de dados muito útil quando se possui um serviço ao qual o sistema recebe alimentação de diversas fontes, mas precisa manter uma ordem do “primeiro que chegou será o primeiro servido”. Um exemplo simples é o sistema que administra diversos computadores ligados a uma única impressora.
Código Fonte
O código fonte abaixo não vai usar o vetor do JavaScript simplesmente para podermos ver em mais detalhes o funcionamento desta estrutura de dados. Não será utilizado um vetor como forma de controle mas sim nós contectados uns aos outros, irei também fazer com que o ato de adicionar o faça no começo da fila e o de remover será na outra ponta.
function Fila() {
var quantidade = 0;
var primeiro = null;
var ultimo = null;
//Retorna a quantidade na fila
this.GetQuantidade = function () {
return quantidade;
}
//adiciona um item a fila
this.Adicionar = function (data) {
var node = {
data: data,
prox: primeiro
};
if (primeiro === null) {
ultimo = node;
}
primeiro = node;
quantidade++;
}
//Remove um item da fila
this.Remover = function () {
//se a fila estiver vaiza, retorna nulo
if (ultimo === null) {
return null;
}
else {
//senão percorre a fila até o ultimo item para removelo e ajusta a lista
var current = primeiro;
var previous = null;
while (current.prox) {
previous = current;
current = current.prox;
}
if (quantidade > 1) {
previous.prox = null;
ultimo = previous;
}
//zera/reseta a fila
else {
primeiro = null;
ultimo = null;
}
quantidade--;
}
//Exibe todos os itens da fila
this.ExibirTodos = function () {
if (primeiro === null) {
return null;
} else {
var arr = new Array();
var current = primeiro;
for (var i = 0; i < quantidade; i++) {
arr[i] = current.data;
current = current.prox;
}
return arr;
}
}
}
}
