Criando uma classe Stack baseada em Objeto

O modo mais fácil de criar uma classe Stack usa um array para armazenar seus elementos

Você pode ver como isso é aplicado nesse outro post de Como criar uma pilha em JS

Ao trabalhar com um conjunto grande de dados (o que é muito comum em projetos reais),

também é necessário analisar qual é o modo mais eficaz de manipular os dados

Quando trabalhamos com arrays, a maioria dos métodos tem uma complexidade de tempo O(n)

isso significa que, para a maioria dos métodos, devemos iterar pelo array até encontrarmos o elemento que estamos procurando e, no cenário de pior caso, faremos a iteração por todas as posições do array, considerando que n é o tamanho do array

Se o array tiver mais elementos, demorará mais para iterar pelos elementos, em comparação com um array com menos elementos

Além disso, um array é um conjunto ordenado de elementos, e, para mantê-los assim, seria necessário ter mais espaço na memória também

Não seria melhor se pudéssemos acessar diretamente o elemento, usar menos espaço de memória e continuar tendo todos os elementos organizados conforme fosse necessário?

No cenário de uma estrutura de dados de pilha na linguagem Javascript, também é possível usar um Objeto para armazenar os elementos da pilha, mantê-los em ordem e obedecer igual ao princípio LIFO (Last In First Out), vamos ver como podemos conseguir esse comportamento

Começaremos declarando a classe Stack da seguinte maneira:

class Stack {
  constructor() {
    this.count = 0
    this.items = {}
  }
}

Nessa versão da classe Stack, usaremos uma propriedade count para nos ajudar a manter o controle do tamanho da pilha e, consequentemente, para nos ajudar também a adicionar e a remover elementos da estrutura de dados

Push de elementos na Pilha

Na versão baseada em array, podíamos adicionar vários elementos à classe Stackao mesmo tempo

Como estamos trabalhando com um objeto, essa versão do método push no permite fazer push somente de um único elemento de cada vez

Podemos ver o código do método push a seguir:

push(element) {
  this.items[this.count] = element
  this.count++
}

Em Javascript, um objeto é um conjunto de pares chave e valor

Para adicionar element à pilha, usaremos a variável count como a chave do objeto items, e element será o seu valor

Depois de fazer o push do elemento na pilha, incrementamos count

Verificando se a Pilha está vazia e o seu tamanho

A propriedade count também funciona como o tamanho da pilha. Assim, para o método size podemos simplesmente devolver a propriedade count

size() {
  return this.count
}

Para verificar se a pilha está vazia, podemos comparar o valor de count é 0

Dessa maneira:

isEmpty() {
  return this.count === 0
}

Pop de elementos da Pilha

Como não estamos usando um array para armazenar os elementos, teremos de implementar manualmente a lógica para remover um elemento

O método pop também devolve o elemento que foi removido da pilha

Esse método é implementado assim:

pop() {
  if (this.isEmpty()) {
    return undefined
  }
  this.count--
  const result = this.items[this.count]
  delete this.items[this.count]
  return result
}

Inicialmente devemos verificar se a pilha está vazia e, em caso afirmativo, devolveremos o valor undefined

Se a pilha não estiver vazia, decrementaremos a propriedade count e armazenaremos o valor do topo da pilha para que possamos devolvê-lo depois que o elemento for removido

Como estamos trabalhando com um Objeto, para remover um valor específico de um objeto, podemos usar o operador delete do Javascript

Vamos usar os valores internos a seguir para emular a ação do pop

items = {
  0: 5,
  1: 8
}

Para acessar o elemento no topo da pilha (último elemento adicionado), precisamos acessar a chave com valor 1

Então decrementamos a variável count de 2 para 1 e podemos acessar items[1], apagá-lo e devolver o seu valor

Dando uma espiada no topo e limpando a Pilha

No último método, vimos que, para acessar o elemento armazenado no topo da pilha, é necessário decrementar a propriedade count de 1

Vamos então ver o código do método peek

peek() {
  if (this.isEmpty()) {
    return undefined
  }
  return this.items[this.count - 1]
}

Para limpar a pilha, basta reiniciá-la com os mesmos valores usados no construtor:

clear() {
  this.count = 0
  this.items = {}
}

E como alternativa, também poderíamos usar a lógica a seguir para remover todos os elementos da pilha, respeitando o comportamento de LIFO

while (!this.isEmpty()){
  this.pop()
}

Criando o método toString

Na versão com array, não precisamos nos preocupar com um método toString, pois a estrutura de dados usará o método já oferecido pelo array

Para essa versão com objeto, criaremos um método toString para que possamos exibir o conteúdo da pilha, de modo semelhante a um array

Veja o código a seguir:

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
}

Se a pilha estiver vazia, basta devolver uma string vazia

Se não estiver vazia, inicializaremos a string com o primeiro elemento, que está na base da pilha

Então faremos a iteração por todas as chaves da pilha até o seu topo, adicionando uma virgula,

em seguida do próximo elemento

Com o método toString, concluímos essa versão da classe Stack

Com exceção do método toString todos os outros métodos que criamos têm complexidade O(1),

o que significa que podemos acessar diretamente o elemento no qual estamos interessados e executar uma ação com ele (push, pop ou peek)

Esse é também um exemplo de como ter diferentes versões de código. Para o desenvolvedor que usar a classe Stack, não importa se a versão com array ou objeto será usada; ambas têm a mesma funcionalidade, mas, internamente, o comportamento é muito diferente