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