Pilha (Stack): Estrutura LIFO em Rust

Introdução

A pilha (stack) é uma das estruturas de dados mais fundamentais e intuitivas da ciência da computação. Ela segue o princípio LIFO — Last In, First Out (último a entrar, primeiro a sair) — da mesma forma que uma pilha de pratos: você só pode colocar ou retirar pratos do topo.

Apesar de sua simplicidade conceitual, a pilha é extraordinariamente versátil. Ela é utilizada internamente pelo próprio computador (a call stack gerencia chamadas de funções), por compiladores (análise sintática e avaliação de expressões), navegadores (botão voltar), editores de texto (desfazer) e em inúmeros algoritmos como DFS (busca em profundidade).

Em Rust, a implementação mais natural e eficiente de uma pilha é usar Vec<T> como armazenamento interno, aproveitando suas operações push() e pop() que já operam no final do vetor em O(1). Neste artigo, construiremos uma pilha genérica, exploraremos algoritmos clássicos e implementaremos um parser/calculadora de expressões completo.

Conceito e Teoria

O Princípio LIFO

  Operações em uma Pilha:

  push(40)          pop()             peek()
  ═══════           ═════             ══════

  ANTES:            ANTES:            Estado:
  ┌─────┐           ┌─────┐           ┌─────┐
  │ 30  │ ← topo    │ 40  │ ← topo    │ 40  │ ← retorna 40
  ├─────┤           ├─────┤           ├─────┤    (sem remover)
  │ 20  │           │ 30  │           │ 30  │
  ├─────┤           ├─────┤           ├─────┤
  │ 10  │           │ 20  │           │ 20  │
  ├─────┤           ├─────┤           ├─────┤
  │     │           │ 10  │           │ 10  │
  └─────┘           └─────┘           └─────┘

  DEPOIS:           DEPOIS:
  ┌─────┐           ┌─────┐
  │ 40  │ ← topo    │ 30  │ ← topo    retorna: Some(40)
  ├─────┤           ├─────┤
  │ 30  │           │ 20  │
  ├─────┤           ├─────┤
  │ 20  │           │ 10  │
  ├─────┤           └─────┘
  │ 10  │
  └─────┘

Pilha na Memória (usando Vec)

  Pilha<i32> com 4 elementos:

  Stack (metadados do Vec)        Heap (dados reais)
  ┌──────────────────┐           ┌─────┬─────┬─────┬─────┬─────┬─────┐
  │ ptr ─────────────┼──────────►│ 10  │ 20  │ 30  │ 40  │     │     │
  │ len: 4           │           │     │     │     │topo │livre│livre│
  │ capacity: 6      │           └─────┴─────┴─────┴─────┴─────┴─────┘
  └──────────────────┘                                ▲
                                            push e pop operam aqui
                                            (final do Vec = topo da pilha)

A Call Stack (Pilha de Chamadas)

Toda vez que uma função é chamada, o computador empilha um stack frame na call stack:

  fn main() {             Execução de main():
      let x = fatorial(4);
  }                       Call Stack:
                          ┌─────────────────┐
  fn fatorial(n: u64)     │ fatorial(1) = 1 │ ← topo (retorna 1)
      -> u64 {            ├─────────────────┤
      if n <= 1 {         │ fatorial(2)     │    (espera resultado)
          1               ├─────────────────┤
      } else {            │ fatorial(3)     │    (espera resultado)
          n * fatorial    ├─────────────────┤
              (n - 1)     │ fatorial(4)     │    (espera resultado)
      }                   ├─────────────────┤
  }                       │ main()          │    (espera resultado)
                          └─────────────────┘

  Desempilhando:
  fatorial(1) retorna 1
  fatorial(2) retorna 2 * 1 = 2
  fatorial(3) retorna 3 * 2 = 6
  fatorial(4) retorna 4 * 6 = 24
  main() recebe 24

Complexidade

