Estruturas de Dados - Pilhas

Escrito por

Hoje vamos falar um pouco sobre uma estrutura de dados que é muito comum em computação, principalmente em sua base, a Pilha. O primeiro conceito que temos que saber sobre Pilha é que ela segue o conceito de LIFO (Last In First Out), então o último que entra é o primeiro que sai. Uma coisa bem legal em JavaScript é que já temos uma Pilha naturalmente no vetor, então se fizermos, por exemplo:

1const vetor = []
2vetor.push(1)
3vetor.push(2)
4console.log(vetor.pop())
5console.log(vetor)

Percebam que quando desempilhamos ele volta o último item que foi empilhado e modifica o vetor. Agora vamos implementar isso sem precisar utilizar o vetor dessa forma, criando nossa própria implementação de stack:

1const Stack = () => {
2 const data = []
3 let top = -1
4}

Como estamos fazendo no modo funcional, não temos o this, estamos guardando apenas no próprio contexto e podemos retornar os métodos que queremos criar:

1const Stack = () => {
2 const data = []
3 let top = -1
4 const push = value => {
5 top++
6 data[top] = value
7 console.log(data)
8 }
9 return {
10 push,
11 }
12}
13const stack = Stack
14stack.push(1)
15stack.push(2)

Perceba que ele está montando o vetor perfeitamente adicionando sempre na frente. Agora precisamos remover esse último item:

1const push = value => {
2 top++
3 data[top] = value
4 console.log(data)
5}
6const pop = () => {
7 if (top < 0) {
8 return false
9 } else {
10 const itemToReturn = data[top]
11 delete data[top]
12 top--
13 return itemToReturn
14 }
15}
16return {
17 push,
18 pop,
19}
20console.log(stack.pop())

Agora funcionou perfeitamente, ele retirou o um e deixou apenas o dois. Vamos criar um novo método chamado print para sabermos como está a estrutura:

1const print = () => {
2 console.log(data)
3}
4return {
5 push,
6 pop,
7 print,
8}

Perceba que nós temos um item vazio, então ele não removeu esse item. Ao invés de utilizar o delete, podemos utilizar o splice:

1} else {
2 const itemToReturn = data[top]
3 data.splice(top, 1)
4 top--
5 return itemToReturn
6 }

O splice já faz essa fatia, cortando nosso array no item top.

Acabamos de implementar uma pilha. É muito interessante conhecer o que é pilha, faz mais sentido quando recebemos os erro stack overflow, acontece que as estruturas de dados vão se empilhando tanto que não aguenta mais o tamanho, por esse motivo é um erro bem comum.

Confira o video:

Curta o DevPleno no Facebookinscreva-se no canal e cadastre seu e-mail para não perder nenhuma novidade. Deixe suas dúvidas e sugestões nos comentários. Abraço!

Evolua mais rápido

Junte-se a milhares de desenvolvedores no nosso time de alunos premium e alcance mais rápido o próximo nível da sua carreira.

Ver cursos Premium