VecDeque<T>: Fila de Duas Pontas em Rust

O VecDeque<T> é uma fila de duas pontas (double-ended queue) da biblioteca padrão do Rust. Ele permite inserção e remoção eficiente em ambas as extremidades — frente e trás — com complexidade O(1) amortizado. Internamente, utiliza um ring buffer (buffer circular) alocado no heap.

Quando Usar VecDeque

Use VecDeque quando:

Precisa inserir/remover elementos tanto na frente quanto no final com eficiência.
Está implementando uma fila (FIFO) ou deque.
Precisa de uma janela deslizante (sliding window) sobre dados.
O Vec não é adequado porque insert(0, ...) e remove(0) são O(n).

Se você só insere/remove no final, use Vec — é mais simples e tem melhor localidade de cache.

Criando e Inicializando

use std::collections::VecDeque;

fn main() {
    // Criar vazio
    let mut fila: VecDeque<i32> = VecDeque::new();

    // Criar com capacidade inicial
    let mut buffer: VecDeque<String> = VecDeque::with_capacity(100);

    // Criar a partir de um array
    let deque = VecDeque::from([1, 2, 3, 4, 5]);

    // Criar a partir de um vetor
    let vec = vec!["a", "b", "c"];
    let deque2: VecDeque<&str> = VecDeque::from(vec);

    // Criar a partir de um iterador
    let deque3: VecDeque<i32> = (1..=10).collect();
    println!("{:?}", deque3);
}

Tabela de Métodos Comuns

Método	Descrição	Complexidade
`push_back(value)`	Insere no final	O(1) amortizado
`push_front(value)`	Insere no início	O(1) amortizado
`pop_back()`	Remove do final; retorna `Option<T>`	O(1)
`pop_front()`	Remove do início; retorna `Option<T>`	O(1)
`front()` / `back()`	Referência ao primeiro/último	O(1)
`get(index)`	Acesso por índice	O(1)
`len()` / `is_empty()`	Tamanho e verificação	O(1)
`insert(index, value)`	Insere na posição `index`	O(min(n-i, i))
`remove(index)`	Remove da posição `index`	O(min(n-i, i))
`rotate_left(n)`	Rotaciona `n` posições para a esquerda	O(min(n, len-n))
`rotate_right(n)`	Rotaciona `n` posições para a direita	O(min(n, len-n))
`make_contiguous()`	Reorganiza para memória contígua	O(n)
`as_slices()`	Retorna as duas fatias do ring buffer	O(1)
`drain(range)`	Remove e retorna um intervalo	O(n)
`retain(f)`	Mantém elementos onde `f` retorna `true`	O(n)
`swap(i, j)`	Troca dois elementos	O(1)
`contains(&value)`	Verifica se contém o valor	O(n)
`iter()` / `iter_mut()`	Iteradores sobre referências	O(n)

Exemplos Práticos

1. Fila FIFO — Primeiro a Entrar, Primeiro a Sair

use std::collections::VecDeque;

fn main() {
    let mut fila: VecDeque<String> = VecDeque::new();

    // Clientes chegam (entram pelo final)
    fila.push_back("Cliente 1".to_string());
    fila.push_back("Cliente 2".to_string());
    fila.push_back("Cliente 3".to_string());
    fila.push_back("Cliente 4".to_string());

    println!("Fila: {:?}", fila);
    println!("Próximo a ser atendido: {:?}", fila.front());

    // Atender clientes (saem pela frente)
    while let Some(cliente) = fila.pop_front() {
        println!("Atendendo: {}", cliente);
        println!("  Restam: {} na fila", fila.len());
    }
}

2. Deque — Inserção e Remoção em Ambas as Pontas

use std::collections::VecDeque;

fn main() {
    let mut historico: VecDeque<&str> = VecDeque::new();

    // Navegador: adicionar páginas ao histórico
    historico.push_back("google.com");
    historico.push_back("rust-lang.org");
    historico.push_back("docs.rs");

    println!("Histórico: {:?}", historico);

    // Voltar (remover do final)
    let pagina_atual = historico.pop_back();
    println!("Voltando de: {:?}", pagina_atual);

    // Adicionar página de alta prioridade no início
    historico.push_front("homepage.com");
    println!("Histórico atualizado: {:?}", historico);

    // Acessar por índice
    if let Some(pagina) = historico.get(1) {
        println!("Segunda página: {}", pagina);
    }
}

3. Buffer Circular com Tamanho Fixo

use std::collections::VecDeque;

struct BufferCircular<T> {
    dados: VecDeque<T>,
    capacidade: usize,
}

impl<T: std::fmt::Debug> BufferCircular<T> {
    fn new(capacidade: usize) -> Self {
        BufferCircular {
            dados: VecDeque::with_capacity(capacidade),
            capacidade,
        }
    }

    fn push(&mut self, valor: T) {
        if self.dados.len() == self.capacidade {
            self.dados.pop_front(); // remove o mais antigo
        }
        self.dados.push_back(valor);
    }