Operação	Complexidade	Descrição
`push(valor)`	O(1)*	Empilha um elemento no topo
`pop()`	O(1)	Desempilha e retorna o topo
`peek()` / `topo()`	O(1)	Consulta o topo sem remover
`esta_vazia()`	O(1)	Verifica se a pilha está vazia
`tamanho()`	O(1)	Retorna o número de elementos
Busca	O(n)	Pilhas não são feitas para busca
Acesso ao i-ésimo	O(n)	Pilhas não suportam acesso aleatório

*O(1) amortizado. No pior caso, quando o Vec precisa realocar, é O(n).

Implementação em Rust

Pilha Genérica com Vec

use std::fmt;

/// Pilha genérica implementada com Vec como armazenamento interno
#[derive(Debug, Clone)]
pub struct Pilha<T> {
    elementos: Vec<T>,
}

impl<T> Pilha<T> {
    /// Cria uma pilha vazia
    pub fn nova() -> Self {
        Pilha {
            elementos: Vec::new(),
        }
    }

    /// Cria uma pilha com capacidade pré-alocada
    pub fn com_capacidade(capacidade: usize) -> Self {
        Pilha {
            elementos: Vec::with_capacity(capacidade),
        }
    }

    /// Empilha um elemento no topo — O(1) amortizado
    pub fn empilhar(&mut self, valor: T) {
        self.elementos.push(valor);
    }

    /// Desempilha e retorna o elemento do topo — O(1)
    pub fn desempilhar(&mut self) -> Option<T> {
        self.elementos.pop()
    }

    /// Retorna referência ao topo sem remover — O(1)
    pub fn topo(&self) -> Option<&T> {
        self.elementos.last()
    }

    /// Retorna referência mutável ao topo sem remover — O(1)
    pub fn topo_mut(&mut self) -> Option<&mut T> {
        self.elementos.last_mut()
    }

    /// Verifica se a pilha está vazia — O(1)
    pub fn esta_vazia(&self) -> bool {
        self.elementos.is_empty()
    }

    /// Retorna o número de elementos — O(1)
    pub fn tamanho(&self) -> usize {
        self.elementos.len()
    }

    /// Remove todos os elementos da pilha
    pub fn limpar(&mut self) {
        self.elementos.clear();
    }
}

/// Exibição formatada da pilha
impl<T: fmt::Display> fmt::Display for Pilha<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "┌─── Topo ───┐")?;
        for elem in self.elementos.iter().rev() {
            writeln!(f, "│ {:^10} │", elem)?;
        }
        writeln!(f, "└────────────┘")?;
        Ok(())
    }
}

fn main() {
    let mut pilha: Pilha<i32> = Pilha::nova();

    // Empilhando elementos
    pilha.empilhar(10);
    pilha.empilhar(20);
    pilha.empilhar(30);
    pilha.empilhar(40);

    println!("Pilha após empilhar 10, 20, 30, 40:");
    println!("{}", pilha);

    // Consultando o topo
    if let Some(topo) = pilha.topo() {
        println!("Topo: {}", topo);
    }

    // Desempilhando
    while let Some(valor) = pilha.desempilhar() {
        println!("Desempilhado: {}", valor);
    }

    println!("Pilha vazia? {}", pilha.esta_vazia());
}

Algoritmo: Balanceamento de Parênteses

Um dos usos mais clássicos de pilhas é verificar se uma expressão tem parênteses balanceados:

/// Verifica se os delimitadores de uma expressão estão balanceados
///
/// Suporta: (), [], {}
/// Exemplos:
///   "(a + b) * [c - d]"    → true
///   "((a + b)"             → false
///   "{[()]}"               → true
///   "([)]"                 → false
fn delimitadores_balanceados(expressao: &str) -> bool {
    let mut pilha: Vec<char> = Vec::new();

    for caractere in expressao.chars() {
        match caractere {
            // Delimitadores de abertura: empilha
            '(' | '[' | '{' => pilha.push(caractere),

            // Delimitadores de fechamento: verifica correspondência
            ')' => {
                if pilha.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if pilha.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if pilha.pop() != Some('{') {
                    return false;
                }
            }

            // Outros caracteres são ignorados
            _ => {}
        }
    }

    // A expressão é balanceada se a pilha estiver vazia
    pilha.is_empty()
}

