A queue adds elements at the back and removes them from the front. This first-in, first-out (FIFO) order makes it useful for holding work temporarily. Insertion and removal are O(1); searching is O(n), so a queue is a poor choice when the main task is finding an arbitrary element. section 8.6 section 7.2
A bounded queue can use a fixed-size array and two indexes. Push writes at the back; pop reads at the front. Each operation advances its index, using the index modulo the array size to select a slot. Equal indexes mean empty; when back has advanced N positions beyond front, the queue is full. Push then returns an error, while pop returns no value when empty. section 8.6
For one producer and one consumer, sharing those indexes requires synchronization. A wait-free SPSC implementation uses atomic indexes: the producer writes a slot before publishing the new back index, and the consumer reads an available slot before publishing the new front index. Acquire loads and release stores coordinate those steps without mutual exclusion. section 8.6
/// Pushes an item into the queue. Returns an error if the queue is full.
pub fn push(&self, value: T) -> Result<(), T> {
let back = self.back.load(Ordering::Relaxed);
let front = self.front.load(Ordering::Acquire);
if front + N - back == 0 {
return Err(value);
}
let ptr = self.data.as_ptr() as *mut T;
unsafe {
ptr.add(back % N).write(value);
}
self.back.store(back + 1, Ordering::Release);
Ok(())
}
The push implementation shows the full-queue check, wrapped array access, and release store that publishes a newly written element. section 8.6
FIFO as a cache replacement policy
A full FIFO cache evicts the entry inserted earliest, regardless of later accesses. SIEVE modifies that behavior: it marks accessed entries as visited and, when choosing an eviction candidate, clears a visited mark and moves past that entry instead of evicting it. This helps retain frequently accessed entries without eagerly moving them on every access. section 6.6.3
A queue's FIFO rule does not by itself guarantee delivery order in a larger messaging system. Actors receive messages through mailboxes, but message delivery order is not guaranteed; account for that distinction when designing concurrent work. section 9.2.6
