Estrutura de dados: Pilhas

O artigo de hoje traz um pouco sobre o que li do livro: Estruturas de Dados e Algoritmos com JavaScript.

Estou na minha primeira estrutura de dados “Pilhas” e confesso que a leitura está sendo boa. O livro é bem legal e os exemplos do final deste capitulos que me inspiraram a escrever este artigo sobre o assunto.

Se o termo “pilhas” ou “estrutura de dados” parece algo novo para você, deixe-me tentar explica-lo. As estruturas de dados são os pilares que constroem a base sólida sobre o entendimento de algoritmos. Imagine o termo estrutura de dados associados a um grupo de estratégias que podemos formar com os dados que temos.

Pois dependendo de como organizamos os nossos dados, tais organizaçaões podem seguir uma lógica para fins de resolver um problema específico. E no caso das pilhas, ela não passa de uma estratégia bem definida que usa um conjunto de dados e o administra para resolver certos objetivos.

Vamos supor que precisamos resolver um simples problema que deve segiuir a riscas tais regras:

1. Você precisa montar uma pilha de livros
2. Você deve pensar bem na ordem que deseja colocar. Pois para pegar o último livro da pilha, você vai ter que desenpilhar todos os outros livros.
3. Desta forma não é possível colocar um livro na ordem que quiser. Todo livro cai sempre no topo da pilha.
4. Para remover um livro da pilha, você só consegue remover o livro que estiver no topo.
5. Então se a pilha tiver dez livros e você precisar do último, vai ter que desempilhar os outros nove primeiro.

Observou que existem uma série de regras a serem seguidas para se resolver o problema? A solução que encontrarmos para resolver o problema é o que chamamos de algoritmo! E uma vez que este algoritimo consiga resolver bem o problema, podemos nomear este algoritmo para saber que sempre que tivermos um problema parecido com este, basta usar o algortimo já conhecido.

Como nosso problema envolve o uso de pilhas de livros, nada mais evidente do que usarmos um algoritmo que busque resolver o problema de empilhamento de itens.

O que é uma pilha?

Observem as duas imagens abaixo que fazem parte da minha pilha pessoal de livros sobre a área de tecnologia.

const book_stack = [
    'b1','b2','b3','b4','b5','b6','b7','b8','b9','b10','b11','b12'
];

Observe a semelhança da estrutura de dados dos livros, no sentido de enumeração caso fossemos indexa-los com o nosso array de exemplo chamado book_stack. Apesar de book_stack não ser uma pilha, eu usei ele de exemplo para você poder fazer o comparativo de que em ambas as estruturas. Todos os itens precisam de um índice para que possa representar a posição dele dentro de uma estrutura. No caso de book_stack, se trata de uma estrutura de array que já foi discutida aqui no blog. Já na imagem dos livros estamos falando de um outra estrutura que é a pilha.

Mas… o que é uma pilha?

Uma pilha nada mais é do que um conjunto de elementos empilhados uns sobre os outros. É algo super simples e óbvio conforme você pode perceber no mundo real. Já dentro das estruturas de software, uma pilha é toda estrutura onde a inserção e a remoção dos dos dados seja dada somente pelo topo, sempre que uma estrutura de dados se enquadrar neste perfil, podemos chama-la de pilha. Basta obsevar o mundo real, e entender que em qualquer estrutura de pilha, sempre será muito mais fácil e eficiente, remover os elementos do topo até que chegue no elemento que deseja pegar.

E em computação, haverá situações em que a estrutura dos dados vão precisar se comportar desta forma e por conta disso, você vai usar este algoritmo.

Entendi… Mas como posso programar isso?

Tudo que você precisa fazer é criar uma estrutura de dados e definir uma forma de operar nesta estrutura. A forma como você vai operar nesta estrutura é o que eu vou chamar aqui neste artigo de “regras”. Pois estas regras poderiam ser de inúmeras maneiras. Porém, como estamos tentando criar uma estrutura de pilha. Devemos apenas definir regras que reflitam o comportamento de uma pilha no mundo real.

Vamos pensar juntos!

Assumindo que no mundo real, nós tenhamos uma pilha de livros como na imagem abaixo:

Me diga se você seria capaz de remover o último livro desta pilha apenas tendo de pegar um livro por vez? Seria difícil né? isso para não dizer impossível!

Então se eu fosse programar uma representação de como eu poderia estar removendo cada livro desta caixa até conseguir tirar o último. Primeiro eu vou precisar definir uma representação dessa pilha de livros.

Uma representação válida seria o código mostrado anteriormente:

const book_stack = ['b1','b2','b3','b4'];