fn main() {
    let testes = vec![
        ("(a + b) * [c - d]", true),
        ("((a + b)", false),
        ("{[()]}", true),
        ("([)]", false),
        ("", true),
        ("}{", false),
        ("fn main() { let v = vec![1, 2, 3]; }", true),
    ];

    println!("═══ Teste de Balanceamento de Delimitadores ═══\n");
    for (expressao, esperado) in testes {
        let resultado = delimitadores_balanceados(expressao);
        let status = if resultado == esperado { "OK" } else { "FALHA" };
        println!(
            "  [{}] \"{}\" → {} (esperado: {})",
            status, expressao, resultado, esperado
        );
    }
}

Algoritmo: Avaliação de Expressão Pós-fixa (Notação Polonesa Reversa)

/// Avalia uma expressão em notação pós-fixa (RPN)
///
/// Na notação pós-fixa, os operadores vêm após os operandos:
///   Infixa: (3 + 4) * 2  →  Pós-fixa: 3 4 + 2 *
///
/// O algoritmo usa uma pilha:
///   - Número: empilha
///   - Operador: desempilha dois, aplica, empilha resultado
fn avaliar_posfixa(expressao: &str) -> Result<f64, String> {
    let mut pilha: Vec<f64> = Vec::new();

    for token in expressao.split_whitespace() {
        match token {
            "+" | "-" | "*" | "/" | "^" => {
                // Operador: precisa de dois operandos
                let b = pilha.pop().ok_or("Expressão inválida: faltam operandos")?;
                let a = pilha.pop().ok_or("Expressão inválida: faltam operandos")?;

                let resultado = match token {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    "/" => {
                        if b == 0.0 {
                            return Err("Erro: divisão por zero".to_string());
                        }
                        a / b
                    }
                    "^" => a.powf(b),
                    _ => unreachable!(),
                };

                pilha.push(resultado);
            }
            // Número: empilha
            _ => {
                let numero: f64 = token
                    .parse()
                    .map_err(|_| format!("Token inválido: '{}'", token))?;
                pilha.push(numero);
            }
        }
    }

    // Deve sobrar exatamente um valor na pilha
    if pilha.len() != 1 {
        return Err(format!(
            "Expressão inválida: {} valores restantes na pilha",
            pilha.len()
        ));
    }

    Ok(pilha.pop().unwrap())
}

fn main() {
    let expressoes = vec![
        ("3 4 +", "(3 + 4) = 7"),
        ("3 4 + 2 *", "(3 + 4) * 2 = 14"),
        ("5 1 2 + 4 * + 3 -", "5 + (1 + 2) * 4 - 3 = 14"),
        ("2 3 ^ 1 -", "2^3 - 1 = 7"),
        ("10 2 /", "10 / 2 = 5"),
        ("15 7 1 1 + - / 3 * 2 1 1 + + -", "expressão complexa"),
    ];

    println!("═══ Avaliação de Expressões Pós-fixas ═══\n");
    for (expr, descricao) in expressoes {
        match avaliar_posfixa(expr) {
            Ok(resultado) => {
                println!("  \"{}\"", expr);
                println!("  {} → {:.2}\n", descricao, resultado);
            }
            Err(erro) => {
                println!("  \"{}\" → ERRO: {}\n", expr, erro);
            }
        }
    }
}

Métodos Principais

Método	Tipo Retorno	Descrição
`Pilha::nova()`	`Pilha<T>`	Cria uma pilha vazia
`com_capacidade(n)`	`Pilha<T>`	Cria com capacidade pré-alocada
`empilhar(valor)`	`()`	Adiciona ao topo — O(1) amortizado
`desempilhar()`	`Option<T>`	Remove e retorna o topo — O(1)
`topo()`	`Option<&T>`	Referência ao topo sem remover — O(1)
`topo_mut()`	`Option<&mut T>`	Referência mutável ao topo — O(1)
`esta_vazia()`	`bool`	Verifica se está vazia — O(1)
`tamanho()`	`usize`	Número de elementos — O(1)
`limpar()`	`()`	Remove todos os elementos

