Deque: Fila de Duas Pontas em Rust

Introdução

O Deque (pronuncia-se “deck”), abreviação de Double-Ended Queue (fila de duas pontas), é uma estrutura de dados que generaliza tanto a pilha quanto a fila. Ele permite inserção e remoção eficientes em ambas as extremidades — frente e trás — em tempo O(1).

Essa versatilidade faz do Deque uma estrutura extremamente poderosa. Você pode usá-lo como pilha (operando apenas na trás), como fila (inserindo na trás e removendo da frente), ou como ambos simultaneamente. Em Rust, o VecDeque<T> da biblioteca padrão implementa um Deque usando um buffer circular (ring buffer), combinando a eficiência de operações em ambas as pontas com a localidade de cache de um array contíguo.

O Deque brilha especialmente em algoritmos de janela deslizante (sliding window), uma técnica fundamental em processamento de sinais, análise de séries temporais e uma categoria inteira de problemas de entrevistas técnicas. Neste artigo, exploraremos a teoria, a implementação interna e resolveremos o clássico problema do “máximo em janela deslizante”.

Conceito e Teoria

Operações do Deque

  Deque — operações em ambas as extremidades:

  push_front(5)                              push_back(40)
       │                                          │
       ▼                                          ▼
  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
  │  (novo)  │  │   10    │  │   20    │  │   30    │
  │    5     │──│         │──│         │──│         │
  └─────────┘  └─────────┘  └─────────┘  └─────────┘
       ▲                                          ▲
       │                                          │
  pop_front()                              pop_back()
  retorna 5                                retorna 30


  Como PILHA (operando na trás):     Como FILA (entra trás, sai frente):
  push_back → empilhar               push_back → enfileirar
  pop_back  → desempilhar            pop_front → desenfileirar

  Como PILHA (operando na frente):   Como FILA inversa:
  push_front → empilhar              push_front → enfileirar
  pop_front  → desempilhar           pop_back   → desenfileirar

Internals do VecDeque: Buffer Circular

