Circular Queue in Data Structure

In Data Structure, a circular queue is a queue in which the front and end parts are connected together and make a circle.

Circular Queue in Data Structure

In the queue, when we delete the item from the front part, then the position from where we deleted the value becomes vacant or None.

To utilise these positions and insert new values again, we make a circular queue.

Note: To make a circular queue, we need to give a fixed size to it.

Enqueue operation

To insert a new value in the queue is called the enqueue operation.

The dequeue operation

To delete a value from the queue is called the Dequeue operation. To keep track of the position of the enqueue and dequeue elements, we use two variables, front and count. Initially, we set the front and count variables to zero. Then, if we enqueue any element in the queue, we increment the count variable’s value by 1, and when we dequeue an element from the queue, we increment the front variable’s value by 1.

We use this formula to find the position where we need to insert a new value.

i = ( front + count ) % len( queue )

Here, the length of the queue is equal to the size of the queue. And we use this formula to find the position from where we need to delete the element from the queue.

queue[front] = None

front = ( front + 1 ) % len( queue )

First, we need to store the value None in the front position of the queue. And then we use the formula to find the new position of the front.

Program to implement a circular queue using an array in Python

class EmptyQueueError(Exception):
    pass

class Queue:

    def __init__(self, default_size=10):
        self.items = [None] * default_size
        self.front = 0        self.count = 0
    def is_empty(self):
        return self.count == 0
    def size(self):
        return self.count

    def enqueue(self, item):
        if self.count == len(self.items):
            self.resize(2 * len(self.items))

        i = (self.front + self.count) % len(self.items)
        self.items[i] = item
        self.count += 1
    def dequeue(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        x = self.items[self.front]
        self.items[self.front] = None        self.front = (self.front + 1) % len(self.items)
        self.count -= 1        return x

    def peek(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        return self.items[self.front]

    def display(self):
        print(self.items)

    def resize(self, newsize):
        old_list = self.items
        self.items = [None] * newsize
        i = self.front
        for j in range(self.count):
            self.items[j] = old_list[i]
            i = (1 + i) % len(old_list)
        self.front = 0

###########

if __name__ == '__main__':
    qu = Queue(6)

    while True:
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.enqueue(x)
        elif choice == 2:
            x = qu.dequeue()
            print("Element deleted from the queue is : ", x)
        elif choice == 3:
            print("Element at the front end is ", qu.peek())
        elif choice == 4:
            print("Size of queue ", qu.size())
        elif choice == 5:
            qu.display()
        elif choice == 6:
            break        else:
            print("Wrong choice")
        print()

class EmptyQueueError(Exception):
    pass

class Queue:

    def __init__(self, default_size=10):
        self.items = [None] * default_size
        self.front = 0        self.count = 0
    def is_empty(self):
        return self.count == 0
    def size(self):
        return self.count

    def enqueue(self, item):
        if self.count == len(self.items):
            self.resize(2 * len(self.items))

        i = (self.front + self.count) % len(self.items)
        self.items[i] = item
        self.count += 1
    def dequeue(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")

        x = self.items[self.front]
        self.items[self.front] = None        self.front = (self.front + 1) % len(self.items)
        self.count -= 1        return x

    def peek(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is empty")
        return self.items[self.front]

    def display(self):
        print(self.items)

    def resize(self, newsize):
        old_list = self.items
        self.items = [None] * newsize
        i = self.front
        for j in range(self.count):
            self.items[j] = old_list[i]
            i = (1 + i) % len(old_list)
        self.front = 0

###########

if __name__ == '__main__':
    qu = Queue(6)

    while True:
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.enqueue(x)
        elif choice == 2:
            x = qu.dequeue()
            print("Element deleted from the queue is : ", x)
        elif choice == 3:
            print("Element at the front end is ", qu.peek())
        elif choice == 4:
            print("Size of queue ", qu.size())
        elif choice == 5:
            qu.display()
        elif choice == 6:
            break        else:
            print("Wrong choice")
        print()

Data Structures & Algorithms Tutorials for Beginners

Circular Queue in Data Structure | DSA Tutorials