Usando Vec Diretamente como Pilha

Na prática, muitos desenvolvedores Rust simplesmente usam Vec<T> como pilha:

fn exemplo_vec_como_pilha() {
    let mut pilha: Vec<String> = Vec::new();

    // push = empilhar
    pilha.push("primeiro".to_string());
    pilha.push("segundo".to_string());
    pilha.push("terceiro".to_string());

    // pop = desempilhar
    while let Some(valor) = pilha.pop() {
        println!("{}", valor);
        // Imprime: terceiro, segundo, primeiro (LIFO)
    }

    // last = topo (peek)
    pilha.push("único".to_string());
    if let Some(topo) = pilha.last() {
        println!("Topo: {}", topo);
    }
}

Exemplo Prático: Parser e Calculadora de Expressões Infixas

Um exemplo realista e completo: converter uma expressão infixa (como “3 + 4 * 2”) para pós-fixa usando o algoritmo Shunting-Yard de Dijkstra, e então avaliar o resultado.

use std::fmt;

/// Tipos de token reconhecidos pelo parser
#[derive(Debug, Clone, PartialEq)]
enum Token {
    Numero(f64),
    Operador(char),
    ParenEsquerdo,
    ParenDireito,
}

impl fmt::Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Token::Numero(n) => write!(f, "{}", n),
            Token::Operador(op) => write!(f, "{}", op),
            Token::ParenEsquerdo => write!(f, "("),
            Token::ParenDireito => write!(f, ")"),
        }
    }
}

/// Retorna a precedência do operador (maior = mais prioritário)
fn precedencia(op: char) -> u8 {
    match op {
        '+' | '-' => 1,
        '*' | '/' => 2,
        '^' => 3,
        _ => 0,
    }
}

/// Verifica se o operador é associativo à direita
fn associativo_direita(op: char) -> bool {
    op == '^'
}

/// Tokeniza uma expressão em string para uma lista de tokens
fn tokenizar(expressao: &str) -> Result<Vec<Token>, String> {
    let mut tokens = Vec::new();
    let mut chars = expressao.chars().peekable();

    while let Some(&c) = chars.peek() {
        match c {
            // Espaços em branco: ignorar
            ' ' | '\t' => {
                chars.next();
            }
            // Dígitos e ponto decimal: construir número
            '0'..='9' | '.' => {
                let mut numero_str = String::new();
                while let Some(&d) = chars.peek() {
                    if d.is_ascii_digit() || d == '.' {
                        numero_str.push(d);
                        chars.next();
                    } else {
                        break;
                    }
                }
                let numero: f64 = numero_str
                    .parse()
                    .map_err(|_| format!("Número inválido: '{}'", numero_str))?;
                tokens.push(Token::Numero(numero));
            }
            // Operadores
            '+' | '-' | '*' | '/' | '^' => {
                tokens.push(Token::Operador(c));
                chars.next();
            }
            // Parênteses
            '(' => {
                tokens.push(Token::ParenEsquerdo);
                chars.next();
            }
            ')' => {
                tokens.push(Token::ParenDireito);
                chars.next();
            }
            // Caractere desconhecido
            _ => {
                return Err(format!("Caractere inesperado: '{}'", c));
            }
        }
    }

    Ok(tokens)
}

