Implement a Circular Queue in Python: An Ultimate How-to Guide

Updated: at 03:34 AM

A circular queue is a data structure that effectively manages first-in-first-out (FIFO) operations. It is a linear data structure that utilizes a circular memory layout to store data elements, allowing both ends of the queue to be used to insert and remove elements. This makes circular queues more memory efficient than traditional linear queues.

In this comprehensive guide, we will learn how to implement a circular queue in Python. We will cover the following topics:

Table of Contents

Open Table of Contents

Overview of Circular Queues

A circular queue is a linear data structure that stores elements in a circular fashion. Unlike a regular queue that ends when it reaches capacity, a circular queue connects the rear to the front to make use of the empty space when the queue is not full.

This makes circular queues more memory efficient as the memory is reused when elements are dequeued. The circular queue follows FIFO - first-in-first-out - order when enqueueing and dequeueing elements.

The key characteristics of circular queues:

Circular queues are useful when you need to buffer incoming data or transfer elements between threads efficiently. They have applications in real-time embedded systems, audio processing, and computer graphics.

Circular Queue Operations

The main operations supported by a circular queue are:

Enqueue

Adds a new element to the rear of the queue.

Dequeue

Removes the oldest element from the front of the queue.

Front

Returns the element at the front of the queue without removing it.

Now let’s see how to implement these operations in Python.

Basic Implementation in Python

Before creating a custom class, we can implement a basic circular queue using built-in Python data structures like lists or the collections module deque.

Using List

# Initialize empty list with capacity
queue = [None] * 5

# Enqueue
def enqueue(queue, item):
  queue.append(item)
  if len(queue) > len(queue) - 1:
    queue.pop(0)

# Dequeue
def dequeue(queue):
  if len(queue) > 0:
    item = queue[0]
    queue.pop(0)
    return item
  else:
    print("Queue empty!")
    return None

# Front
def front(queue):
  if len(queue) > 0:
    return queue[0]
  else:
    print("Queue empty!")
    return None

# Driver code
q = [None] * 5
enqueue(q, 1)
enqueue(q, 2)
enqueue(q, 3)

print(q) # [1, 2, 3, None, None]

print(front(q)) # 1

print(dequeue(q)) # 1
print(q) # [2, 3, None, None, None]

We initialize an empty list of a fixed capacity to represent the circular queue. The enqueue operation appends elements to the rear, popping from the front if full. Dequeue pops from the front while front returns the first element.

This demonstrates the basic logic, but lacks some validation and modularity. Next we’ll use the deque class which handles the circular behavior for us.

Using Collections Module

Python’s collections module provides specialized container datatypes, including a double-ended queue or deque class that naturally handles circular queues.

from collections import deque

# Initialize deque with max length
queue = deque(maxlen=5)

# Enqueue
def enqueue(queue, item):
  queue.append(item)

# Dequeue
def dequeue(queue):
  if len(queue) > 0:
    return queue.popleft()
  else:
    print("Queue empty!")
    return None

# Front
def front(queue):
  if len(queue) > 0:
    return queue[0]
  else:
    print("Queue empty!")
    return None

# Driver code
q = deque(maxlen=5)
enqueue(q, 1)
enqueue(q, 2)
enqueue(q, 3)

print(q) # deque([1, 2, 3], maxlen=5)

print(front(q)) # 1

print(dequeue(q)) # 1

deque handles the circular behavior and capacity limit automatically. We simply append to enqueue, pop from the left to dequeue, and access index 0 to get the front.

This is simple but lacks customization. Next we’ll build a custom CircularQueue class with more control.

Circular Queue Class in Python

For full control and extensibility, we can build a CircularQueue class in Python. The key aspects are:

class CircularQueue:

  def __init__(self, max_size):
    self.queue = [None] * max_size
    self.max_size = max_size
    self.head = self.tail = -1

  def enqueue(self, data):
    if self.tail + 1 == self.head or (self.head == 0 and self.tail + 1 == self.max_size):
      print("Queue full!")
      return -1

    elif self.tail == -1: # First element
      self.tail = 0
      self.head = 0
      self.queue[self.tail] = data

    else:
      self.tail = (self.tail + 1) % self.max_size
      self.queue[self.tail] = data

  def dequeue(self):
    if self.head == -1:
      print("Queue empty!")
      return -1

    data = self.queue[self.head]
    self.queue[self.head] = None

    if self.head == self.tail:
      self.head = -1
      self.tail = -1

    else:
      self.head = (self.head + 1) % self.max_size

    return data

  def front(self):
    if self.head == -1:
      print("Queue empty!")
      return -1
    return self.queue[self.head]

# Driver code
q = CircularQueue(5)

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.queue) # [1, 2, 3, None, None]

print(q.front()) # 1

print(q.dequeue()) # 1
print(q.queue) # [2, 3, None, None, None]

The CircularQueue class initializes the circular queue with a given maximum capacity. We use a Python list to represent the underlying circular array.

The enqueue method inserts elements at the tail, looping back to 0 when reaching max size. Dequeue removes from the head, also looping back around. Front simply returns the head element.

This gives us full control over a circular queue implementation in Python!

Complexity Analysis

The complexity of core circular queue operations is:

Since we use a fixed size array as the underlying data structure, all operations complete in constant time.

The space complexity is O(N) linear for the array of size N capacity.

Compared to dynamic arrays or linked lists, circular queues provide great performance by sacrificing flexibility in size.

Applications of Circular Queues

Circular queues provide an efficient FIFO data structure useful for several applications:

Some key benefits over regular queues:

Circular queues strike an effective balance between flexibility and performance for FIFO data structures.

Conclusion

In this guide, we learned how circular queues work and how to implement them in Python using lists, deques, and a custom class.

Key takeaways:

Circular queues are fundamental data structures in computer science and have many practical use cases. Using the concepts and Python code covered here, you should be able to implement circular queues efficiently in your own applications.