pushFrente(5)     pushTras(8)     pushFrente(2)
                 ↓                ↓                ↓
Frente →    +---+           +---+---+       +---+---+---+
            | 5 |           | 5 | 8 |       | 2 | 5 | 8 |
            +---+           +---+---+       +---+---+---+    ← Trás

popFrente()→2    popTras()→8
    +---+---+       +---+
    | 5 | 8 |       | 5 |
    +---+---+       +---+

Buffer circular:
  Capacidade: 6
  +---+---+---+---+---+---+
  | 8 |   |   | 2 | 5 | 3 |   frente=3, trás=1
  +---+---+---+---+---+---+
    ↑               ↑
   trás           frente

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

/// Deque genérico baseado em buffer circular.
pub fn Deque(comptime T: type) type {
    return struct {
        const Self = @This();

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

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

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

        /// Insere na frente — O(1) amortizado.
        pub fn pushFrente(self: *Self, valor: T) !void {
            if (self.tamanho_atual == self.capacidade) try self.redimensionar();
            self.frente = if (self.frente == 0) self.capacidade - 1 else self.frente - 1;
            self.buffer[self.frente] = valor;
            self.tamanho_atual += 1;
        }

        /// Insere atrás — O(1) amortizado.
        pub fn pushTras(self: *Self, valor: T) !void {
            if (self.tamanho_atual == self.capacidade) try self.redimensionar();
            const tras = (self.frente + self.tamanho_atual) % self.capacidade;
            self.buffer[tras] = valor;
            self.tamanho_atual += 1;
        }

        /// Remove da frente — O(1).
        pub fn popFrente(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;
        }

        /// Remove de trás — O(1).
        pub fn popTras(self: *Self) ?T {
            if (self.tamanho_atual == 0) return null;
            self.tamanho_atual -= 1;
            const tras = (self.frente + self.tamanho_atual) % self.capacidade;
            return self.buffer[tras];
        }

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

        /// Consulta a traseira — O(1).
        pub fn peekTras(self: *const Self) ?T {
            if (self.tamanho_atual == 0) return null;
            const tras = (self.frente + self.tamanho_atual - 1) % self.capacidade;
            return self.buffer[tras];
        }

        /// Acesso por índice (0 = frente) — O(1).
        pub fn get(self: *const Self, indice: usize) ?T {
            if (indice >= self.tamanho_atual) return null;
            return self.buffer[(self.frente + indice) % self.capacidade];
        }

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

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

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

            for (0..self.tamanho_atual) |i| {
                novo[i] = self.buffer[(self.frente + i) % self.capacidade];
            }

            self.allocator.free(self.buffer);
            self.buffer = novo;
            self.frente = 0;
            self.capacidade = nova_cap;
        }
    };
}

/// Exemplo: máximo em janela deslizante usando Deque.
pub fn maximoJanela(allocator: Allocator, arr: []const i32, k: usize) ![]i32 {
    if (arr.len < k) return try allocator.alloc(i32, 0);

    var resultado = try allocator.alloc(i32, arr.len - k + 1);
    var dq = try Deque(usize).init(allocator);
    defer dq.deinit();

    for (0..arr.len) |i| {
        // Remove índices fora da janela
        while (!dq.vazio()) {
            if (dq.peekFrente().? + k <= i) {
                _ = dq.popFrente();
            } else break;
        }
        // Remove menores que o atual
        while (!dq.vazio()) {
            if (arr[dq.peekTras().?] <= arr[i]) {
                _ = dq.popTras();
            } else break;
        }
        try dq.pushTras(i);

        if (i >= k - 1) {
            resultado[i - k + 1] = arr[dq.peekFrente().?];
        }
    }
    return resultado;
}

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

    var dq = try Deque(i32).init(allocator);
    defer dq.deinit();

    // Operações
    try dq.pushTras(10);
    try dq.pushTras(20);
    try dq.pushFrente(5);
    try dq.pushTras(30);
    try dq.pushFrente(1);

    try stdout.print("Deque: ", .{});
    for (0..dq.tamanho()) |i| {
        try stdout.print("{?d} ", .{dq.get(i)});
    }
    try stdout.print("\n", .{});

    try stdout.print("Frente: {?d}\n", .{dq.peekFrente()});
    try stdout.print("Trás: {?d}\n", .{dq.peekTras()});
    try stdout.print("Pop frente: {?d}\n", .{dq.popFrente()});
    try stdout.print("Pop trás: {?d}\n", .{dq.popTras()});

    // Máximo em janela
    try stdout.print("\n=== Máximo em janela ===\n", .{});
    const arr = [_]i32{ 1, 3, -1, -3, 5, 3, 6, 7 };
    const maxs = try maximoJanela(allocator, &arr, 3);
    defer allocator.free(maxs);
    try stdout.print("Máximos (janela 3): ", .{});
    for (maxs) |m| try stdout.print("{d} ", .{m});
    try stdout.print("\n", .{});
}