/// Algoritmo Shunting-Yard: converte infixa para pós-fixa
///
/// Usa duas estruturas:
///   - Fila de saída (resultado em pós-fixa)
///   - Pilha de operadores
fn shunting_yard(tokens: &[Token]) -> Result<Vec<Token>, String> {
    let mut saida: Vec<Token> = Vec::new();
    let mut pilha_operadores: Vec<Token> = Vec::new();

    for token in tokens {
        match token {
            Token::Numero(_) => {
                // Números vão direto para a saída
                saida.push(token.clone());
            }
            Token::Operador(op) => {
                // Desempilha operadores de maior ou igual precedência
                while let Some(topo) = pilha_operadores.last() {
                    match topo {
                        Token::Operador(op_topo) => {
                            let prec_topo = precedencia(*op_topo);
                            let prec_atual = precedencia(*op);

                            let deve_desempilhar = if associativo_direita(*op) {
                                prec_topo > prec_atual
                            } else {
                                prec_topo >= prec_atual
                            };

                            if deve_desempilhar {
                                saida.push(pilha_operadores.pop().unwrap());
                            } else {
                                break;
                            }
                        }
                        _ => break,
                    }
                }
                pilha_operadores.push(token.clone());
            }
            Token::ParenEsquerdo => {
                pilha_operadores.push(token.clone());
            }
            Token::ParenDireito => {
                // Desempilha até encontrar o parêntese esquerdo
                let mut encontrou = false;
                while let Some(topo) = pilha_operadores.pop() {
                    if topo == Token::ParenEsquerdo {
                        encontrou = true;
                        break;
                    }
                    saida.push(topo);
                }
                if !encontrou {
                    return Err("Parêntese direito sem correspondente".to_string());
                }
            }
        }
    }

    // Desempilha operadores restantes
    while let Some(op) = pilha_operadores.pop() {
        if op == Token::ParenEsquerdo {
            return Err("Parêntese esquerdo sem correspondente".to_string());
        }
        saida.push(op);
    }

    Ok(saida)
}

/// Avalia uma expressão pós-fixa tokenizada
fn avaliar_tokens_posfixa(tokens: &[Token]) -> Result<f64, String> {
    let mut pilha: Vec<f64> = Vec::new();

    for token in tokens {
        match token {
            Token::Numero(n) => pilha.push(*n),
            Token::Operador(op) => {
                let b = pilha.pop().ok_or("Faltam operandos")?;
                let a = pilha.pop().ok_or("Faltam operandos")?;

                let resultado = match op {
                    '+' => a + b,
                    '-' => a - b,
                    '*' => a * b,
                    '/' => {
                        if b == 0.0 {
                            return Err("Divisão por zero".to_string());
                        }
                        a / b
                    }
                    '^' => a.powf(b),
                    _ => return Err(format!("Operador desconhecido: {}", op)),
                };
                pilha.push(resultado);
            }
            _ => return Err("Token inesperado na expressão pós-fixa".to_string()),
        }
    }

    if pilha.len() != 1 {
        return Err("Expressão malformada".to_string());
    }

    Ok(pilha.pop().unwrap())
}

/// Calcula uma expressão infixa completa
fn calcular(expressao: &str) -> Result<f64, String> {
    let tokens = tokenizar(expressao)?;
    let posfixa = shunting_yard(&tokens)?;
    avaliar_tokens_posfixa(&posfixa)
}

fn main() {
    let expressoes = vec![
        "3 + 4 * 2",
        "(3 + 4) * 2",
        "2 ^ 3 ^ 2",
        "10 / (5 - 3)",
        "3.14 * 2.5 ^ 2",
        "(1 + 2) * (3 + 4) / (5 - 2)",
        "100 - 50 * 2 + 25",
    ];

    println!("════════════════════════════════════════════");
    println!("       CALCULADORA DE EXPRESSÕES            ");
    println!("════════════════════════════════════════════\n");

    for expr in expressoes {
        match calcular(expr) {
            Ok(resultado) => {
                // Mostra também a forma pós-fixa
                let tokens = tokenizar(expr).unwrap();
                let posfixa = shunting_yard(&tokens).unwrap();
                let posfixa_str: Vec<String> = posfixa.iter().map(|t| t.to_string()).collect();

                println!("  Infixa:   {}", expr);
                println!("  Pós-fixa: {}", posfixa_str.join(" "));
                println!("  Resultado: {:.4}\n", resultado);
            }
            Err(erro) => {
                println!("  {} → ERRO: {}\n", expr, erro);
            }
        }
    }
}

