Implementando Pilha (Stack) com NodeJS e Javascript

Desfazer a última ação, avaliar expressão, percorrer DFS — tudo é pilha (LIFO): o último que entrou sai primeiro. Vamos implementar com array nativo do JS.

O que você vai aprender:

• push / pop como stack
• Encapsular em classe Stack
• Call stack e parsing como casos reais
• Quando pilha ≠ array “qualquer”

Pré-requisitos: arrays (ep. 2) e linked list (ep. 3).

Stack (pilha): LIFO com push e pop

Então tá, vamos lá. Chegamos na implementação de Pilhas, ou stacks. Que bicho é esse é como funciona? Pilhas são uma estrutura de dados fundamental na programação, elas operam no modo Last In, First Out (LIFO), onde o último elemento adicionado é o primeiro a ser removido/processado.

Em NodeJS/JavaScript, entender e implementar pilhas pode otimizar significativamente o gerenciamento de dados, especialmente quando a gente precisa resolver algum problema de uma sequência reversa de operações (lembra aquele desafio que sempre encontramos por ai de inverter uma array? Pois é.! ) ou também pode ser usada para gerenciamento de estados.

Pilhas (Stacks): Implementação

Uma pilha é uma coleção ordenada de itens onde a adição de novos itens e a remoção de itens existentes sempre ocorrem no mesmo final, conhecido como topo da pilha. Este conceito é amplamente utilizado em várias aplicações de programação, desde a execução de chamadas de função até algoritmos de parsing.

Implementando Pilhas em JavaScript

O JavaScript não tem uma estrutura de dados de pilha incorporada e isso é ótimo, porque daí podemos fazer a nossa (ou usar uma lib né, você não precisa fazer pra usar no teu trampo sendo que já tem lib pra isso) mas é legal entender como funciona, é possível implementar uma usando arrays. Aqui está uma implementação básica:

class Stack {
  constructor() {
    this.items = []
  }
 
  // Adiciona um elemento no topo da pilha
  push(element) {
    this.items.push(element)
  }
 
  // Remove o elemento do topo da pilha
  pop() {
    if (this.items.length == 0) {
      return 'Empty' // Pilha vazia
    }
    return this.items.pop()
  }
 
  // Retorna o elemento no topo da pilha sem removê-lo
  peek() {
    return this.items[this.items.length - 1]
  }
 
  // Verifica se a pilha está vazia
  isEmpty() {
    return this.items.length == 0
  }
 
  // Imprime a pilha
  printStack() {
    for (let i = this.items.length - 1; i >= 0; i--) {
      console.log(this.items[i])
    }
  }
}

Aplicações Práticas

Gerenciamento de Chamadas de Função

Pilhas são essenciais para o gerenciamento de chamadas de função, onde cada chamada é colocada em uma pilha e processada na ordem LIFO, facilitando a execução e o retorno de funções.

Ordenação

Sabe aquele histórico que você consulta e precisa ordenar por data? A última alteração (a mais recente) é a primeira que aparece na tela? Então, é um exemplo bobo, mas essa ordenação pode ser feita com stacks também.

Algoritmos de Parsing

No parsing de expressões, como conversões de notação infix para postfix, pilhas desempenham um papel crucial na ordenação correta dos operadores e operandos.

Edge cases: pop em pilha vazia

pop() em array vazio retorna undefined — sem erro. Em produção, cheque isEmpty() antes ou lance exceção explícita.

"Tá Jon, stack overflow é a mesma pilha?"

Sim — estourou a call stack do JS: muitas funções recursivas sem caso base. Estrutura é a mesma ideia LIFO.

TL;DR — Pilha

Próximos passos

• Fila (ep. 5): FIFO — oposto natural da pilha — Implementando Filas
• Grafos (ep. 14): DFS usa pilha (ou recursão) — BFS e DFS

Antes de fechar

Qual one-liner de “inverter array com pilha” você usaria? Comenta — e se viu erro no Stack do post, avisa.