// 1040: Queue Using VecDeque
// FIFO queue: push_back, pop_front — both O(1)
use std::collections::VecDeque;
/// Queue wrapper (optional — VecDeque is already a queue)
struct Queue<T> {
inner: VecDeque<T>,
}
impl<T> Queue<T> {
fn new() -> Self {
Queue { inner: VecDeque::new() }
}
fn enqueue(&mut self, value: T) {
self.inner.push_back(value);
}
fn dequeue(&mut self) -> Option<T> {
self.inner.pop_front()
}
fn peek(&self) -> Option<&T> {
self.inner.front()
}
fn is_empty(&self) -> bool {
self.inner.is_empty()
}
fn len(&self) -> usize {
self.inner.len()
}
}
fn basic_queue() {
let mut q = Queue::new();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
assert_eq!(q.len(), 3);
assert_eq!(q.peek(), Some(&1));
assert_eq!(q.dequeue(), Some(1));
assert_eq!(q.dequeue(), Some(2));
assert_eq!(q.dequeue(), Some(3));
assert!(q.is_empty());
}
/// VecDeque directly as a queue
fn vecdeque_as_queue() {
let mut q: VecDeque<&str> = VecDeque::new();
q.push_back("first");
q.push_back("second");
q.push_back("third");
assert_eq!(q.front(), Some(&"first"));
assert_eq!(q.pop_front(), Some("first"));
assert_eq!(q.pop_front(), Some("second"));
assert_eq!(q.len(), 1);
}
/// BFS with level tracking using queue
fn bfs_levels(adjacency: &[Vec<usize>], start: usize) -> Vec<Vec<usize>> {
let n = adjacency.len();
let mut visited = vec![false; n];
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
let mut levels: Vec<Vec<usize>> = Vec::new();
visited[start] = true;
queue.push_back((start, 0));
while let Some((node, level)) = queue.pop_front() {
// Extend levels vec if needed
while levels.len() <= level {
levels.push(Vec::new());
}
levels[level].push(node);
for &neighbor in &adjacency[node] {
if !visited[neighbor] {
visited[neighbor] = true;
queue.push_back((neighbor, level + 1));
}
}
}
levels
}
fn bfs_test() {
let adj = vec![
vec![1, 2], // 0 -> 1, 2
vec![3], // 1 -> 3
vec![3], // 2 -> 3
vec![], // 3 -> (none)
];
let levels = bfs_levels(&adj, 0);
assert_eq!(levels[0], vec![0]);
assert_eq!(levels[1], vec![1, 2]);
assert_eq!(levels[2], vec![3]);
}
fn main() {
basic_queue();
vecdeque_as_queue();
bfs_test();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic() { basic_queue(); }
#[test]
fn test_vecdeque() { vecdeque_as_queue(); }
#[test]
fn test_bfs() { bfs_test(); }
#[test]
fn test_empty_dequeue() {
let mut q: Queue<i32> = Queue::new();
assert_eq!(q.dequeue(), None);
assert_eq!(q.peek(), None);
}
}
(* 1040: Queue Using VecDeque *)
(* OCaml has a mutable Queue module in stdlib *)
(* Approach 1: OCaml's Queue module *)
let stdlib_queue () =
let q = Queue.create () in
Queue.push 1 q;
Queue.push 2 q;
Queue.push 3 q;
assert (Queue.length q = 3);
assert (Queue.peek q = 1);
assert (Queue.pop q = 1);
assert (Queue.pop q = 2);
assert (Queue.pop q = 3);
assert (Queue.is_empty q)
(* Approach 2: Functional queue using two lists *)
type 'a fqueue = { inbox: 'a list; outbox: 'a list }
let empty_q = { inbox = []; outbox = [] }
let enqueue x q = { q with inbox = x :: q.inbox }
let dequeue q =
match q.outbox with
| x :: rest -> Some (x, { q with outbox = rest })
| [] ->
match List.rev q.inbox with
| [] -> None
| x :: rest -> Some (x, { inbox = []; outbox = rest })
let fqueue_size q = List.length q.inbox + List.length q.outbox
let functional_queue () =
let q = empty_q in
let q = enqueue 1 q in
let q = enqueue 2 q in
let q = enqueue 3 q in
assert (fqueue_size q = 3);
let (v, q) = Option.get (dequeue q) in
assert (v = 1);
let (v, q) = Option.get (dequeue q) in
assert (v = 2);
let (v, _q) = Option.get (dequeue q) in
assert (v = 3)
(* Approach 3: BFS using Queue *)
let bfs_levels adjacency start =
let n = Array.length adjacency in
let visited = Array.make n false in
let q = Queue.create () in
Queue.push (start, 0) q;
visited.(start) <- true;
let levels = Hashtbl.create 16 in
while not (Queue.is_empty q) do
let (node, level) = Queue.pop q in
let current = try Hashtbl.find levels level with Not_found -> [] in
Hashtbl.replace levels level (current @ [node]);
List.iter (fun neighbor ->
if not visited.(neighbor) then begin
visited.(neighbor) <- true;
Queue.push (neighbor, level + 1) q
end
) adjacency.(node)
done;
levels
let bfs_test () =
let adj = [| [1; 2]; [3]; [3]; [] |] in
let levels = bfs_levels adj 0 in
assert (Hashtbl.find levels 0 = [0]);
assert (Hashtbl.find levels 1 = [1; 2]);
assert (Hashtbl.find levels 2 = [3])
let () =
stdlib_queue ();
functional_queue ();
bfs_test ();
Printf.printf "✓ All tests passed\n"