Queues & Deques

First-In, First-Out for fair waiting lines, or Double-Ended for maximum flexibility.

The idea

A Queue is a line at the grocery store: whoever gets in first is served first (FIFO). In arrays, this is tricky because removing from the front means shifting everything else over (O(N)).

To make it O(1), we can use a Ring Buffer (Circular Queue). We keep a head and tail pointer. When the tail reaches the end of the array, it wraps around to index 0 using modulo math.

A Deque (Double-Ended Queue) allows adding and removing from both ends in O(1) time. It is heavily used in advanced sliding-window problems.

Empty Ring Buffer of size 5.

How it works

class RingBuffer:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.tail = 0
        self.size = 0
        self.k = k

    def enqueue(self, val):
        if self.size == self.k: return False
        self.q[self.tail] = val
        self.tail = (self.tail + 1) % self.k
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0: return False
        self.head = (self.head + 1) % self.k
        self.size -= 1
        return True