Queues and its implementation in C

A Queue is a First In First Out (FIFO) which is an ordered collection of items which are deleted at the front end and inserted at the rear end. A simple queue is represented as below –

Simple Sequential Queue

A Queue in C may be defined as an array as –

#define QMAX 80
struct Queue{
             int item[QMAX];
             int rear = -1, front=0;
            }q;

item[] stores the elements of the Queue and rear, front are variables which represents positions of insertion and deletion in the queue. Initially, R_e = -1, f_r = 0.

Two basic functions are required for representing a queue => Qinsert(q,x), Qdelete(q), where x is the element(int, char) to be inserted.Another function empty(&q) could also be used to check whether queue is empty or not. An ordinary Queue encounters Queue overflow and underflow. Overflow occurs when pq->rear > QMAX – 1 and Underflow occurs when pq->front > pq->rear. Various Queue manipulation functions could be implemented as follows –

/*insert function*/
call  qinsert(&q,x)

void qinsert(struct queue *pq, int x){
              if(pq->rear > = MAX - 1)
                  printf("\n Queue Overflow");
              else{
                  (pq->rear)++;
                  pq->items[pq-rear] = x;
              }
              return;
}

/*delete function*/
call  qdelete(&q)

void qdelete(struct queue *pq){
              empty(pq);
              if(pq->front > = pq->rear)
                  printf("\n Queue Underflow");
              else{
                  (pq->front)++;                  
              }
              return;
}

/*emptyfunction*/
call  empty(pq)

int empty(struct queue *pq){
    return(pq->front > pq->rear) ? TRUE : FALSE);
}

Circular Queues

In the case of Circular Queues, Queue overflow is eliminated by inserting elements in the deleted points of the queue as long as front != rear and front, rear != QMAX – 1.

Circular Queues could be represented in C as follows –

/*Basic representation*/
#define QMAX 80
struct CQueue{
             int item[QMAX];
             int front = rear = MAX - 1;
            }cq;

/*insert function*/
call  cqinsert(&cq,x)

void cqinsert(struct cqueue *pq, int x){
              if(pq->rear == MAX - 1)
                  pq->rear = 0;
              else
                  (pq->rear)++;
              if(empty(pq))   
                  printf("\nQueue underflow");
              else
                  pq->(items[pq->rear]) = x;
               return;
}

/*delete function*/
call  cqdelete(&cq)

void cqdelete(struct cqueue *pq){
              empty(pq);
              if(pq->front == MAX - 1)
                  pq->front = 0;
              else if(empty(pq))
                  printf("\n Queue Underflow");
              else
                  (pq->front)++;                              
              return;
}

/*emptyfunction*/
call  empty(pq)

int empty(struct cqueue *pq){
    return(pq->front == pq->rear) ? TRUE : FALSE);
}

Priority Queues

There are two types of priority queues – Ascending and Descending Priority queues. An Ascending priority queue is one in which always the item with minimum value is deleted first while in a descending priority queue, the item with the largest value is deleted first.

Ascending or Descending priority queues could be easily implemented by the same structure as an ordinary circular queue in which pq->front always prints to a smallest item pq->rear point to 1 ahead of the largest item. Deletion involves merely increasing pq->front by 1 in the case of a apq or decreasing pq->rear for a dpq. Insertion involves shifting and searching operations. Additional setting involves introducing an additional variable ‘priori’ in the queue structure and by maintaining a static int variable ‘count’ in the qinsert function.

An ascending priority queue may thus be implemented as below –

/*Basic representation*/
#define QMAX 80
struct apueue{
             int item[QMAX];
             int rear = MAX - 1;
             int priori;
            }apq;

/*insert function*/
call  apqinsert(&apq,x)

void apqinsert(struct apqueue *pq, int x){

              static int count = 0;

              if(pq->rear == MAX - 1)
                  pq->rear = 0;
              else{
                   (pq->rear)++;
                   pq->(items[pq->rear]) = x;
                   while(count == 0){
                      pq->priori = x; /* initialize to first item*/
                      break;                    
                   }
                   count++;
                   if(x < pq->priori)
                       pq->priori = x;
              }                  
              return;
}

/*delete function*/
call  apqdelete(&apq)

void apqdelete(struct apqueue *pq){
              if(pq->priori == NULL){       
                 printf("\n Empty");                       
                 return;
               }
               return(pq->priori);  /*returns the min value stored in pq->priori*/
}

Similarly, a descending priority queue may be implemented as below –

/*Basic representation*/
#define QMAX 80
struct apueue{
             int item[QMAX];
             int rear = MAX - 1;
             int priori;
            }dpq;

/*insert function*/
call  apqinsert(&dpq,x)

void apqinsert(struct apqueue *pq, int x){

              static int count = 0;

              if(pq->rear == MAX - 1)
                  pq->rear = 0;
              else{
                   (pq->rear)++;
                   pq->(items[pq->rear]) = x;
                   while(count == 0){
                      pq->priori = x; /* initialize to first item*/
                      break;                    
                   }
                   count++;
                   if(x < pq->priori)
                       pq->priori = x;
              }                  
              return;
}

/*delete function*/
call  apqdelete(&q)

void apqdelete(struct apqueue *pq){
              if(pq->priori == NULL){       
                 printf("\n Empty");                       
                 return;
               }
               return(pq->priori);  /*returns the min value stored in pq->priori*/
}