O VecDeque implementa um buffer circular alocado na heap:

  VecDeque com capacidade 8, contendo [10, 20, 30, 40, 50]:

  Caso normal (sem wrap-around):
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │     │ 10  │ 20  │ 30  │ 40  │ 50  │     │     │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
    [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
            ▲                        ▲
          head=1                   tail=6 (próx. posição livre)


  Após push_front(5) e push_front(0) — wrap-around:
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  5  │ 10  │ 20  │ 30  │ 40  │ 50  │     │  0  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
    [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
                                          ▲     ▲
                                        tail  head=7

  Ordem lógica: [0, 5, 10, 20, 30, 40, 50]
  Leitura: head(7) → 0 → 1 → 2 → 3 → 4 → 5 → tail(6)

  Fórmula: índice_real = (head + índice_lógico) % capacidade

Visualização da Circularidade

  Representação circular do buffer:

           [0]
          ╱     ╲
       [7]       [1]
       │   ┌───┐   │
    [6]│   │VDQ│   │[2]
       │   └───┘   │
       [5]       [3]
          ╲     ╱
           [4]

  Com head=7 e 7 elementos:
           [0]=5
          ╱     ╲
   [7]=0 ●       ● [1]=10
       │   ┌───┐   │
    [6]│   │   │   │[2]=20
       │   └───┘   │
   [5]=50●       ● [3]=30
          ╲     ╱
           [4]=40

  Sentido de leitura: head(7) → 0 → 1 → 2 → 3 → 4 → 5
  push_front: head se move para trás (anti-horário)
  push_back:  tail se move para frente (horário)

Complexidade

Operação	VecDeque	Vec	LinkedList
`push_front(val)`	O(1) amortizado	O(n)	O(1)
`push_back(val)`	O(1) amortizado	O(1) amortizado	O(1)
`pop_front()`	O(1)	O(n)	O(1)
`pop_back()`	O(1)	O(1)	O(1)
Acesso por índice `[i]`	O(1)	O(1)	O(n)
Busca (`contains`)	O(n)	O(n)	O(n)
Inserção no meio	O(n)	O(n)	O(1)*
Remoção do meio	O(n)	O(n)	O(1)*
`make_contiguous()`	O(n)	—	—
Espaço	O(n)	O(n)	O(n) + ponteiros

*O(1) se já tiver o ponteiro para o nó. Encontrar o nó é O(n).

Implementação em Rust

Operações Básicas com VecDeque

use std::collections::VecDeque;

fn demonstrar_deque_basico() {
    // Criação
    let mut deque: VecDeque<i32> = VecDeque::new();

    // Inserções na frente e atrás
    deque.push_back(10);     // [10]
    deque.push_back(20);     // [10, 20]
    deque.push_front(5);     // [5, 10, 20]
    deque.push_back(30);     // [5, 10, 20, 30]
    deque.push_front(1);     // [1, 5, 10, 20, 30]

    println!("Deque: {:?}", deque);
    println!("Tamanho: {}", deque.len());

    // Acesso por índice
    println!("deque[0] = {}", deque[0]); // 1
    println!("deque[2] = {}", deque[2]); // 10

    // Espiar extremidades
    println!("Frente: {:?}", deque.front()); // Some(1)
    println!("Trás: {:?}", deque.back());    // Some(30)

    // Remoções
    let da_frente = deque.pop_front(); // Some(1)
    let de_tras = deque.pop_back();    // Some(30)
    println!("Removido da frente: {:?}", da_frente);
    println!("Removido de trás: {:?}", de_tras);
    println!("Deque restante: {:?}", deque); // [5, 10, 20]

    // Iteração
    println!("\nIterando:");
    for (i, val) in deque.iter().enumerate() {
        println!("  [{}] = {}", i, val);
    }

    // Converter para Vec (contíguo)
    let como_vec: Vec<i32> = deque.iter().copied().collect();
    println!("Como Vec: {:?}", como_vec);
}

fn main() {
    demonstrar_deque_basico();
}

Deque Como Pilha e Como Fila

use std::collections::VecDeque;

/// Demonstra o uso do VecDeque como pilha (LIFO)
fn usar_como_pilha() {
    println!("═══ VecDeque como Pilha (LIFO) ═══\n");

    let mut pilha: VecDeque<&str> = VecDeque::new();

    // Empilhar (push_back)
    pilha.push_back("primeiro");
    pilha.push_back("segundo");
    pilha.push_back("terceiro");

    // Desempilhar (pop_back) — sai na ordem inversa
    while let Some(valor) = pilha.pop_back() {
        println!("  Desempilhado: {}", valor);
    }
    // Saída: terceiro, segundo, primeiro
}

/// Demonstra o uso do VecDeque como fila (FIFO)
fn usar_como_fila() {
    println!("\n═══ VecDeque como Fila (FIFO) ═══\n");

    let mut fila: VecDeque<&str> = VecDeque::new();

    // Enfileirar (push_back)
    fila.push_back("primeiro");
    fila.push_back("segundo");
    fila.push_back("terceiro");

    // Desenfileirar (pop_front) — sai na ordem de chegada
    while let Some(valor) = fila.pop_front() {
        println!("  Desenfileirado: {}", valor);
    }
    // Saída: primeiro, segundo, terceiro
}

/// Demonstra operações mistas (deque verdadeiro)
fn usar_como_deque() {
    println!("\n═══ VecDeque como Deque (ambas as pontas) ═══\n");

    let mut deque: VecDeque<i32> = VecDeque::new();

    // Inserções alternadas
    deque.push_back(3);     // [3]
    deque.push_front(2);    // [2, 3]
    deque.push_back(4);     // [2, 3, 4]
    deque.push_front(1);    // [1, 2, 3, 4]
    deque.push_back(5);     // [1, 2, 3, 4, 5]
    deque.push_front(0);    // [0, 1, 2, 3, 4, 5]

    println!("  Deque: {:?}", deque);

    // Remoções alternadas
    println!("  pop_front: {:?}", deque.pop_front()); // 0
    println!("  pop_back:  {:?}", deque.pop_back());  // 5
    println!("  pop_front: {:?}", deque.pop_front()); // 1
    println!("  pop_back:  {:?}", deque.pop_back());  // 4
    println!("  Restante: {:?}", deque);              // [2, 3]
}

fn main() {
    usar_como_pilha();
    usar_como_fila();
    usar_como_deque();
}

Métodos Avançados do VecDeque

use std::collections::VecDeque;

fn metodos_avancados() {
    let mut deque: VecDeque<i32> = VecDeque::from(vec![1, 2, 3, 4, 5, 6, 7, 8]);

    println!("Original: {:?}\n", deque);

    // swap — troca dois elementos por índice
    deque.swap(0, 7);
    println!("Após swap(0, 7): {:?}", deque);
    deque.swap(0, 7); // desfaz

    // rotate_left — rotaciona para a esquerda
    let mut rotacionado = deque.clone();
    rotacionado.rotate_left(3);
    println!("rotate_left(3): {:?}", rotacionado);
    // [4, 5, 6, 7, 8, 1, 2, 3]

    // rotate_right — rotaciona para a direita
    let mut rotacionado = deque.clone();
    rotacionado.rotate_right(2);
    println!("rotate_right(2): {:?}", rotacionado);
    // [7, 8, 1, 2, 3, 4, 5, 6]

    // split_off — divide em dois deques
    let mut parte1 = deque.clone();
    let parte2 = parte1.split_off(4);
    println!("\nsplit_off(4):");
    println!("  Parte 1: {:?}", parte1); // [1, 2, 3, 4]
    println!("  Parte 2: {:?}", parte2); // [5, 6, 7, 8]

    // append — junta dois deques
    let mut combinado = VecDeque::from(vec![10, 20]);
    let mut extra = VecDeque::from(vec![30, 40]);
    combinado.append(&mut extra);
    println!("\nAppend: {:?} (extra agora vazio: {:?})", combinado, extra);

    // retain — filtra in-place
    let mut numeros = VecDeque::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    numeros.retain(|&x| x % 2 == 0);
    println!("\nretain(pares): {:?}", numeros);

    // drain — remove um intervalo e retorna iterador
    let mut dados = VecDeque::from(vec![10, 20, 30, 40, 50]);
    let drenados: Vec<i32> = dados.drain(1..4).collect();
    println!("\ndrain(1..4): removidos = {:?}, restante = {:?}", drenados, dados);

    // make_contiguous — garante memória contígua, retorna &mut [T]
    let mut deque = VecDeque::from(vec![1, 2, 3]);
    deque.push_front(0); // pode causar wrap-around
    let fatia: &mut [i32] = deque.make_contiguous();
    println!("\nmake_contiguous: {:?}", fatia);

    // binary_search — busca binária (requer ordenação)
    let deque_ord = VecDeque::from(vec![2, 5, 8, 12, 15, 20]);
    match deque_ord.binary_search(&12) {
        Ok(indice) => println!("\nbinary_search(12): encontrado no índice {}", indice),
        Err(indice) => println!("\nbinary_search(12): não encontrado, inserir em {}", indice),
    }
}

fn main() {
    metodos_avancados();
}

Métodos Principais

Método	Complexidade	Descrição
`VecDeque::new()`	O(1)	Cria um deque vazio
`VecDeque::with_capacity(n)`	O(1)	Cria com capacidade pré-alocada
`push_front(val)`	O(1) amortizado	Insere na frente
`push_back(val)`	O(1) amortizado	Insere na trás
`pop_front()`	O(1)	Remove e retorna da frente
`pop_back()`	O(1)	Remove e retorna de trás
`front()` / `back()`	O(1)	Referência à frente/trás sem remover
`get(i)`	O(1)	Acesso por índice (retorna `Option`)
`swap(i, j)`	O(1)	Troca dois elementos
`rotate_left(n)`	O(n)	Rotaciona n posições para a esquerda
`rotate_right(n)`	O(n)	Rotaciona n posições para a direita
`split_off(at)`	O(n)	Divide em dois deques na posição
`append(other)`	O(n)	Move todos de `other` para o final
`retain(f)`	O(n)	Remove elementos que não satisfazem `f`
`drain(range)`	O(n)	Remove e retorna iterador sobre intervalo
`make_contiguous()`	O(n)	Reorganiza para memória contígua
`binary_search(val)`	O(log n)	Busca binária (requer deque ordenado)
`contains(val)`	O(n)	Busca linear
`iter()` / `iter_mut()`	O(1)	Iteradores por referência
`len()` / `is_empty()`	O(1)	Tamanho e verificação de vazio

Exemplo Prático: Máximo em Janela Deslizante

Este é um problema clássico de entrevistas e competições de programação: dado um array de inteiros e um tamanho de janela k, encontre o valor máximo em cada posição da janela conforme ela desliza pelo array.

A solução ingênua (verificar todos os k elementos em cada posição) custa O(n*k). Usando um Deque monotônico, resolvemos em O(n).

use std::collections::VecDeque;
use std::fmt;

/// Resultado de uma janela com sua posição e elementos
#[derive(Debug)]
struct ResultadoJanela {
    posicao_inicio: usize,
    elementos: Vec<i32>,
    maximo: i32,
}

impl fmt::Display for ResultadoJanela {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "  posição [{:>2}..{:>2}]: {:>15?} → máximo = {}",
            self.posicao_inicio,
            self.posicao_inicio + self.elementos.len(),
            self.elementos,
            self.maximo
        )
    }
}

