Circular Queue Data Structure in Java, easy in 5 minutes

The post shows you about Circular Queue Data Structure in Java and how to implement Circular Queue Data Structure in Java. Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Circular queue saves the space more than a normal queue implementation using arrays. In normal queue , once queue becomes full, we can not insert the next element even if there is a space in front of queue.

Circular Queue Data Structure in Java

How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment any variable and we reach the end of queue, we start from the beginning of queue by modulo division with the queue size.

Queue operations work as follows:

  • Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
  • When initializing the queue, we set the value of FRONT and REAR to -1.
  • Enqueue an element, we circularly increase the value of REAR index and place the new element in the position pointed to by REAR. Before enqueing, we check if queue is already full.
  • Dequeue an element, we return the value pointed to by FRONT and circularly increase he FRONT index. Before dequeuing, we check if queue is already empty.
  • When enqueing the first element, we set the value of FRONT to 0.
  • When dequeing the last element, we reset the values of FRONT and REAR to -1.

Implement Circular Queue Data Structure in Java using array.

The most common queue implementation is using arrays, but it can also be implemented using lists, eg: ArrayList, LinkedList.

Here is output of the above program

Implement Circular Queue in Java using array, Circular Queue Data Structure in Java

Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) time because there is no loop in any of the operations.

Use of Circular Queue

  • Memory Management: The unused memory locations in the case of normal queues can be utilized in circular queues. It saves spaces.
  • Traffic system: Circular queues are used to switch on the traffic lights one by one repeatedly as per the time set in the traffic system.
  • CPU Scheduling: Operating systems (e.g: Windows, Linux) often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

That’s all about Circular Queue Data Structure in Java.

References
Queue Data Structure in Java


Data Structures and Algorithms Tutorial in Java

Please share it if you found this useful
Hide Buttons