    fn ultimos(&self) -> &VecDeque<T> {
        &self.dados
    }
}

fn main() {
    let mut logs = BufferCircular::new(5);

    for i in 1..=8 {
        logs.push(format!("Log #{}", i));
        println!("Buffer: {:?}", logs.ultimos());
    }
    // Mantém apenas os 5 últimos:
    // ["Log #4", "Log #5", "Log #6", "Log #7", "Log #8"]
}

4. Rotação e Janela Deslizante

use std::collections::VecDeque;

fn main() {
    // Rotação
    let mut carrossel: VecDeque<&str> = VecDeque::from([
        "Slide A", "Slide B", "Slide C", "Slide D", "Slide E",
    ]);

    println!("Original: {:?}", carrossel);

    carrossel.rotate_left(2);
    println!("Rotação esquerda (2): {:?}", carrossel);
    // ["Slide C", "Slide D", "Slide E", "Slide A", "Slide B"]

    carrossel.rotate_right(1);
    println!("Rotação direita (1): {:?}", carrossel);
    // ["Slide B", "Slide C", "Slide D", "Slide E", "Slide A"]

    // Janela deslizante: média móvel de 3 elementos
    let dados = vec![10.0, 20.0, 30.0, 25.0, 35.0, 40.0, 15.0];
    let tamanho_janela = 3;
    let mut janela: VecDeque<f64> = VecDeque::with_capacity(tamanho_janela);

    println!("\nMédia móvel (janela = {}):", tamanho_janela);
    for valor in &dados {
        janela.push_back(*valor);
        if janela.len() > tamanho_janela {
            janela.pop_front();
        }
        if janela.len() == tamanho_janela {
            let media: f64 = janela.iter().sum::<f64>() / janela.len() as f64;
            println!("  {:?} -> média = {:.1}", janela, media);
        }
    }
}

5. Convertendo entre VecDeque e Vec

use std::collections::VecDeque;

fn main() {
    // Vec -> VecDeque
    let vetor = vec![1, 2, 3, 4, 5];
    let mut deque: VecDeque<i32> = VecDeque::from(vetor);

    // Manipular como deque
    deque.push_front(0);
    deque.push_back(6);
    println!("Deque: {:?}", deque); // [0, 1, 2, 3, 4, 5, 6]

    // VecDeque -> Vec (pode não ser contíguo!)
    // Opção 1: make_contiguous + into()
    deque.make_contiguous();
    let vetor2: Vec<i32> = deque.into();
    println!("Vec: {:?}", vetor2);

    // Opção 2: collect de um iterador
    let deque3 = VecDeque::from([10, 20, 30]);
    let vetor3: Vec<i32> = deque3.into_iter().collect();
    println!("Vec coletado: {:?}", vetor3);

    // as_slices: ver as duas fatias internas do ring buffer
    let mut d = VecDeque::from([1, 2, 3]);
    d.push_front(0); // pode dividir o buffer
    let (frente, tras) = d.as_slices();
    println!("Fatia da frente: {:?}", frente);
    println!("Fatia de trás: {:?}", tras);
}

Características de Desempenho

Operação	VecDeque	Vec
`push_back`	O(1) amortizado	O(1) amortizado
`push_front`	O(1) amortizado	O(n)
`pop_back`	O(1)	O(1)
`pop_front`	O(1)	O(n)
Acesso por índice	O(1)	O(1)
`insert` no meio	O(min(n-i, i))	O(n)
`remove` no meio	O(min(n-i, i))	O(n)
Iteração	O(n)	O(n)
Localidade de cache	Boa*	Excelente

* O ring buffer do VecDeque pode ter os dados divididos em duas fatias não contíguas, o que reduz ligeiramente a localidade de cache comparado ao Vec.

Memória: VecDeque aloca um buffer contíguo como o Vec, mas com um ponteiro de início (head) que permite operações circulares. O overhead de memória é mínimo — apenas dois campos extras (head e len).

VecDeque vs Vec vs LinkedList

Critério	VecDeque	Vec	LinkedList
push/pop frente	O(1)	O(n)	O(1)
push/pop trás	O(1)	O(1)	O(1)
Acesso por índice	O(1)	O(1)	O(n)
Localidade de cache	Boa	Excelente	Ruim
Uso de memória	Baixo	Baixo	Alto
Caso de uso	Fila/deque	Pilha/lista geral	Raramente ideal

Regra prática: Use Vec como padrão. Use VecDeque quando precisar de operações eficientes na frente. Evite LinkedList na maioria dos casos.

Veja Também

Vec em Rust — vetor dinâmico, a coleção mais usada
LinkedList em Rust — lista duplamente encadeada
BinaryHeap: Fila de Prioridade — quando precisa sempre do maior elemento
Filtrar Vetor em Rust — técnicas de filtragem
Ordenar Vetor em Rust — técnicas de ordenação
Variáveis, Tipos e Funções — fundamentos dos tipos