Onde vou apenas fingir que nesta caixa tenham apenas 4 livros.

Então, da mesma forma como existem diversas funções nativas do javascript para se manipular um array, neste contexto de pilhas, você vai precisar criar métodos que sejam capazes de executar operações nesta pilha. Entre estas operações podemos dizer que temos disponível:

1. Inserção na caixa (push): Seria o ato de inserir um novo livro nesta caixa.
2. Remoção (pop): Seria o ato de retirar o primeiro livro da pilha de livros na caixa. (somente o primeiro livro!)
3. Observação (peek): Seria o equivalente a você abrir a caixa e apenas observar qual é o livro que está no topo da caixa.
4. Verificar se está vazio (isEmpty): Seria o equivalente a você abrir a caixa para saber e existe algum livro na caixa ou se ela stá vazia. É apenas uma verificação.
5. Limpar (clear): Seria o equivalente a você remover todos os livros da caixa de uma só vez.
6. Tamanho da pilha (size): Seria o equivalente a você conseguir contar quantos livros existem dentro da caixa.

Lembrando que entre estas operações, as primeira são fáceis de entender se você for compara-las a uma ação no mundo real. É fácil de imaginar que numa cai grande cheia de livros, eu provavelmente só vou começar a retirar um livro por vez, sendo que só vai dar para retirar os livros do topo.

Da mesma forma se eu fosse inserir um novo livro. Eu jamais conseguiria inseri um livro no meio de uma pilha que está dentro de uma caixa sem antes ter de desempilhar alguns livros.

Então para programar isso, você primeiramente precisa definir algumas funções. Tais funções podem ter um nome a sua escolha, mas vamos seguir os nomes mais convencionais conforme eu listei entre parenteses na listagem acima.

Criando um script de exemplo

Vamos criar algumas funções de exemplo em javascript, apenas para ilustrar isso. Lembre-se que o foco principal deste artigo é fazer você entender o conceito por trás da ideia deste algoritimo que não é nada mais do que representar o comportamento de uma pilha via programação.

Então, se na listagem acima eu descrevi as principais ações que podem ser feitas no mundo real sobre uma pilha de livros. A implementação disso, nada mais é do que a versão em código destas ações.

Tudo que será explicado em código a seguir, não passa de um exemplo de uma implementação real sobre o conceito de pilhas.

Primeiro, antes de tudo, vamos representar a nossa pilha através de uma estrutura de array para simplificar as coisas. Num contexto mais amplo, poderíamos representar a pilha através de um objeto. Mas vamos deixar as coisas mais simples e fazer isso com um array que vai simular uma pilha.

// Declaração do array book_stack que simula uma pilha de livros 
const book_stack = ['b1', 'b2', 'b3', 'b4'];

// Função para verificar se a pilha está vazia 
function isEmpty(stack) {
	return stack.length === 0;
}

// Função para adicionar um elemento ao topo da pilha
function push(stack, element) {
	stack.push(element);
}

// Função para remover e retornar o elemento do topo da pilha
function pop(stack) {
	if (!isEmpty(stack)) {
		return stack.pop();
	} else {
		console.log('A pilha está vazia.');
		return null;
	}
}

// Função para obter o elemento do topo da pilha sem removê-lo
function peek(stack) {
	if (!isEmpty(stack)) {
		return stack[stack.length - 1];
	} else {
		console.log('A pilha está vazia.');
		return null;
	}
}

// Função para limpar a pilha
function clear(stack) {
	stack.length = 0;
}

// Função para obter o tamanho da pilha
function size(stack) {
	return stack.length;
}

Finalizando

Este trecho de código é apenas um exemplo de uma implementação de uma pilha. Na declaração do array book_stack nós tentamos simular esta estrutura de dados como se ela fosse uma pilha. Mas na verdade uma melhor maneira de representar esta estrutura seria através de um objeto pilha. Mas isso vamos deixar para outro artigo focado neste exemplo. Se atente mais ao conceito.

Além disso, se você for um iniciante em programação, eu acredito que nesta fase, tentar entender a implementação seria muito complicado a principio por conta de ficar bem abstrato o propósito desta implementação. A minha dica é que você estude os comandos básicos de programação e quando estiver bem familiarizado com ele e também estiver com o conceito de pilha bem fresco em sua memória. Aí sim, vai valer a pena, tentar implementar este algoritimo e também pesquisar mais a fundo sobre os exemplos de código. Mas por enquanto, caso você seja um iniciante, se atente somente ao conceito deste algoritimo.

Bem galera, vou finalizar por aqui e até o próximo artigo.