--- title: "VecDeque\u003cT\u003e: Fila de Duas Pontas em Rust" url: "https://rustlang.com.br/stdlib/vecdeque/" markdown_url: "https://rustlang.com.br/stdlib/vecdeque.MD" description: "Guia completo do VecDeque em Rust: fila de duas pontas, push/pop em ambas as extremidades, ring buffer, rotação e comparação com Vec. Exemplos práticos." date: "2026-02-23" author: "Equipe Rust Brasil" --- # VecDeque: Fila de Duas Pontas em Rust Guia completo do VecDeque em Rust: fila de duas pontas, push/pop em ambas as extremidades, ring buffer, rotação e comparação com Vec. Exemplos práticos. O `VecDeque` é 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`](/stdlib/vec/) — é mais simples e tem melhor localidade de cache. ## Criando e Inicializando ```rust use std::collections::VecDeque; fn main() { // Criar vazio let mut fila: VecDeque = VecDeque::new(); // Criar com capacidade inicial let mut buffer: VecDeque = 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 = (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` | O(1) | | `pop_front()` | Remove do início; retorna `Option` | 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 ```rust use std::collections::VecDeque; fn main() { let mut fila: VecDeque = 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 ```rust 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 ```rust use std::collections::VecDeque; struct BufferCircular { dados: VecDeque, capacidade: usize, } impl BufferCircular { 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 { &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 ```rust 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 = 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::() / janela.len() as f64; println!(" {:?} -> média = {:.1}", janela, media); } } } ``` ### 5. Convertendo entre VecDeque e Vec ```rust use std::collections::VecDeque; fn main() { // Vec -> VecDeque let vetor = vec![1, 2, 3, 4, 5]; let mut deque: VecDeque = 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 = deque.into(); println!("Vec: {:?}", vetor2); // Opção 2: collect de um iterador let deque3 = VecDeque::from([10, 20, 30]); let vetor3: Vec = 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](/stdlib/vec/) --- vetor dinâmico, a coleção mais usada - [LinkedList em Rust](/stdlib/linkedlist/) --- lista duplamente encadeada - [BinaryHeap: Fila de Prioridade](/stdlib/binaryheap/) --- quando precisa sempre do maior elemento - [Filtrar Vetor em Rust](/receitas/filtrar-vetor/) --- técnicas de filtragem - [Ordenar Vetor em Rust](/receitas/ordenar-vetor/) --- técnicas de ordenação - [Variáveis, Tipos e Funções](/tutoriais/variaveis-tipos-funcoes/) --- fundamentos dos tipos