/// Encontra o máximo em cada janela deslizante de tamanho k — O(n)
///
/// Algoritmo do Deque Monotônico:
///   - Mantemos um deque com ÍNDICES dos elementos
///   - O deque é mantido em ordem DECRESCENTE de valores
///   - O elemento da frente do deque é sempre o máximo da janela atual
///   - Ao inserir um novo elemento, removemos de trás todos que são menores
///   - Ao avançar a janela, removemos da frente índices que saíram da janela
///
/// Visualização do processo:
///
///   nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
///
///   i=0: deque=[0]         nums[0]=1   janela incompleta
///   i=1: deque=[1]         nums[1]=3   janela incompleta (1 < 3, remove 0)
///   i=2: deque=[1, 2]      nums[2]=-1  janela [1,3,-1] máx=3
///   i=3: deque=[1, 3]      nums[3]=-3  janela [3,-1,-3] máx=3
///   i=4: deque=[4]         nums[4]=5   janela [-1,-3,5] máx=5
///   i=5: deque=[4, 5]      nums[5]=3   janela [-3,5,3] máx=5
///   i=6: deque=[6]         nums[6]=6   janela [5,3,6] máx=6
///   i=7: deque=[7]         nums[7]=7   janela [3,6,7] máx=7
fn maximo_janela_deslizante(nums: &[i32], k: usize) -> Vec<ResultadoJanela> {
    if nums.is_empty() || k == 0 || k > nums.len() {
        return Vec::new();
    }

    let mut resultados: Vec<ResultadoJanela> = Vec::new();

    // Deque monotônico: armazena ÍNDICES, não valores
    // Invariante: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[n]]
    let mut deque: VecDeque<usize> = VecDeque::new();

    for i in 0..nums.len() {
        // Remove índices que saíram da janela (estão muito à esquerda)
        while let Some(&frente) = deque.front() {
            if frente + k <= i {
                deque.pop_front();
            } else {
                break;
            }
        }

        // Remove de trás todos os índices cujos valores são menores que nums[i]
        // Isso mantém o deque monotonicamente decrescente
        while let Some(&tras) = deque.back() {
            if nums[tras] <= nums[i] {
                deque.pop_back();
            } else {
                break;
            }
        }

        // Adiciona o índice atual
        deque.push_back(i);

        // A janela está completa a partir de i >= k - 1
        if i >= k - 1 {
            let inicio = i + 1 - k;
            let maximo = nums[*deque.front().unwrap()];
            let elementos: Vec<i32> = nums[inicio..=i].to_vec();

            resultados.push(ResultadoJanela {
                posicao_inicio: inicio,
                elementos,
                maximo,
            });
        }
    }

    resultados
}

