Introdução
Uma pilha (stack) é uma estrutura de dados que segue o princípio LIFO (Last In, First Out) — o último elemento inserido é o primeiro a ser removido. Pilhas são amplamente usadas para controle de chamadas de funções, parsing de expressões, algoritmos de backtracking e undo/redo.
Nesta receita, você aprenderá a implementar pilhas em Zig de diferentes formas e verá aplicações práticas.
Pré-requisitos
- Zig instalado (versão 0.13+). Veja o guia de instalação
- Conhecimento básico de Zig. Consulte a introdução ao Zig
Pilha Dinâmica com ArrayList
A forma mais flexível, com tamanho ilimitado:
const std = @import("std");
fn Stack(comptime T: type) type {
return struct {
const Self = @This();
items: std.ArrayList(T),
pub fn init(allocator: std.mem.Allocator) Self {
return .{ .items = std.ArrayList(T).init(allocator) };
}
pub fn deinit(self: *Self) void {
self.items.deinit();
}
pub fn push(self: *Self, valor: T) !void {
try self.items.append(valor);
}
pub fn pop(self: *Self) ?T {
return self.items.popOrNull();
}
pub fn peek(self: *Self) ?T {
if (self.items.items.len == 0) return null;
return self.items.items[self.items.items.len - 1];
}
pub fn len(self: *Self) usize {
return self.items.items.len;
}
pub fn isEmpty(self: *Self) bool {
return self.items.items.len == 0;
}
};
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var pilha = Stack(i32).init(allocator);
defer pilha.deinit();
// Empilhar valores
try pilha.push(10);
try pilha.push(20);
try pilha.push(30);
std.debug.print("Topo: {d}\n", .{pilha.peek().?});
std.debug.print("Tamanho: {d}\n\n", .{pilha.len()});
// Desempilhar
while (pilha.pop()) |valor| {
std.debug.print("Pop: {d}\n", .{valor});
}
std.debug.print("\nPilha vazia: {}\n", .{pilha.isEmpty()});
}
Saída esperada
Topo: 30
Tamanho: 3
Pop: 30
Pop: 20
Pop: 10
Pilha vazia: true
Pilha com Buffer Fixo (Sem Alocação)
Para cenários onde o tamanho máximo é conhecido:
const std = @import("std");
fn FixedStack(comptime T: type, comptime max_size: usize) type {
return struct {
const Self = @This();
buffer: [max_size]T = undefined,
count: usize = 0,
pub fn init() Self {
return .{};
}
pub fn push(self: *Self, valor: T) !void {
if (self.count == max_size) return error.StackOverflow;
self.buffer[self.count] = valor;
self.count += 1;
}
pub fn pop(self: *Self) ?T {
if (self.count == 0) return null;
self.count -= 1;
return self.buffer[self.count];
}
pub fn peek(self: *Self) ?T {
if (self.count == 0) return null;
return self.buffer[self.count - 1];
}
pub fn len(self: *Self) usize {
return self.count;
}
pub fn isEmpty(self: *Self) bool {
return self.count == 0;
}
pub fn items(self: *Self) []T {
return self.buffer[0..self.count];
}
};
}
pub fn main() !void {
var pilha = FixedStack(u8, 10).init();
// Empilhar caracteres
const texto = "Zig";
for (texto) |c| {
try pilha.push(c);
}
// Desempilhar inverte a string
std.debug.print("Invertido: ", .{});
while (pilha.pop()) |c| {
std.debug.print("{c}", .{c});
}
std.debug.print("\n", .{});
}
Aplicação Prática: Validar Parênteses
Um dos usos clássicos de pilhas — verificar se uma expressão tem parênteses balanceados:
const std = @import("std");
fn validarParenteses(allocator: std.mem.Allocator, expressao: []const u8) !bool {
var pilha = std.ArrayList(u8).init(allocator);
defer pilha.deinit();
for (expressao) |c| {
switch (c) {
'(', '[', '{' => try pilha.append(c),
')' => {
const topo = pilha.popOrNull() orelse return false;
if (topo != '(') return false;
},
']' => {
const topo = pilha.popOrNull() orelse return false;
if (topo != '[') return false;
},
'}' => {
const topo = pilha.popOrNull() orelse return false;
if (topo != '{') return false;
},
else => {},
}
}
return pilha.items.len == 0;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const testes = [_][]const u8{
"(a + b) * [c - d]",
"{[()]}",
"(()",
"({[}])",
"",
"a + b",
};
for (&testes) |expr| {
const valido = try validarParenteses(allocator, expr);
const status = if (valido) "valido" else "INVALIDO";
std.debug.print("\"{s}\" -> {s}\n", .{ expr, status });
}
}
Saída esperada
"(a + b) * [c - d]" -> valido
"{[()]}" -> valido
"(()" -> INVALIDO
"({[}])" -> INVALIDO
"" -> valido
"a + b" -> valido
Aplicação Prática: Converter Decimal para Binário
const std = @import("std");
fn decimalParaBinario(allocator: std.mem.Allocator, numero: u64) ![]u8 {
var pilha = std.ArrayList(u8).init(allocator);
defer pilha.deinit();
if (numero == 0) {
var resultado = try allocator.alloc(u8, 1);
resultado[0] = '0';
return resultado;
}
var n = numero;
while (n > 0) {
const bit: u8 = @intCast(n % 2);
try pilha.append('0' + bit);
n /= 2;
}
// Inverter (desempilhar para resultado)
var resultado = try allocator.alloc(u8, pilha.items.len);
var i: usize = 0;
while (pilha.popOrNull()) |c| {
resultado[i] = c;
i += 1;
}
return resultado;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const numeros = [_]u64{ 0, 1, 10, 42, 255, 1024 };
for (&numeros) |n| {
const binario = try decimalParaBinario(allocator, n);
defer allocator.free(binario);
std.debug.print("{d} -> {s}\n", .{ n, binario });
}
}
Dicas e Boas Práticas
Use
ArrayList.popOrNull(): Em Zig,ArrayListjá se comporta como uma pilha no final da lista, entãoappend+popOrNullé muito eficiente (O(1)).Prefira buffer fixo quando possível: Se o tamanho máximo é conhecido,
FixedStackevita alocação dinâmica.Cuidado com stack overflow: Em pilhas com buffer fixo, sempre trate o erro quando a pilha estiver cheia.
errdeferpara segurança: Ao alocar dentro de funções, useerrdefer pilha.deinit()para liberar memória em caso de erro.
Receitas Relacionadas
- Implementação de Fila (Queue) - Estrutura FIFO
- Arrays Dinâmicos com ArrayList - Base para pilhas
- Converter entre Bases Numéricas - Conversão com pilhas
- Try/Catch e Tratamento de Erros - Erros em pilhas