Circular Queue

A circular queue is similar to a linear queue, but it uses a circular buffer to efficiently reuse empty slots when elements are dequeued. This prevents the queue from becoming full in the usual sense. Circular queues are often implemented using arrays or linked lists with wraparound logic.

Operations

Circular Queue Operations

These are the same as linear queues:

Enqueue
Adding an element to the back (also known as the rear or tail) of the queue.

Dequeue
Removing and returning the element from the front (also known as the head) of the queue.

Peek
Viewing the element at the front of the queue without removing it.

Demo

Circular Queue Interactive Demonstration

Code

Circular Queue Python Code

class CircularQueue:
    def __init__(self, max_size):
        self.max_size = max_size
        self.queue = [None] * max_size
        self.front = self.rear = -1

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.max_size == self.front

    def enqueue(self, item):
        if self.is_full():
            print("Queue is full")
        elif self.is_empty():
            self.front = self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.max_size
            self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
        elif self.front == self.rear:
            item = self.queue[self.front]
            self.front = self.rear = -1
            return item
        else:
            item = self.queue[self.front]
            self.front = (self.front + 1) % self.max_size
            return item

    def size(self):
        if self.is_empty():
            return 0
        elif self.front <= self.rear:
            return self.rear - self.front + 1
        else:
            return self.max_size - (self.front - self.rear) + 1

# Example usage:
if __name__ == "__main__":
    queue = CircularQueue(5)
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.enqueue(5)

    print("Queue:", queue.queue)
    print("Dequeue:", queue.dequeue())
    print("Queue:", queue.queue)
    print("Is empty?", queue.is_empty())
    print("Is full?", queue.is_full())
    print("Size:", queue.size())

Resources

Presentation