/// Versão com mínimo (para comparação)
fn minimo_janela_deslizante(nums: &[i32], k: usize) -> Vec<i32> {
    if nums.is_empty() || k == 0 || k > nums.len() {
        return Vec::new();
    }

    let mut resultado = Vec::new();
    let mut deque: VecDeque<usize> = VecDeque::new();

    for i in 0..nums.len() {
        // Remove índices fora da janela
        while let Some(&frente) = deque.front() {
            if frente + k <= i {
                deque.pop_front();
            } else {
                break;
            }
        }

        // Mantém deque monotonicamente CRESCENTE (para mínimo)
        while let Some(&tras) = deque.back() {
            if nums[tras] >= nums[i] {
                deque.pop_back();
            } else {
                break;
            }
        }

        deque.push_back(i);

        if i >= k - 1 {
            resultado.push(nums[*deque.front().unwrap()]);
        }
    }

    resultado
}

/// Aplicação prática: análise de séries temporais de preços de ações
fn analisar_acoes() {
    println!("\n═══ Análise de Ações — Máximos e Mínimos Móveis ═══\n");

    // Preços de fechamento simulados (em centavos para usar i32)
    let precos: Vec<i32> = vec![
        10050, 10120, 10080, 10200, 10150, 10300, 10250, 10400,
        10380, 10350, 10500, 10450, 10600, 10550, 10700,
    ];

    let dias = vec![
        "01/Jan", "02/Jan", "03/Jan", "04/Jan", "05/Jan",
        "06/Jan", "07/Jan", "08/Jan", "09/Jan", "10/Jan",
        "11/Jan", "12/Jan", "13/Jan", "14/Jan", "15/Jan",
    ];

    let janela = 5; // janela de 5 dias (semana de negociação)

    println!("Preços diários (em centavos):");
    for (i, (&preco, dia)) in precos.iter().zip(dias.iter()).enumerate() {
        println!("  {}: {} → R$ {:.2}", dia, i, preco as f64 / 100.0);
    }

    println!("\nMáximos em janela de {} dias:", janela);
    let maximos = maximo_janela_deslizante(&precos, janela);
    for resultado in &maximos {
        let dia_inicio = dias[resultado.posicao_inicio];
        let dia_fim = dias[resultado.posicao_inicio + janela - 1];
        println!(
            "  {} a {}: máx = R$ {:.2}",
            dia_inicio, dia_fim,
            resultado.maximo as f64 / 100.0
        );
    }

    println!("\nMínimos em janela de {} dias:", janela);
    let minimos = minimo_janela_deslizante(&precos, janela);
    for (i, &min) in minimos.iter().enumerate() {
        let dia_inicio = dias[i];
        let dia_fim = dias[i + janela - 1];
        println!(
            "  {} a {}: mín = R$ {:.2}",
            dia_inicio, dia_fim,
            min as f64 / 100.0
        );
    }

    // Calcular a amplitude (máx - mín) de cada janela
    println!("\nAmplitude (volatilidade) por janela:");
    for (i, (&max, &min)) in maximos.iter()
        .map(|r| &r.maximo)
        .zip(minimos.iter())
        .enumerate()
    {
        let amplitude = max - min;
        let dia_inicio = dias[i];
        let dia_fim = dias[i + janela - 1];
        println!(
            "  {} a {}: R$ {:.2} (variação de {:.1}%)",
            dia_inicio, dia_fim,
            amplitude as f64 / 100.0,
            (amplitude as f64 / min as f64) * 100.0
        );
    }
}

