Implementation of operations on a linear queue:

Creating an Empty Queue

Before we can use a queue, it must be created. The purpose of initializing the queue is served by assigning -1 (as a sentinel value) to the front and rear variables. Note that the valid range of an index for the array is 0 to CAPACITY-1.

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

void createqueue(queue *q)
{
 q->front=q->rear=-1;
}

Testing the Queue for Underflowline r-queue

bool isempty(queue q)
{
 if(q.front==-1)
 return true;
 else
 return false;
}

Testing the Queue for Overflow

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

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

Performing the enqueue Operation on a Linear Queue

There are two scenarios that we should consider, assuming that the queue is not full.

  1. If the linear queue is empty, then the value of the front and the rear variable will be -1 (the sentinel value), then both front and rear are set to 0.
  2. If the linear queue is not empty, then there are two further possibilities:

    1. If the value of the rear variable is less than CAPACITY-1, then the rear variable is incremented.
    2. If the value of the rear variable is equal to CAPACITY-1, then the elements of the linear queue are moved forward, and the front and rear variables are adjusted accordingly.

C Code

void enqueue(queue *q, int value)
{
 int i;
 if(isempty(*q))
 q->front=q->rear=0;
 else if (q->rear==CAPACITY-1)
 {
 for(i=q->front;i<=q->rear;i++)
 q->elements[i-q->front]=q->elements[i];
 q->rear=q->rear-q->front+1;
 q->front=0;
 }
 else
 {
 q->rear++;
 }
&nbs; q->elements[q->rear]=value;
}

Performing the dequeue Operation on a Linear Queue

There are two possibilities:

  1. If there is only one element in the linear queue then after dequeueing it will become empty. This state of the linear queue is reflected by setting the front and rear variables to -1, the sentinel value.
  2. Otherwise, the value of the front variable is incremented.

C Code

int dequeue(queue *q)
{
 int temp;
 temp=q->elements[q->front];
 if(q->front==q->rear)
 q->front=q->rear=-1;
 else
 q->front++;
 return temp;
}

Complete Program

/*
 * Linear Queue
 * http://www.byteguide.com
 */
 
#include <stdio.h>
 
#define CAPACITY 10
typedef struct
{
 int front;
 int rear;
 int elements[CAPACITY];
} queue;
 
 
typedef enum {false, true} bool;
void createqueue(queue *);
bool isempty(queue );
bool isfull(queue );
void enqueue(queue *, int );
int dequeue(queue *);
void display(queue );
 
int main()
{
 queue q;
 int elem, count;
 
 createqueue(&q);
 printf("Enter integers to enqueue or -99 to stop: ");
 scanf("%d", &elem);
 for (count=0; elem!=-99 && count<CAPACITY; count++)
 {
 enqueue(&q, elem);
 puts("Now, the queue is (front..to..rear): ");
 display(q);
 printf("nEnter another element: ");
 scanf("%d", &elem);
 }
 puts("nDequeueing elements...");
 while (!isempty(q))
 {
 dequeue(&q);
 printf("An element has been dequeued...the queue is now: ");
 display(q);
 }
 
 return 0;
}
void createqueue(queue *q)
{
 q->front=q->rear=-1;
}
bool isempty(queue q)
{
 if(q.front==-1)
 return true;
 else
 return false;
}
bool isfull(queue q)
{
 if ((q.front==0) && (q.rear==CAPACITY-1))
 return true;
 else
 return false;
}
 
void enqueue(queue *q, int value)
{
 int i;
 if(isempty(*q))
 q->front=q->rear=0;
 else if (q->rear==CAPACITY-1)
 {
 for(i=q->front;i<=q->rear;i++)
 q->elements[i-q->front]=q->elements[i];
 q->rear=q->rear-q->front+1;
 q->front=0;
 }
 else
 {
 q->rear++;
 }
 q->elements[q->rear]=value;
}
int dequeue(queue *q)
{
 int temp;
 temp=q->elements[q->front];
 if(q->front==q->rear)
 q->front=q->rear=-1;
 else
 q->front++;
 return temp;
}
 
void display(queue q) 
{
 int i;
 if (!isempty(q))
 {
 for (i=q.front; i<=q.rear; i++)
 printf(" %d -->", q.elements[i]);
 
 printf("bbb n"); /*erase the last arrow*/
 }
 else
 puts("Empty");
}

Output

Enter integers to enqueue or -99 to stop: 7 Now, the queue is (front..to..rear): 7

Enter another element: 4 Now, the queue is (front..to..rear): 7 –> 4

Enter another element: 8 Now, the queue is (front..to..rear): 7 –> 4 –> 8

Enter another element: 2 Now, the queue is (front..to..rear): 7 –> 4 –> 8 –> 2

Enter another element: -99

Dequeueing elements… An element has been dequeued…the queue is now: 4 –> 8 –> 2 An element has been dequeued…the queue is now: 8 –> 2 An element has been dequeued…the queue is now: 2 An element has been dequeued…the queue is now: Empty