Comparação com Outras Estruturas

Critério	Pilha (Vec)	Fila (VecDeque)	Lista Ligada
Inserção (principal)	O(1) topo	O(1) final	O(1) início
Remoção (principal)	O(1) topo	O(1) início	O(1) início
Acesso ao próximo elemento	O(1) topo	O(1) frente	O(1) cabeça
Acesso aleatório	O(1)*	O(1)	O(n)
Semântica	LIFO	FIFO	Variável
Cache-friendly	Sim	Sim	Não

*O acesso aleatório é possível tecnicamente (por estar em Vec), mas viola a semântica da pilha.

Quando Usar Pilha?

Inversão de ordem: quando precisa processar elementos na ordem reversa da inserção.
Parsing e avaliação de expressões: compiladores, calculadoras, validação de sintaxe.
Backtracking: algoritmos que precisam “voltar atrás”, como resolução de labirintos e DFS.
Gerenciamento de estados: undo/redo, navegação (voltar/avançar).
Conversão de recursão para iteração: qualquer algoritmo recursivo pode ser convertido para iterativo usando uma pilha explícita.

Pilha vs Recursão

Muitas vezes a escolha entre usar uma pilha explícita e usar recursão depende do contexto:

Aspecto	Recursão	Pilha Explícita
Legibilidade	Geralmente melhor	Pode ser mais verbosa
Risco de overflow	Sim (stack limitada)	Não (heap)
Controle	Menos	Total
Performance	Overhead de chamadas	Mais eficiente

Exercícios

Exercício 1: Inverter uma String com Pilha

Implemente uma função inverter_string(s: &str) -> String que usa uma pilha para inverter uma string. Considere caracteres Unicode (como acentos e emojis).

Dica: Empilhe os caracteres e depois desempilhe para construir a string invertida. Compare com o método chars().rev().collect() — qual é mais idiomático em Rust?

Exercício 2: Converter Infixa para Pós-fixa

Estenda o parser do exemplo prático para suportar:

Números negativos (ex: “-5 + 3”)
Funções unárias como sqrt e abs
Variáveis (ex: “x + 2”, onde x é fornecido em um mapa)

Dica: Para números negativos, você pode tratar o - unário como um operador especial durante a tokenização.

Exercício 3: Verificador de Código HTML

Implemente uma função html_balanceado(html: &str) -> bool que verifica se as tags HTML de um trecho estão corretamente aninhadas. Considere tags como <div>, </div>, <p>, </p>, <span>, </span>. Tags auto-fechantes como <br/> e <img/> podem ser ignoradas.

Dica: Empilhe os nomes das tags de abertura. Ao encontrar uma tag de fechamento, verifique se corresponde ao topo da pilha.

Conclusão

A pilha é uma estrutura deceptivamente simples que sustenta alguns dos algoritmos mais importantes da computação. Em Rust, sua implementação é elegante graças ao Vec<T>, que já oferece operações LIFO eficientes nativamente.

Pontos-chave a lembrar:

LIFO — o último a entrar é o primeiro a sair. Essa propriedade é a essência da pilha.
Todas as operações principais são O(1) — empilhar, desempilhar e consultar o topo.
Na prática, use Vec<T> diretamente como pilha — não precisa de wrapper na maioria dos casos.
O algoritmo Shunting-Yard demonstra o poder das pilhas: com apenas uma pilha auxiliar, é possível converter e avaliar expressões matemáticas completas.
A call stack é uma pilha — entender pilhas é entender como o próprio programa executa.
Pilhas explícitas podem substituir recursão, evitando stack overflow em entradas grandes.

Dominar a pilha é essencial para qualquer programador, e entendê-la em Rust reforça conceitos fundamentais de ownership e gerenciamento de memória.