fn main() {
    println!("═══ Máximo em Janela Deslizante ═══\n");

    let nums = vec![1, 3, -1, -3, 5, 3, 6, 7];
    let k = 3;

    println!("Array: {:?}", nums);
    println!("Tamanho da janela: {}\n", k);

    let resultados = maximo_janela_deslizante(&nums, k);
    for resultado in &resultados {
        println!("{}", resultado);
    }

    // Análise de preços de ações
    analisar_acoes();

    // Demonstração com dados maiores
    println!("\n═══ Teste de Performance ═══\n");
    let grande: Vec<i32> = (0..1_000_000).map(|i| (i * 7 + 13) % 100_000).collect();
    let k_grande = 1000;

    let inicio = std::time::Instant::now();
    let resultado = maximo_janela_deslizante(&grande, k_grande);
    let duracao = inicio.elapsed();

    println!(
        "Array de {} elementos, janela de {}:",
        grande.len(), k_grande
    );
    println!("  Resultados: {} janelas", resultado.len());
    println!("  Tempo: {:?}", duracao);
    println!(
        "  Primeiro máximo: {}, Último máximo: {}",
        resultado.first().map(|r| r.maximo).unwrap_or(0),
        resultado.last().map(|r| r.maximo).unwrap_or(0),
    );
}

Comparação com Outras Estruturas

Critério	VecDeque	Vec	LinkedList	BinaryHeap
push_front	O(1)*	O(n)	O(1)	—
push_back	O(1)*	O(1)*	O(1)	O(log n)
pop_front	O(1)	O(n)	O(1)	—
pop_back	O(1)	O(1)	O(1)	O(log n)
Acesso por índice	O(1)	O(1)	O(n)	—
Cache-friendly	Sim	Sim	Nao	Sim
Uso como Pilha	Sim	Sim (melhor)	Sim	Nao
Uso como Fila	Sim (melhor)	Nao (O(n))	Sim	Nao
Uso como Deque	Sim (melhor)	Nao	Sim (lento)	Nao
Uso para Prioridade	Nao	Nao	Nao	Sim (melhor)

