enqueue(5)  enqueue(8)  enqueue(3)  dequeue()→5  enqueue(1)

  frente         trás
    ↓              ↓
  +---+---+---+---+---+
  | 5 | 8 | 3 |   |   |     Fila linear: desperdício de espaço
  +---+---+---+---+---+

Fila circular (ring buffer):
  Capacidade: 4

    +---+---+---+---+
    | 5 | 8 | 3 |   |    frente=0, trás=3
    +---+---+---+---+

  dequeue() → 5:
    +---+---+---+---+
    |   | 8 | 3 |   |    frente=1, trás=3
    +---+---+---+---+

  enqueue(1), enqueue(7):
    +---+---+---+---+
    | 7 | 8 | 3 | 1 |    frente=1, trás=1 (wraparound!)
    +---+---+---+---+

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Fila circular genérica.
pub fn Fila(comptime T: type) type {
    return struct {
        const Self = @This();

        buffer: []T,
        frente: usize,
        tras: usize,
        tamanho_atual: usize,
        capacidade: usize,
        allocator: Allocator,

        pub fn init(allocator: Allocator, capacidade: usize) !Self {
            const cap = if (capacidade == 0) 4 else capacidade;
            return .{
                .buffer = try allocator.alloc(T, cap),
                .frente = 0,
                .tras = 0,
                .tamanho_atual = 0,
                .capacidade = cap,
                .allocator = allocator,
            };
        }

        pub fn deinit(self: *Self) void {
            self.allocator.free(self.buffer);
        }

        /// Adiciona ao final da fila — O(1) amortizado.
        pub fn enqueue(self: *Self, valor: T) !void {
            if (self.tamanho_atual == self.capacidade) {
                try self.redimensionar();
            }
            self.buffer[self.tras] = valor;
            self.tras = (self.tras + 1) % self.capacidade;
            self.tamanho_atual += 1;
        }

        /// Remove e retorna o primeiro da fila — O(1).
        pub fn dequeue(self: *Self) ?T {
            if (self.tamanho_atual == 0) return null;
            const valor = self.buffer[self.frente];
            self.frente = (self.frente + 1) % self.capacidade;
            self.tamanho_atual -= 1;
            return valor;
        }

        /// Consulta o primeiro sem remover — O(1).
        pub fn frente_val(self: *const Self) ?T {
            if (self.tamanho_atual == 0) return null;
            return self.buffer[self.frente];
        }

        /// Consulta o último sem remover — O(1).
        pub fn tras_val(self: *const Self) ?T {
            if (self.tamanho_atual == 0) return null;
            const idx = if (self.tras == 0) self.capacidade - 1 else self.tras - 1;
            return self.buffer[idx];
        }

        pub fn vazia(self: *const Self) bool {
            return self.tamanho_atual == 0;
        }

        pub fn tamanho(self: *const Self) usize {
            return self.tamanho_atual;
        }

        fn redimensionar(self: *Self) !void {
            const nova_cap = self.capacidade * 2;
            const novo_buffer = try self.allocator.alloc(T, nova_cap);

            // Copia elementos na ordem correta
            for (0..self.tamanho_atual) |i| {
                novo_buffer[i] = self.buffer[(self.frente + i) % self.capacidade];
            }

            self.allocator.free(self.buffer);
            self.buffer = novo_buffer;
            self.frente = 0;
            self.tras = self.tamanho_atual;
            self.capacidade = nova_cap;
        }
    };
}

/// Fila de prioridade simples (min-heap).
pub fn FilaPrioridade(comptime T: type) type {
    return struct {
        const Self = @This();

        items: std.ArrayList(T),
        comptime lessThan: fn (T, T) bool,

        pub fn init(allocator: Allocator, comptime cmp: fn (T, T) bool) Self {
            return .{
                .items = std.ArrayList(T).init(allocator),
                .lessThan = cmp,
            };
        }

        pub fn deinit(self: *Self) void {
            self.items.deinit();
        }

        pub fn inserir(self: *Self, valor: T) !void {
            try self.items.append(valor);
            self.subirHeap(self.items.items.len - 1);
        }

        pub fn removerMin(self: *Self) ?T {
            if (self.items.items.len == 0) return null;
            const min = self.items.items[0];
            const ultimo = self.items.items.len - 1;
            self.items.items[0] = self.items.items[ultimo];
            _ = self.items.pop();
            if (self.items.items.len > 0) self.descerHeap(0);
            return min;
        }

        fn subirHeap(self: *Self, idx: usize) void {
            var i = idx;
            while (i > 0) {
                const pai = (i - 1) / 2;
                if (self.lessThan(self.items.items[i], self.items.items[pai])) {
                    std.mem.swap(T, &self.items.items[i], &self.items.items[pai]);
                    i = pai;
                } else break;
            }
        }

        fn descerHeap(self: *Self, idx: usize) void {
            var i = idx;
            const n = self.items.items.len;
            while (true) {
                var menor = i;
                const esq = 2 * i + 1;
                const dir = 2 * i + 2;
                if (esq < n and self.lessThan(self.items.items[esq], self.items.items[menor]))
                    menor = esq;
                if (dir < n and self.lessThan(self.items.items[dir], self.items.items[menor]))
                    menor = dir;
                if (menor == i) break;
                std.mem.swap(T, &self.items.items[i], &self.items.items[menor]);
                i = menor;
            }
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Fila circular
    var fila = try Fila(i32).init(allocator, 4);
    defer fila.deinit();

    try fila.enqueue(10);
    try fila.enqueue(20);
    try fila.enqueue(30);

    try stdout.print("Frente: {?d}\n", .{fila.frente_val()});
    try stdout.print("Dequeue: {?d}\n", .{fila.dequeue()});
    try stdout.print("Dequeue: {?d}\n", .{fila.dequeue()});

    try fila.enqueue(40);
    try fila.enqueue(50);

    try stdout.print("Tamanho: {d}\n", .{fila.tamanho()});
    while (fila.dequeue()) |v| {
        try stdout.print("  {d}\n", .{v});
    }

    // Fila de prioridade
    try stdout.print("\n=== Fila de Prioridade ===\n", .{});
    var fp = FilaPrioridade(i32).init(allocator, struct {
        fn f(a: i32, b: i32) bool {
            return a < b;
        }
    }.f);
    defer fp.deinit();

    for ([_]i32{ 30, 10, 50, 20, 40 }) |v| try fp.inserir(v);
    try stdout.print("Ordem de saída (min primeiro): ", .{});
    while (fp.removerMin()) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});
}