Introdução
Uma fila (queue) é uma estrutura de dados que segue o princípio FIFO (First In, First Out) — o primeiro elemento inserido é o primeiro a ser removido. Filas são fundamentais em programação para processamento de tarefas, buffers de comunicação, BFS em grafos e muito mais.
Nesta receita, você aprenderá diferentes formas de implementar filas em Zig, desde implementações simples até filas circulares eficientes.
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
Fila Simples com ArrayList
A implementação mais direta usa ArrayList como base:
const std = @import("std");
fn Queue(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 enqueue(self: *Self, valor: T) !void {
try self.items.append(valor);
}
pub fn dequeue(self: *Self) ?T {
if (self.items.items.len == 0) return null;
return self.items.orderedRemove(0);
}
pub fn peek(self: *Self) ?T {
if (self.items.items.len == 0) return null;
return self.items.items[0];
}
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 fila = Queue([]const u8).init(allocator);
defer fila.deinit();
// Enfileirar tarefas
try fila.enqueue("Compilar projeto");
try fila.enqueue("Executar testes");
try fila.enqueue("Fazer deploy");
std.debug.print("Tarefas na fila: {d}\n", .{fila.len()});
std.debug.print("Próxima: {s}\n\n", .{fila.peek().?});
// Processar fila
while (fila.dequeue()) |tarefa| {
std.debug.print("Processando: {s}\n", .{tarefa});
}
std.debug.print("\nFila vazia: {}\n", .{fila.isEmpty()});
}
Saída esperada
Tarefas na fila: 3
Próxima: Compilar projeto
Processando: Compilar projeto
Processando: Executar testes
Processando: Fazer deploy
Fila vazia: true
Fila Circular com Buffer Fixo
Para cenários de alta performance sem alocação dinâmica:
const std = @import("std");
fn CircularQueue(comptime T: type, comptime capacity: usize) type {
return struct {
const Self = @This();
buffer: [capacity]T = undefined,
head: usize = 0,
tail: usize = 0,
count: usize = 0,
pub fn init() Self {
return .{};
}
pub fn enqueue(self: *Self, valor: T) !void {
if (self.count == capacity) return error.QueueFull;
self.buffer[self.tail] = valor;
self.tail = (self.tail + 1) % capacity;
self.count += 1;
}
pub fn dequeue(self: *Self) ?T {
if (self.count == 0) return null;
const valor = self.buffer[self.head];
self.head = (self.head + 1) % capacity;
self.count -= 1;
return valor;
}
pub fn peek(self: *Self) ?T {
if (self.count == 0) return null;
return self.buffer[self.head];
}
pub fn len(self: *Self) usize {
return self.count;
}
pub fn isFull(self: *Self) bool {
return self.count == capacity;
}
pub fn isEmpty(self: *Self) bool {
return self.count == 0;
}
};
}
pub fn main() !void {
var fila = CircularQueue(i32, 5).init();
// Enfileirar até o limite
try fila.enqueue(10);
try fila.enqueue(20);
try fila.enqueue(30);
try fila.enqueue(40);
try fila.enqueue(50);
std.debug.print("Fila cheia: {}\n", .{fila.isFull()});
// Tentar adicionar em fila cheia resulta em erro
fila.enqueue(60) catch |err| {
std.debug.print("Erro esperado: {}\n", .{err});
};
// Remover alguns e adicionar novos (circular)
_ = fila.dequeue(); // Remove 10
_ = fila.dequeue(); // Remove 20
try fila.enqueue(60); // Vai para posição 0 (circular)
try fila.enqueue(70); // Vai para posição 1 (circular)
std.debug.print("\nElementos na fila: ", .{});
while (fila.dequeue()) |valor| {
std.debug.print("{d} ", .{valor});
}
std.debug.print("\n", .{});
}
Fila de Prioridade Simples
Fila onde elementos com menor valor saem primeiro:
const std = @import("std");
fn PriorityQueue(comptime T: type) type {
return struct {
const Self = @This();
const Entry = struct {
valor: T,
prioridade: i32,
};
items: std.ArrayList(Entry),
pub fn init(allocator: std.mem.Allocator) Self {
return .{ .items = std.ArrayList(Entry).init(allocator) };
}
pub fn deinit(self: *Self) void {
self.items.deinit();
}
pub fn enqueue(self: *Self, valor: T, prioridade: i32) !void {
try self.items.append(.{ .valor = valor, .prioridade = prioridade });
}
pub fn dequeue(self: *Self) ?T {
if (self.items.items.len == 0) return null;
// Encontrar o item com menor prioridade (maior urgência)
var min_idx: usize = 0;
for (self.items.items, 0..) |item, i| {
if (item.prioridade < self.items.items[min_idx].prioridade) {
min_idx = i;
}
}
const resultado = self.items.orderedRemove(min_idx);
return resultado.valor;
}
pub fn len(self: *Self) usize {
return self.items.items.len;
}
};
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var fila = PriorityQueue([]const u8).init(allocator);
defer fila.deinit();
// Adicionar com prioridades diferentes (menor = mais urgente)
try fila.enqueue("Bug crítico em produção", 1);
try fila.enqueue("Atualizar documentação", 5);
try fila.enqueue("Falha de segurança", 1);
try fila.enqueue("Nova feature", 3);
try fila.enqueue("Refatorar módulo", 4);
std.debug.print("Processando por prioridade:\n", .{});
while (fila.dequeue()) |tarefa| {
std.debug.print(" -> {s}\n", .{tarefa});
}
}
Dicas e Boas Práticas
Escolha a implementação certa: Use fila circular para tamanho fixo e alta performance; use ArrayList para filas de tamanho variável.
orderedRemove(0)é O(n): Para filas com muitos elementos, prefira a fila circular que temdequeueem O(1).Para concorrência: Use atomics ou mutex para filas acessadas por múltiplas threads.
Considere
std.PriorityQueue: A biblioteca padrão tem uma implementação de heap que pode servir como fila de prioridade eficiente.
Receitas Relacionadas
- Implementação de Pilha (Stack) - Estrutura LIFO
- Arrays Dinâmicos com ArrayList - Base para filas
- Operações com Lista Ligada - Alternativa para filas
- Como usar Mutex em Zig - Filas thread-safe