PortfólioAlgoritmos e Estrutura de Dados: Pilhas
Algoritmos e Estrutura de dados é de longe a disciplina mais importante em ciência da computação, pois encontrar o algoritmo ideal para solucionar um problema, forma a base do desenvolvimento de software e da ciência da computação.
As estruturas de dados, como o proprio nome já indica, nos ajuda a estruturar os dados para que possam ser manipulados de uma forma mais eficiente dependendo do caso de uso, gerando assim uma abstração muito util.
Este será o primeiro artigo de uma sequência de artigos que pretendo publicar sobre este tema, explicando em detalhes o funcionamento de cada algoritmo e estrutura de dados, com exemplos em JavaScript e imagens que facilitam a compreensão do seu funcionamento, além dos seus casos de uso no dia a dia do desenvolvimento de software.
Como funciona uma pilha?
Pense na organização de livros em uma pilha, você vai colocando cada livro sobre o outro, empilhando esses livros, e o primeiro livro que você colocou ficou no final da pilha, ou seja, embaixo de todos outros livros. Agora para desfazer essa pilha, intuitivamente você pensa em tirar primeiro os livros que estão no topo da pilha até não haver mais livros.
Esse também é o funcionamento da estrutura de dados Pilha (ou “Stack”), essa estrutura usa o principio LIFO (last-in first-out), onde o ultimo elemento a ser inserido é o primeiro a ser retirado. Desta forma, uma pilha permite o acesso a um elemento por vez, e sempre é o ultimo a ser inserido na pilha, ou seja, o elemento que está no topo da pilha.
Você pode estar se perguntando: qual é a utilidade disso? Por exemplo, quando você esta escrevendo um texto ou usando algum programa que tem uma opção de desfazer, as suas modificações estão sendo guardadas em uma estrutura de pilha, permitindo então que você desfaça e refaça ações.
Funções recursivas em compiladores também usam pilhas, o Node JS e o seu event loop também fazem uso extensivo de pilhas para controlar o que deve ser executado. Também podemos citar a navegação em paginas da web, onde podemos voltar uma pagina ou avançar, porque esta informação está sendo guardada em uma pilha.
Implementando uma pilha em JavaScript
Agora que já entendemos o funcionamento de uma pilha e alguns de seus usos, vamos analisar como criamos essa estrutura de dados, estarei usando JavaScript em esses exemplos.
Podemos começar criando uma classe que será chamada Stack e inicializando as variáveis privadas count e items.
class Stack {
#count;
#items;
}A variável count será usada para controlar a quantidade de elementos em nossa pilha e a variável items guardará os elementos que serão inseridos dentro da pilha.
Então inicializaremos os valores dessas duas variáveis no construtor da classe como mostrado abaixo:
class Stack {
#count;
#items;
constructor() {
this.#count = 0;
this.#items = {};
}
}Em este exemplo estaremos usando um objeto para armazenar os nossos itens ou elementos da pilha, porem também pode ser usado um array.
Agora vamos fazer o método que insere o elemento em nossa pilha, que chamaremos de push.
class Stack {
#count;
#items;
constructor() {
this.#count = 0;
this.#items = {};
}
push(element) {
this.#items[this.#count] = element;
this.#count++;
}
}O que estamos fazendo é atribuir o elemento que queremos inserir na pilha na posição armazenada em nosso contador e depois o incrementando em 1, se a nossa pilha estiver vazia esta será a posição 0 .
Então criaremos a função que retira um elemento do topo da pilha, chamaremos de pop , como é mostrado abaixo:
class Stack {
// ... código anterior
pop() {
if (this.isEmpty()) {
return undefined;
}
const result = this.#items[--this.#count];
delete this.#items[this.#count];
return result;
}
}Não se importe no momento com o método isEmpty logo o construiremos, o que esse método faz é verificar se a nossa pilha está vazia e caso isso seja verdadeiro, retornaremos undefined , porque não queremos tentar retirar um elemento de uma pilha que está vazia, pois isso geraria um erro. Em seguida armazenamos o elemento que estamos removendo na variável result ao mesmo tempo que decrementamos o valor de count , em seguida usamos o comando delete para apagar o elemento na pilha e retornamos o resultado.
Também precisamos ter um meio de saber qual elemento está no topo da pilha, sem necessariamente ter que retira-lo para isto. Por isso criaremos o método que chamaremos de peek como demostrado abaixo:
class Stack {
// ... código anterior
peek() {
if (this.isEmpty()){
return undefined;
}
return this.#items[this.#count - 1];
}
}Novamente verificaremos se a pilha está vazia, pois não queremos verificar o ultimo elemento em uma pilha vazia, logo retornaremos o ultimo elemento que está na posição contador - 1, isto se deve porque sabemos que estamos contando desde a posição 0 , então o valor atual de nosso contador está apontando para a posição do próximo elemento a ser inserido na pilha.
Finalmente criaremos o nosso método isEmpty que irá verificar se pilha está vazia, o código para isso é bem simples, verificaremos se o valor de nosso contador é igual a 0 , porque sabemos que se existir um elemento em nossa pilha, a nossa variável terá o valor 1 ou maior dependendo da quantidade de elementos em nossa pilha.
class Stack {
// ... código anterior
isEmpty() {
return this.#count === 0;
}
}Também precisamos saber a quantidade de elementos que temos atualmente na pilha, criaremos o método size para isso.
class Stack {
// ... código anterior
size() {
return this.#count;
}
}Simplesmente retornaremos o valor de nosso contador que sempre corresponderá a quantidade elementos em nossa pilha, devido a lógica que estamos usando.
Temos que também criar um método para esvaziar a nossa pilha, para isso criaremos o método clear como visto abaixo:
class Stack {
// ... código anterior
clear() {
this.#items = {};
this.#count = 0;
}
}O que fazemos aqui é simplesmente definir os atributos para os mesmos valores que iniciamos em nosso construtor, ou seja, zerados. Poderíamos também ter criado um loop que usaria nosso método pop até não haver itens em nossa pilha, mais escolhi essa abordagem mais simples.
Também seria muito útil se tivéssemos uma função que retornarse uma string com todos os valores armazenados em nossa stack, para isso criaremos o método toString da seguinte maneira:
class Stack {
// ... código anterior
toString() {
if(this.isEmpty()){
return "";
}
let objString = `${this.#items[0]}`;
for (let i = 1; i < this.#count; i++) {
objString = `${objString},${this.#items[i]}`
}
return objString;
}
}O que estamos fazendo aqui é primeiro verificar se a pilha esta vazia, logo iniciamos uma variável de suporte chamada objString que começará com o valor referente a primeira posição de nossa pilha, depois iniciamos um loop na posição 1 que se refere 2ª posição de nossa pilha e logo concatenaremos em cada volta do loop o valor atual em objString com a próxima posição de nossa pilha até não haver mais elementos a serem concatenados na string, por fim retornaremos essa string.
Código final
Terminamos a implementação de nossa pilha (”stack”), veja o resultado final abaixo:
class Stack {
#count;
#items;
constructor() {
this.#count = 0;
this.#items = {};
}
push(element) {
this.#items[this.#count] = element;
this.#count++;
}
pop() {
if (this.isEmpty()) {
return undefined;
}
const result = this.#items[--this.#count];
delete this.#items[this.#count];
return result;
}
peek() {
if (this.isEmpty()){
return undefined;
}
return this.#items[this.#count - 1];
}
isEmpty() {
return this.#count === 0;
}
size() {
return this.#count;
}
clear() {
this.#items = {};
this.#count = 0;
}
toString() {
if(this.isEmpty()){
return "";
}
let objString = `${this.#items[0]}`;
for (let i = 1; i < this.#count; i++) {
objString = `${objString},${this.#items[i]}`
}
return objString;
}
}Para que você possa visualizar melhor o funcionamento dessa estrutura de dados analise a seguinte imagem:
Exemplo do funcionamento da pilha, por professor Ricardo Farias - UFRJ
Em código esse exemplo de uso ficaria assim:
const stack = new Stack();
stack.push(10);
stack.push(5);
stack.push(15);
stack.pop();
console.log(stack.toString());E o resultado:
10,5
Imagem por Youssef Sawiris
Exemplo prático de uso
Agora vamos ver um dos muitos exemplos práticos de uso de pilhas, neste caso construiremos um algoritmo que converte um numero decimal para outro tipo de base.
function baseConverter(decNumber, base) {
const remStack = new Stack();
const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
let number = decNumber;
let rem;
let baseString = "";
if(!(base >= 2 && base <= 36)) return "";
while (number > 0) {
rem = Math.floor(number % base);
remStack.push(rem);
number = Math.floor(number / base);
}
while(!remStack.isEmpty()) {
baseString += digits[remStack.pop()];
}
return baseString;
}Nesse algoritmo declaramos a função que recebe como parâmetros o numero a ser convertido e a base para o qual deve ser convertido, na função, iniciamos nossa stack e declaramos os dígitos possíveis nas bases decimais que serão suportadas que no caso é da base 2 a 36.
Iniciamos a variável number que receberá o valor que queremos converter, a variável rem que servirá para armazenar o resto temporario da divisão e baseString que armazenará o resultado final do nosso algoritmo.
Verificamos se a base que queremos converter está dentro dos valores válidos citados anteriormente, se não, apenas retornamos uma string vazia.
Então fazemos um primeiro loop enquanto o valor de number for maior que 0 , o algoritmo calcula o resto da divisão de number pela base e empilha esse resto na stack. Em seguida atualiza o valor de number pelo quociente da divisão.
O segundo loop, enquanto a pilha não estiver vazia, desempilha os valores e os utiliza para construir a string do número da base alvo, e por fim retorna o resultado final com baseString.
baseConverter(15, 2)Resultado:
1111Conclusão
A estrutura de dados pilha pode ser usada em muitas situações além da que vimos hoje como em: análise de expressões matemáticas, em algoritmos de backtracking, como busca em labirinto ou resolução de quebra cabeças, histórico de navegação em navegadores web, chamadas de função em linguagens de programação, já ouviu falar do Stack Overflow? Não me refiro ao famoso fórum de programação e sim ao problema de estouro de pilha.
Enfim, são muitos usos e é muito importante o estudo dessa disciplina. Nos próximos artigos estarei trazendo novos algoritmos e estruturas de dados, com uma abordagem detalhada.
Espero que tenha gostado, até a aproxima.
Referencias:
Introduction to Algorithms (”Algoritmos - teoria e prática” em português) - Thomas Cormen
Estruturas de Dados e Algoritmos com JavaScript - Loiane Groner
Estrutura de Dados e Algoritmos | Pilha - Prof. Ricardo Faria/UFRJ