• Main Menu
  • Circular Queue


    The difficulty of managing front and rear in an array-based non-circular queue can be overcome if we treat the queue position with index 0 as if it comes after the last position (in our case, index 9), i.e., we treat the queue as circular. Note that we use the same array declaration of the queue.

    Empty queue:

    Empty circular queue

    Non-empty queues:

    Non-empty circular queue

    Non-empty circular queue

    Non-empty circular queue

    Implementation of operations on a circular queue:

    Testing a circular queue for overflow

    There are two conditions:

    • (front=0) and (rear=capacity-1)
    • front=rear+1

    If any of these two conditions is satisfied, it means that circular queue is full.

    .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; }

    bool isfull(queue *q)
    {
     if (((q->front==0)&&( q->rear==CAPACITY-1))||( q->front==q->rear+1))
     return true;
     else
     return false;
    }

    Note: bool can be defined as typedef enum {false, true} bool;

    The enqueue Operation on a Circular Queue

    There are three scenarios which need to be considered, assuming that the queue is not full:

    1. If the queue is empty, then the value of the front and the rear variable will be -1 (i.e., the sentinel value), then both front and rear are set to 0.
    2. If the queue is not empty, then the value of the rear will be the index of the last element of the queue, then the rear variable is incremented.
    3. If the queue is not full and the value of the rear variable is equal to capacity -1 then rear is set to 0.

    void enqueue(queue *q, int value) /*assumes queue is not full*/
    {
     /*adjust rear variable*/
     if (q->front==-1)
     q->front=q->rear=0;
     else if (q->rear==CAPACITY-1)
     q->rear=0;
     else
     q->rear++;
     /*store element at new rear */
     q->elements[q->rear]=value;
    }

    The dequeue Operation on a Circular Queue

    Again, there are three possibilities:

    1. If there was only one element in the circular queue, then after the dequeue operation the queue will become empty. This state of the circular queue is reflected by setting the front and rear variables to -1.
    2. If the value of the front variable is equal to CAPACITY-1, then set front variable to 0.
    3. Ifneither of the above conditions hold, then the front variable is incremented

    int dequeue(queue *q)
    { 
     int temp=q->elements[q->front]; /*store the front element in a temporary variable, so that we return this value later */
     
     /*adjust front variable */ 
     if (q->front == q->rear)
     q->front = q->rear=-1;
     else if (q->front == CAPACITY-1)
     q->front = 0;
     else
     q->front++;
     
     return temp; /*return the dequeued element*/
    }

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    4 comments
    1. Ravi

      24 September, 2012 at 7:39 pm

      So this Overflow condition occurs only when we’ve already chosen some capacity (like we are statically assigning some memory & then using) for our queue. & hence two conditions. 1. (front=0) and (rear=capacity-1) 2. front=rear+1

      If we are implementing Circular Queue by dynamic allocation of memory then there’s no Overflow condition (provided allocation never fails)

      Reply
    2. kibrom

      10 December, 2011 at 7:05 pm

      I think buzzzzzz on testing for empty and full

      Reply
    3. rishi

      10 March, 2011 at 6:45 pm

      any body knows how to identify front and rear in circular queqe

      Reply
      • suraj

        28 August, 2011 at 5:59 pm

        initially we can assume any index as front & rear…but keep rear is one less than the front…(eg if f=0,r=-1)….it is not compulsory …but it will give u better result….try it …im waiting for ur reply…..thanx… 

        Reply
    C
    174 queries in 0.587 seconds.