Есть ли в Rust коллекции типа очередь и стек?

Да, в Rust есть стандартные коллекции для очереди и стека, а также эффективные альтернативы

Вы абсолютно правы, что Vec::remove(0) — это неэффективно для очереди. К счастью, в стандартной библиотеке Rust (std) есть специализированные коллекции, которые решают вашу задачу.

Стек (LIFO) — Vec как стек

Для стека в Rust используется обычный Vec. Он уже предоставляет все необходимые методы:

fn main() {
    let mut stack: Vec<i32> = Vec::new();
    stack.push(1);  // Добавляем на вершину
    stack.push(2);
    stack.push(3);
    
    let top = stack.pop();  // Извлекаем с вершины — O(1)
    println!("{:?}", top);  // Some(3)
    
    let peek = stack.last();  // Просмотр вершины без извлечения
    println!("{:?}", peek);   // Some(2)
}

push и pop работают за амортизированное O(1). Это идеальный стек.

Очередь (FIFO) — VecDeque

Для двусторонней очереди (deque) в std есть std::collections::VecDeque. Она реализована как кольцевой буфер и обеспечивает O(1) для вставки/удаления с обоих концов:

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<i32> = VecDeque::new();
    queue.push_back(1);   // Добавляем в конец
    queue.push_back(2);
    queue.push_back(3);
    
    let front = queue.pop_front();  // Извлекаем из начала — O(1)
    println!("{:?}", front);        // Some(1)
    
    // Можно также добавлять в начало и извлекать с конца
    queue.push_front(0);            // O(1)
    let back = queue.pop_back();    // O(1)
}

Это то, что вам нужно для FIFO очереди. VecDeque также поддерживает индексацию (но медленнее, чем Vec) и итерацию.

Приоритетная очередь — BinaryHeap

Если вам нужна очередь с приоритетом (наибольший элемент извлекается первым), используйте std::collections::BinaryHeap:

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(5);
    
    let max = heap.pop();  // Извлекает наибольший — O(log n)
    println!("{:?}", max); // Some(5)
}

Для очереди с наименьшим приоритетом оберните значения в std::cmp::Reverse.

Сравнение производительности

• Vec как стек: push/pop — O(1). remove(0) — O(n). Идеально для LIFO.
• VecDeque: push_back/pop_front — O(1). Лучший выбор для FIFO очереди.
• LinkedList (тоже есть в std): push_back/pop_front — O(1), но с большими накладными расходами на кэш-промахи. Обычно медленнее VecDeque на практике.
• BinaryHeap: push/pop — O(log n). Только для приоритетных очередей.

Итог

Для вашей задачи с обработкой задач в порядке поступления (FIFO) используйте VecDeque. Это стандартная, эффективная и простая в использовании коллекция. Стек уже реализован через Vec. Никаких внешних крейтов не требуется!

use crossbeam::queue::SegQueue;

fn main() {
    let q = SegQueue::new();
    q.push(1);
    q.push(2);
    if let Some(val) = q.pop() {
        println!("{}", val);
    }
}

use arraydeque::ArrayDeque;
use arraydeque::behavior::Wrapping;

fn main() {
    let mut queue: ArrayDeque<[i32; 5], Wrapping> = ArrayDeque::new();
    queue.push_back(1);
    queue.push_back(2);
}