Estrutura de dados de Pilha

Uma pilha é uma coleção ordenada de items que obedece ao princípio LIFO

LIFO = (Last In First Out) que significa: O último a entrar é o primeiro a sair

A adição de novos itens ou a remoção de itens existentes ocorrem na mesma extremidade

O Final da Pilha é conhecido como o Topo, e o lado oposto é conhecido como a base

Os elementos mais novos ficam próximos ao topo, e os elementos antigos próximos da base

Criando uma classe Stack baseada em Array

class Stack {
  constructor() {
    this.items = []
  }
}

Como a Pilha obedece o princípio LIFO (Last In First Out), limitaremos as funcionalidades que estarão disponíveis à inserção e remoção de elementos

Os métodos a seguir estarão disponíveis na classe Stack

• push(element(s)): esse método adiciona um novo elemento (ou vários elementos) no topo da pilha

• pop(): esse método remove o elemento que está no topo da pilha e também devolve o elemento removido

• peek(): esse método devolve o elemento que está no topo da pilha. A pilha não é modificada (O elemento não é removido; ele é devolvido apenas como informação)

• isEmpty(): esse método devolve true se a pilha não contiver nenhum elemento e false se o tamanho da pilha for menor que 0

• clear(): esse método removetodosos elementos da pilha

• size(): esse método devolve o número de elementos contidos na pilha. É semelhante à propriedade length de um array

Push de elementos na Pilha

O primeiro método que vamos implementar é o método push, responsável pela adição de novos elementos na pilha, e com um detalhe muito importante: só podemos adicionar novos itens no topo da pilha, isso significa, no final dela

O método push é representado assim:

push(element) {
  this.items.push(element)
}

Como estamos usando um array para armazenar os elementos da pilha, podemos usar o método push de Array do Javascript

Pop de elementos da Pilha

Agora vamos implementar o método pop, responsável pela remoção de itens da pilha. Como a pilha utiliza o princípio LIFO (Last In First Out), o último item adicionado é aquele que será removido. Por esse motivo vamos utilizar o método pop de Array do Javascript

O método pop é representado assim:

pop() {
  return this.items.pop()
}

Como estamos utilizando apenas os métodos push e pop para adição e remoção de itens da pilha, o princípio LIFO (Last In First Out) se aplicará à nossa classe Stack

Verificando o elemento que está no topo da Pilha

Vamos implementar agora alguns métodos auxiliares adicionais em nossa classe

Se quisermos saber qual foi o último elemento adicionado em nossa pilha, podemos usar o método peek. Esse método devolverá o item que está no topo da pilha

O método peek é representado assim:

peek() {
  return this.items[this.items.length - 1]
}

Como estamos usando internamente um array Javascript para armazenar os itens, o último item de um array pode ser obtido usando length - 1

Verificando se a Pilha está vazia

Os próximos métodos que criaremos é isEmpty e size

isEmpty devolverá true se a pilha estiver vazia (nenhum elemento foi adicionado), e false caso contrário

O método isEmpty é representado assim:

isEmpty() {
  return this.items.length === 0
}

Ao usar o método isEmpty, podemos simplesmente verificar se o tamanho do array interno é 0

De modo semelhante à propriedade length de um array Javascript, também podemos implementar length em nossa classe Stack. Para coleções, em geral é usado o termo size no lugar de length

novamente, como estamos usando um array Javascript internamente, basta devolver o valor de length

O método size é representado assim:

size() {
  return this.items.length
}

Limpando todos os elementos da Pilha

Por fim, vamos implementar o método clear, o qual simplesmente esvazia a pilha, removendo todos os seus elementos

O método clear é representado assim:

clear() {
  this.items = []
}

E uma alternativa seria chamar o método pop até que a pilha esteja vazia

Pronto! sua classe Stack está implementada :)