Circular Queue using Arrays

In this module, we will cover

  • What's the core idea behind a circular queue
  • why the circular queue is needed?
  • Basic operations of the circular queue
  • Array implementation of the circular queue in c++
  • Explanation of code
  • use of modular arithmetic
A queue where the start and end of the queue are joined together is a circular queue.

Why the circular queue needed?

For complete utilization of space available

Array implementation of circular queue

Basic operations :

  1. isFull( ) : check if the queue is full ( when head = ( tail + 1 ) % max_size )
  2. isEmpty( ) : check if the queue is empty
  3. enqueue( x ) : add a new element x to the back of the queue ( tail = ( tail + 1 ) % max_size )
  4. dequeue( ) : remove the front value from the queue ( head = ( head + 1 ) % max_size )
  5. headElement( ) : returns the head element of the queue
  6. tailElement( ) : returns the tail element of the queue
  7. clearQueue( ) : empties the queue

Code :


Explanation of Code :

 Initially 12, 35, 99, 22 are inserted and then dequeue operation is performed once
enqueue( 68 )

enqueue( 54 )
dequeue( )
enqueue( 17 )
enqueue( 81 )
enqueue( 43 )

enqueue( 67 )
Since the queue is FULL now, the further insertion will lead to overflow conditions!!

clearQueue( ) , queue is emptied 

dequeue( )

Since the queue is EMPTY now, further deletion will lead to underflow conditions!!

so tail starts at 4, goes to 5, goes to 6, goes to 7, goes to 0, goes to 1 etc
4 -> 5 -> 6 -> 7 -> 0 -> 1
that's why tail = ( tail + 1 ) % 8  [ here 8 is MAXSIZE ]
tail % 8 works as follows
4 % 8 = 4
5 % 8 = 5
6 % 8 = 6
7 % 8 = 7
8 % 8 = 0
9 % 8 = 1

Any doubts related to the topics discussed above can be mentioned in the comment section
In the subsequent modules, we will focus on problem-solving using the concept of stack, queue, deque and circular queue

Thank You

Comments