[Data Structure] Circular Queue (Implementation with Array/C++)

You must’ve heard of queue before. When you apply for a course during the add/drop period in college, you’re put into the queue(waiting list) if the quota is full. Then, students who come first get into the course when some students decide to drop the class. This scenario clearly shows the structure of Queue. Queue is a linear & dynamic data structure with FIFO(First in First out) or LILO(Last in Last out) logic. Queue has various applications as CPU task scheduling, printer, or BFS(Breadth First Search) Algorithm, etc.

Queue Operations

• enqueue() //push
  - push to the back of queue
• dequeue() //pop
  - pop the front of queue
• count()
  - count the number of elements
• isEmpty()
• isFull()

Time Complexity Analysis

As we keep maintaining front & rear pointers, all these operations take O(1) time.

Front and rear are initialized as -1 denoting that there’s nothing in the queue. When you add for the first time, set both of them to 0. After that, for enqueue operation, increment rear by 1 unless queue isn’t full. Here, note that we’re dealing with circular queue so when rear gets to the last position of array, you have to rear = (rear+1)%size. It applies to the dequeue operation as well.

For count() operation, it might be a bit tricky. Look at the image below. When front≤rear, size = rear-front+1 and for front>rear, size = rear+queue size-front+1.

Implementation with Array

Circular Queue with Array