VecDeque în Rust

use std::collections::VecDeque;

let mut c: VecDeque<T> = VecDeque::new();
let c = VecDeque::from([a, b, c]);
pub fn len(&self) -> usize

Ce face VecDeque

VecDeque<T> (de la „double-ended queue”) ține elementele într-un tablou circular. Spre deosebire de Vec, unde inserarea la început mută toate elementele, aici push_front și pop_front sunt la fel de rapide ca push_back și pop_back.

Este alegerea potrivită pentru o coadă (primul venit, primul servit): cereri de procesat, parcurgerea în lățime a unui graf, ultimele N valori dintr-un flux. VecDeque::new() creează o coadă goală, VecDeque::from([..]) sau collect() una cu elemente, iar len() spune câte elemente are.

Poți accesa elementele după poziție (c[0], c.get(i)) și le poți parcurge cu iter(), ca la un vector. Pentru că elementele nu sunt neapărat continue în memorie, nu obții direct un &[T]; make_contiguous() le aranjează într-un singur slice. Trebuie importată cu use std::collections::VecDeque;.

Ce returnează

VecDeque::new() returnează o coadă goală; len() returnează numărul de elemente (usize).

Exemple

Exemplul 1: Coada de la cabinetul medical

use std::collections::VecDeque;

fn main() {
    let mut coada = VecDeque::new();
    coada.push_back("Ana");
    coada.push_back("Mihai");
    coada.push_back("Ioana");
    println!("în așteptare: {:?} ({} persoane)", coada, coada.len());

    while let Some(pacient) = coada.pop_front() {
        println!("intră la medic: {pacient}; mai așteaptă {}", coada.len());
    }
}

Rezultat

în așteptare: ["Ana", "Mihai", "Ioana"] (3 persoane)
intră la medic: Ana; mai așteaptă 2
intră la medic: Mihai; mai așteaptă 1
intră la medic: Ioana; mai așteaptă 0

Exemplul 2: Ultimele 3 temperaturi

Când coada are deja 3 valori, cea mai veche iese prin față înainte să intre cea nouă prin spate.

use std::collections::VecDeque;

fn main() {
    let mut ultimele: VecDeque<i32> = VecDeque::with_capacity(3);
    for temp in [12, 15, 11, 18, 20] {
        if ultimele.len() == 3 {
            ultimele.pop_front();
        }
        ultimele.push_back(temp);
        println!("ultimele 3 temperaturi: {:?}", ultimele);
    }
    println!("cea mai veche: {}, cea mai nouă: {}", ultimele[0], ultimele[ultimele.len() - 1]);

    let v: Vec<i32> = ultimele.into_iter().collect();
    println!("ca vector: {:?}", v);
}

Rezultat

ultimele 3 temperaturi: [12]
ultimele 3 temperaturi: [12, 15]
ultimele 3 temperaturi: [12, 15, 11]
ultimele 3 temperaturi: [15, 11, 18]
ultimele 3 temperaturi: [11, 18, 20]
cea mai veche: 11, cea mai nouă: 20
ca vector: [11, 18, 20]

Exemplul 3: Câte drumuri până la fiecare oraș (parcurgere în lățime)

Pornim din București. Orașele descoperite intră în coadă și sunt vizitate în ordinea descoperirii, deci prima distanță găsită este cea mai mică.

use std::collections::VecDeque;

fn main() {
    let orase = ["București", "Ploiești", "Brașov", "Pitești", "Sibiu", "Cluj"];
    // vecinii fiecărui oraș (poziții în tabloul de mai sus)
    let drumuri: [&[usize]; 6] = [&[1, 3], &[0, 2], &[1, 4], &[0, 4], &[2, 3, 5], &[4]];

    let mut distanta = [usize::MAX; 6];
    let mut coada = VecDeque::new();
    distanta[0] = 0;
    coada.push_back(0);
    while let Some(oras) = coada.pop_front() {
        for &vecin in drumuri[oras] {
            if distanta[vecin] == usize::MAX {
                distanta[vecin] = distanta[oras] + 1;
                coada.push_back(vecin);
            }
        }
    }
    for (i, nume) in orase.iter().enumerate() {
        println!("{nume:10} la {} drumuri de București", distanta[i]);
    }
}

Rezultat

București  la 0 drumuri de București
Ploiești   la 1 drumuri de București
Brașov     la 2 drumuri de București
Pitești    la 1 drumuri de București
Sibiu      la 2 drumuri de București
Cluj       la 3 drumuri de București

Greșeli frecvente

• Folosești Vec cu remove(0) pentru o coadă. Fiecare scoatere mută toate elementele; VecDeque::pop_front e instantaneu.
• Uiți importul: failed to resolve: use of undeclared type `VecDeque`. Adaugă use std::collections::VecDeque;.
• Încerci să sortezi direct sau să dai coada unei funcții care cere &[T]. Apelează întâi make_contiguous(), care returnează &mut [T], sau transformă coada în Vec.

Comenzi înrudite

• VecDeque::push_back: Adaugă (push) și scoate (pop) elemente la oricare capăt al cozii: back este sfârșitul, front este începutul.
• VecDeque::front: Arată primul (front) sau ultimul (back) element al cozii, fără să-l scoată; None dacă coada e goală.
• Vec: Vectorul dinamic din Rust: o listă de elemente de același tip, ținute unul după altul în memorie, care crește singură.
• BinaryHeap: Coadă de priorități: pop scoate mereu cel mai mare element, iar peek îl arată fără să-l scoată.
• Vec::rotate_left: Rotește elementele spre stânga: primele mid elemente trec la final, în aceeași ordine. rotate_right face invers.