Uso de Pilhas para Resolver Problemas Comuns

Algumas situações são naturalmente adequadas para implementação com pilhas. Esta seção explora três exemplos práticos que demonstram a utilidade dessa estrutura de dados em algoritmos com JavaScript.

1. Conversão entre Bases Numéricas

Uma pilha pode ser empregada para converter números entre diferentes bases. Para transformar um número inteiro n na base b, o processo envolve extrair os dígitos restantes e empilhá-los, produzindo a representação correta na nova base. A implementação a seguir converte números para bases de dois a nove:

// Conversão de base usando classe Pilha
function mudarBase(num, base) {
    let pilha = [];
    let valor = num;
    do {
        pilha.push(valor % base);
        valor = Math.floor(valor / base);
    } while (valor > 0);

    let resultado = "";
    while (pilha.length > 0) {
        resultado += pilha.pop();
    }
    return resultado;
}

// Exemplo de uso
console.log(mudarBase(32, 2));   // Saída: 100000 (binário)
console.log(mudarBase(125, 8));  // Saída: 175 (octal)

A função acumula os restos da divisão na pilha e, em seguida, desempilha para formar a string resultante na base desejada.

2. Verificação de Palíndromos

Um palíndromo é uma sequência que se lê da mesma forma de trás para frente, ignorando pontuações e espaços. Para verificar se uma string é um palíndromo, pode-se empilhar todos os caracteres e depois desempilhá-los para construir a versão invertida. Se as duas strings coincidirem, trata-se de um palíndromo.

// Função para detectar palíndromos com pilha
function ehPalindromo(texto) {
    let pilha = [];
    for (let i = 0; i < texto.length; i++) {
        pilha.push(texto[i]);
    }
    let invertido = "";
    while (pilha.length > 0) {
        invertido += pilha.pop();
    }
    return texto === invertido;
}

// Testes
console.log(ehPalindromo("racecar")); // true
console.log(ehPalindromo("hello"));   // false

Este método simples garante uma verificação eficiente, aproveitando a propriedade LIFO da pilha para inverter a string.

3. Simulação de Recursão com Pilha

Pilhas podem simular o comportamento de funções recursivas, evitando o uso direto de chamadas recursivas. Para calcular o fatorial de um número, por exemplo, empilham-se os valores de n até 1 e depois multiplicamos os elementos desempilhados.

// Cálculo de fatorial usando pilha iterativa
function fatorial(n) {
    let pilha = [];
    let contador = n;
    while (contador > 1) {
        pilha.push(contador);
        contador--;
    }
    let produto = 1;
    while (pilha.length > 0) {
        produto *= pilha.pop();
    }
    return produto;
}

console.log(fatorial(5)); // 120

Esta abordagem ilustra como a pilha organiza os passos de cálculo de maneira explícita, substituindo a pilha de chamadas do sistema em uma implementação recursiva.