*O(1) amortizado. Pode ser O(n) quando precisa realocar o buffer.

Quando Usar VecDeque?

Precisa de fila FIFO eficiente — push_back + pop_front.
Precisa de operações em ambas as extremidades — verdadeiro deque.
Algoritmos de janela deslizante — deque monotônico.
Buffer circular — produtor/consumidor com tamanho limitado.
Precisa usar como pilha E fila no mesmo programa.

Quando NÃO Usar VecDeque?

Apenas operações no final — Vec<T> é mais simples e ligeiramente mais eficiente.
Precisa de fatias (&[T]) — VecDeque pode ter dados fragmentados. Use make_contiguous() se necessário, mas isso custa O(n).
Precisa de prioridade — use BinaryHeap<T>.
Inserções/remoções no meio são frequentes — todas as alternativas são O(n); considere estruturas baseadas em árvores para esse caso.

Exercícios

Exercício 1: Palíndromo com Deque

Implemente uma função eh_palindromo(texto: &str) -> bool que usa um VecDeque para verificar se uma string é um palíndromo. O algoritmo deve:

Inserir todos os caracteres no deque (ignorando espaços e pontuação)
Remover simultaneamente da frente e de trás, comparando os caracteres
Se todos os pares corresponderem, é palíndromo

Teste com: “socorram me subi no onibus em marrocos”, “a man a plan a canal panama”.

Dica: Converta para minúsculas e filtre apenas caracteres alfanuméricos antes de inserir.

Exercício 2: Soma Máxima em Subarrays de Tamanho K

Usando a técnica de janela deslizante com VecDeque, implemente uma função soma_maxima_janela(nums: &[i32], k: usize) -> (i32, usize) que retorna a soma máxima entre todos os subarrays de tamanho k e a posição inicial desse subarray.

Exemplo: nums = [2, 1, 5, 1, 3, 2], k = 3 retorna (9, 2) porque [5, 1, 3] tem soma 9.

Dica: Mantenha uma soma corrente. Ao avançar a janela, some o novo elemento e subtraia o que saiu. Não precisa necessariamente de VecDeque para este caso simplificado.

Exercício 3: Deque de Tamanho Limitado (LRU simplificado)

Implemente uma estrutura DequeLimitado<T> que mantém no máximo N elementos. Quando um novo elemento é inserido e o deque está cheio, o elemento mais antigo (da ponta oposta) é automaticamente removido. Isso simula o comportamento de um cache LRU simplificado.

Implemente:

inserir_frente(val) — insere na frente, remove de trás se cheio
inserir_tras(val) — insere na trás, remove da frente se cheio
contem(&val) -> bool — verifica se um valor está presente
promover(&val) — se o valor existir, move para a frente (acesso recente)

Dica: Use VecDeque<T> internamente. Para promover, encontre o elemento com iter().position(), remova com remove(i) e insira na frente.

Conclusão

O Deque (VecDeque) é a estrutura mais versátil entre as lineares, capaz de assumir o papel de pilha, fila ou ambos. Seu buffer circular interno oferece operações O(1) em ambas as extremidades com excelente localidade de cache.

Pontos-chave a lembrar:

VecDeque generaliza Pilha e Fila — use quando precisar de operações eficientes em ambas as extremidades.
O buffer circular evita a necessidade de mover elementos, usando aritmética modular para “envolver” os índices.
O deque monotônico é a técnica-chave para resolver problemas de janela deslizante em O(n), como encontrar máximos/mínimos em janelas.
Prefira Vec<T> se só precisa de operações no final (pilha) — é mais simples e o compilador pode otimizar melhor.
make_contiguous() permite obter uma fatia &[T] do VecDeque, mas custa O(n) — use com parcimônia.
Na prática, VecDeque é a escolha correta para filas em Rust, BFS, agendadores round-robin e qualquer cenário que combine inserções/remoções nas duas pontas.

O Deque demonstra como uma boa escolha de estrutura de dados pode transformar um algoritmo O(n*k) em O(n) — a diferença entre uma solução que funciona e uma que escala.