A Queue is a **F**irst **I**n **F**irst **O**ut (**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*/ }