Data Structure Circular Queue

Introduction to Circular Queue

A circular queue is a type of data structure that follows the First-In-First-Out (FIFO) principle. It is a linear data structure in which the operations are performed in a circular manner. In a circular queue, the last element is connected to the first element to form a circular chain.

One of the main advantages of using a circular queue is its efficient use of memory. Unlike a regular queue, where the elements are stored in a linear manner, a circular queue allows for the reutilization of empty spaces. When an element is dequeued from the front of the queue, the space it occupied becomes available for storing new elements. This circular nature of the queue allows for a more efficient use of memory, especially in scenarios where the queue is constantly being enqueued and dequeued.

Another advantage of a circular queue is its ability to handle situations where the queue becomes full. In a regular queue, once all the available spaces are filled, further enqueuing of elements is not possible. However, in a circular queue, when the rear pointer reaches the end of the queue, it wraps around to the beginning of the queue, allowing for new elements to be enqueued and overwriting the oldest elements in the queue.

Implementing a circular queue involves keeping track of two pointers: the front and the rear. The front pointer indicates the position of the first element in the queue, while the rear pointer indicates the position where the next element will be enqueued. Initially, both the front and rear pointers are set to -1, indicating an empty queue. As elements are enqueued, the rear pointer is incremented, and as elements are dequeued, the front pointer is incremented.

When implementing a circular queue, it is important to handle certain edge cases. For example, if the front and rear pointers are both pointing to -1, it means the queue is empty. Similarly, if the front and rear pointers are pointing to the same position, it means the queue is full. These edge cases need to be considered when performing enqueue and dequeue operations on the circular queue.

In conclusion, a circular queue is a useful data structure that allows for efficient memory utilization and handling of full queues. It is commonly used in scenarios where elements need to be enqueued and dequeued in a circular manner, such as in scheduling algorithms, buffer management, and CPU task management.

7. Size

The size operation returns the number of elements currently present in the circular queue. It does not modify the queue in any way.

8. Clear

The clear operation removes all the elements from the circular queue, making it empty. After this operation, the size of the queue will be zero.

9. Peek

The peek operation returns the element at a specified position in the circular queue without removing it. The position is provided as a parameter to the operation.

10. Search

The search operation returns the position of a specified element in the circular queue. If the element is not found, it returns -1.

These operations provide the necessary functionality to manipulate and retrieve data from a circular queue. They can be used in various applications where a circular queue is required, such as implementing a buffer or managing a fixed-size collection of items.

It is important to note that the circular queue has a fixed capacity, which means that once the queue is full, no more elements can be added until some elements are dequeued. This property makes it suitable for scenarios where a fixed amount of memory is available and needs to be efficiently managed.

Implementation of Circular Queue

Let’s see an example implementation of a circular queue in Python:

class CircularQueue:
    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.front = self.rear = -1
    def enqueue(self, data):
        if self.isFull():
            return "Queue is full"
        elif self.isEmpty():
            self.front = self.rear = 0
            self.queue[self.rear] = data
        else:
            self.rear = (self.rear + 1) % self.k
            self.queue[self.rear] = data
    def dequeue(self):
        if self.isEmpty():
            return "Queue is empty"
        elif self.front == self.rear:
            temp = self.queue[self.front]
            self.front = self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.k
            return temp
    def front(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.queue[self.front]
    def rear(self):
        if self.isEmpty():
            return "Queue is empty"
        return self.queue[self.rear]
    def isEmpty(self):
        return self.front == -1
    def isFull(self):
        return (self.rear + 1) % self.k == self.front

The above code snippet demonstrates the implementation of a circular queue in Python. A circular queue is a data structure that follows the First-In-First-Out (FIFO) principle, where the elements are added at the rear and removed from the front. In a circular queue, the rear and front pointers wrap around to the beginning of the queue when they reach the end, creating a circular behavior.

The CircularQueue class has several methods to perform operations on the circular queue:

• __init__(self, k): This is the constructor method that initializes the circular queue with a maximum size of k. It also initializes the queue array with None values and sets the front and rear pointers to -1.
• enqueue(self, data): This method adds an element to the circular queue. It checks if the queue is full using the isFull() method and returns “Queue is full” if it is. If the queue is empty, it sets the front and rear pointers to 0 and adds the element at the rear. If the queue is not empty, it increments the rear pointer using modulo arithmetic and adds the element at the new rear position.
• dequeue(self): This method removes and returns the element at the front of the circular queue. It checks if the queue is empty using the isEmpty() method and returns “Queue is empty” if it is. If the front and rear pointers are equal, indicating that there is only one element in the queue, it removes the element and resets the front and rear pointers to -1. If there are multiple elements in the queue, it removes the element at the front position, increments the front pointer using modulo arithmetic, and returns the removed element.
• front(self): This method returns the element at the front of the circular queue. It checks if the queue is empty using the isEmpty() method and returns “Queue is empty” if it is. Otherwise, it returns the element at the front position.
• rear(self): This method returns the element at the rear of the circular queue. It checks if the queue is empty using the isEmpty() method and returns “Queue is empty” if it is. Otherwise, it returns the element at the rear position.
• isEmpty(self): This method checks if the circular queue is empty by comparing the front pointer to -1. If the front pointer is -1, it means the queue is empty, and the method returns True. Otherwise, it returns False.
• isFull(self): This method checks if the circular queue is full by comparing the incremented rear pointer to the front pointer using modulo arithmetic. If the incremented rear pointer is equal to the front pointer, it means the queue is full, and the method returns True. Otherwise, it returns False.

This implementation of a circular queue provides a way to efficiently manage elements in a fixed-size queue, allowing for constant-time enqueue and dequeue operations. It ensures that the queue wraps around when it reaches the end, making it a suitable data structure for scenarios where the order of elements matters and the size of the queue is known in advance.

Example Usage of Circular Queue

Let’s consider an example to understand how a circular queue works:

queue = CircularQueue(5)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
print(queue.dequeue())  # Output: 1
print(queue.front())  # Output: 2
print(queue.rear())  # Output: 5
queue.enqueue(6)  # Output: "Queue is full"
queue.dequeue()  # Output: 2

In the above example, we create a circular queue with a maximum capacity of 5. This means that the queue can hold up to 5 elements at a time. We start by enqueueing elements 1, 2, 3, 4, and 5 into the queue. The enqueue operation adds elements to the rear end of the queue. So, after enqueueing these elements, the queue will look like this: [1, 2, 3, 4, 5].

Next, we perform a dequeue operation, which removes the element from the front end of the queue. In this case, the first element in the queue is 1, so it gets removed. The dequeue operation returns the removed element, which in this case is 1. So, the output of the first print statement is 1.

After the dequeue operation, the queue will look like this: [2, 3, 4, 5].

To check the front element of the queue, we use the front() function. This function returns the element at the front end of the queue without removing it. In this case, the front element is 2, so the output of the second print statement is 2.

The rear() function returns the element at the rear end of the queue without removing it. In this case, the rear element is 5, so the output of the third print statement is 5.

Finally, we try to enqueue element 6 into the queue. However, since the queue is already full with a maximum capacity of 5, the enqueue operation returns an error message: “Queue is full”.

To further demonstrate the circular nature of the queue, we perform another dequeue operation. This removes the front element, which is now 2. After this operation, the queue will look like this: [3, 4, 5].

4. Support for Wraparound Operations

One of the key advantages of circular queues is their ability to support wraparound operations. In a circular queue, the last element is connected to the first element, creating a circular structure. This allows for seamless insertion and removal of elements at both ends of the queue.

For example, if the circular queue is full and an element needs to be inserted, it will wrap around to the beginning of the queue and replace the oldest element. Similarly, if the circular queue is empty and an element needs to be removed, it will wrap around to the end of the queue and retrieve the most recently inserted element.

This wraparound functionality is particularly useful in scenarios where the queue needs to maintain a fixed size and older elements need to be automatically discarded when new elements are added. It eliminates the need for resizing the queue or shifting elements, resulting in improved performance and efficiency.

5. Flexibility in Implementation

Circular queues offer flexibility in their implementation. They can be implemented using arrays or linked lists, depending on the specific requirements of the application. Arrays provide constant time access to elements, making them suitable for scenarios where random access is important. On the other hand, linked lists offer dynamic memory allocation and deallocation, making them more suitable for scenarios with varying queue sizes.

This flexibility allows developers to choose the most appropriate implementation based on factors such as memory constraints, performance requirements, and ease of use.

6. Support for Multiple Applications

Due to their efficient memory utilization, constant time complexity, and flexibility in implementation, circular queues can be used in a wide range of applications. Some common applications include:

• Operating systems: Circular queues are used in scheduling algorithms to manage the execution of processes in a circular manner.
• Networking: Circular queues are used in buffer management to store incoming and outgoing data packets.
• Simulation: Circular queues are used to model real-world scenarios where entities need to be processed in a circular fashion, such as event-driven simulations.
• Data structures: Circular queues can be used as a building block for other data structures, such as circular buffers or circular linked lists.

Overall, the advantages of circular queues make them a valuable tool in various domains, providing efficient and flexible solutions to a wide range of problems.