Queue data structure

Queue is a linear data structure to which values are added and removed using FIFO method - first in first out. That is to say, the value which is added first, will be removed first from the queue. Exactly like the behavior of a real life queue.

The other related data structure is stack, from which elements are added and removed using LIFO method - last in first out.

Terminology

An element is always added to the rear end of the queue. This operation is called enqueue. 

An element is added from the front end of the queue. The operation of removing an element is called dequeue operation.

Implementation of queue

You can implement a queue using an array or a linked list. Array poses the problem that it is limited by its size. But by making the array as circular, queue can be implemented. Here when the array index reaches maximum value, queue insertion happens at the beginning of the array.

But implementation of a queue with linked list is not having such limitations. If you just add one more pointer for front end of the queue, all operations can be implemented with O(1) complexity.

Let us look at the algorithm for queue using linked list

• Enqueue operation
• create a new node
• if rear is NULL, rear = front = newnode
• else link rear node to newnode
• set rear as newnode
•  Dequeue operation
• if queue is empty return error code
• set temp to front
• set front to next node of front
• free the memory allocated to front node
• return the value of temp
• IsEmpty
•  if front = null and rear = null return true

Do not forget the initialize the queue by setting front and rear equal to NULL. You don't want to get segmentation fault.

Enqueue operation

NODEPTR create_node(int n)
{
    NODEPTR newnode = malloc(sizeof(struct node));
    newnode->num = n;
    newnode->next = NULL;
    return newnode;
}

void enqueue(QUEUE *q1,int n)
{
   NODEPTR temp = create_node(n);
   if(is_empty(q1))
      {
 q1->rear = q1->front = temp;
    }
    else{
      q1->rear->next = temp;
      q1->rear = temp;
   }  
}

Next let us look at dequeue function

int is_empty(QUEUE *q1)
{
    return (q1->front==NULL  && q1->rear==NULL);
}
int dequeue(QUEUE *q1)
{
   if(is_empty(q1))
     return -1;
   
   NODEPTR temp = q1->front;
   int m = temp->num;
   q1->front = q1->front->next;
   free(temp);
   if(q1->front==NULL)
      q1->rear = NULL;
   return m;
}

I have added an additional line in dequeue function, if the q1->front = NULL then even q1->rear = NULL, because when all the nodes are removed from the queue, both pointers must be NULL.

And here is the complete program.

#include<stdio.h>
#include<stdlib.h>
struct node 
{
   int num;
   struct node *next;
};

typedef struct node *NODEPTR;

struct queue
{
    NODEPTR front,rear;
};

typedef struct queue QUEUE;

 
NODEPTR create_node(int n)
{
    NODEPTR newnode = malloc(sizeof(struct node));
    newnode->num = n;
    newnode->next = NULL;
    return newnode;
}
int is_empty(QUEUE *q1)
{
    return (q1->front==NULL  && q1->rear==NULL);
}
void enqueue(QUEUE *q1,int n)
{
   NODEPTR temp = create_node(n);
   if(is_empty(q1))
      {
 q1->rear = q1->front = temp;
    }
    else{
      q1->rear->next = temp;
      q1->rear = temp;
   }  
}

int dequeue(QUEUE *q1)
{
   if(is_empty(q1))
     return -1;
   
   NODEPTR temp = q1->front;
   int m = temp->num;
   q1->front = q1->front->next;
   free(temp);
   if(q1->front==NULL)
      q1->rear = NULL;
   return m;
}

void display(QUEUE q1)
{
   NODEPTR node=q1.front;
   printf("\nThe list is \n");
   while(node !=NULL)
   {
     printf("%d----",node->num);
     node = node->next;
   }
} 

int main()
{
    QUEUE q1;
    /*initialize queue*/
    q1.front = q1.rear = NULL;
    
    while(1)
    {
 int ans;
       printf("Enter 1 - Add a node 2 - remove a node  3 - quit\n");
       scanf("%d",&ans);
       if (ans==1)
       {
    int n;
           printf("Node to enqueued:");
    scanf("%d",&n);
           enqueue(&q1,n);
           display(q1);
        }else if (ans==2)
        {
            int n;
            n = dequeue(&q1);
            if(n==-1)
               printf("THe queue is empty");
            else
               printf("The value dequed is %d\n",n);
            display(q1);
         }
         else
            break;
     }
     return 0;
}