Circular Queues and Deques

While linked lists provide O(1) queue operations, each node allocation introduces pointer overhead and garbage collection pauses. The Circular Queue (Ring Buffer) achieves O(1) performance inside a fixed, cache-friendly array.

The Circular Queue (Ring Buffer)

A Circular Queue treats a flat array as if its two ends were connected in a continuous circle.

Instead of shifting items upon dequeue, we maintain two integer indices:

• front: Points to the item to be dequeued.
• rear: Points to the next insertion slot.

When either pointer reaches the end of the array, it wraps around to index 0 using modulo arithmetic:

nextIndex = (currentIndex + 1) mod Capacity

Copy codeArray Capacity = 5

      [0]   [1]   [2]   [3]   [4]
    +-----+-----+-----+-----+-----+
    | 50  |     |     | 30  | 40  |
    +-----+-----+-----+-----+-----+
             ^           ^
             |           |
           rear = 1    front = 3

Kotlin Ring Buffer Implementation

Copy codeclass CircularQueue<T>(private val capacity: Int) {
    private val buffer = arrayOfNulls<Any>(capacity)
    private var front = 0
    private var rear = 0
    private var count = 0

    fun enqueue(item: T): Boolean {
        if (isFull()) return false
        buffer[rear] = item
        rear = (rear + 1) % capacity // Wrap around!
        count++
        return true
    }

    @Suppress("UNCHECKED_CAST")
    fun dequeue(): T? {
        if (isEmpty()) return null
        val item = buffer[front] as T
        buffer[front] = null
        front = (front + 1) % capacity // Wrap around!
        count--
        return item
    }

    fun isFull(): Boolean = count == capacity
    fun isEmpty(): Boolean = count == 0
}

What is a Deque (Double-Ended Queue)?

A Deque (pronounced "deck") is a generalized queue that supports insertion and deletion at both ends:

• addFirst(e) / removeFirst()
• addLast(e) / removeLast()

Copy code<- Pop/Push (Front)                      Push/Pop (Rear) ->
      |                                         |
      v                                         v
   [ Head ] <==============================> [ Tail ]

Deque as a Universal Structure

A Deque can function as:

• A Stack (use only addFirst and removeFirst).
• A Queue (use addLast and removeFirst).

In the Java/Android standard library, java.util.ArrayDeque is the officially recommended class for both Stacks and Queues because it is significantly faster than Stack and LinkedList.

Summary

• Circular Queues use modulo pointer wrapping (i + 1) % N to achieve O(1) queue operations without shifting elements.
• Deques support O(1) operations at both ends, serving as the most efficient backing structure for stacks and queues.