Circular Queue

Also known as a Ring Buffer. Used in Operating Systems and Network Traffic.

We use a fixed-size array (Circular Queue). Instead of shifting elements when we dequeue (which is slow), we use pointers (head and tail) that move forward. When a pointer reaches the end of the array, it wraps around to index 0 using the Modulo operator (%).

The Math: $\text{Next Index}=(\text{Current Index}+1)\%\text{Capacity}$

Implementation

class MyCircularQueue:
    def __init__(self, k: int):
        self.capacity = k
        self.buffer = [None] * k
        self.head = 0
        self.count = 0  # Tracks current number of elements
 
    def en_queue(self, value: int) -> bool:
        if self.is_full():
            return False
 
        # Calculate tail position based on head + count
        tail_index = (self.head + self.count) % self.capacity
        self.buffer[tail_index] = value
        self.count += 1
        return True
 
    def de_queue(self) -> bool:
        if self.is_empty():
            return False
 
        # Move head forward, wrapping around if needed
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True
 
    def front(self) -> int:
        if self.is_empty():
            return -1
        return self.buffer[self.head]
 
    def rear(self) -> int:
        if self.is_empty():
            return -1
        # Tail is one step behind (head + count)
        tail_index = (self.head + self.count - 1) % self.capacity
        return self.buffer[tail_index]
 
    def is_empty(self) -> bool:
        return self.count == 0
 
    def is_full(self) -> bool:
        return self.count == self.capacity

pub struct CircularQueue<T> {
    buffer: Vec<Option<T>>, // We use `Vec<Option<T>>` to safely represent empty slots.*
    head: usize,
    count: usize,
    capacity: usize,
}
 
impl<T: Clone> CircularQueue<T> {
    pub fn new(k: usize) -> Self {
        Self {
            buffer: vec![None; k], // Initialize with None
            head: 0,
            count: 0,
            capacity: k,
        }
    }
 
    pub fn en_queue(&mut self, value: T) -> bool {
        if self.is_full() {
            return false;
        }
        let tail_index = (self.head + self.count) % self.capacity;
        self.buffer[tail_index] = Some(value);
        self.count += 1;
        true
    }
 
    pub fn de_queue(&mut self) -> bool {
        if self.is_empty() {
            return false;
        }
        // Optional: clear the value (not strictly necessary for logic, good for memory)
        self.buffer[self.head] = None;
        self.head = (self.head + 1) % self.capacity;
        self.count -= 1;
        true
    }
 
    pub fn front(&self) -> Option<&T> {
        if self.is_empty() {
            return None;
        }
        self.buffer[self.head].as_ref()
    }
 
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }
 
    pub fn is_full(&self) -> bool {
        self.count == self.capacity
    }
}