1. What is a circular queue? Write a C program for static implementation of Circular Queue.

A circular queue is a queue which wraps around itself. It has no begining and no end.

Circular queue has the advantage that if there is space at the front of the array instead of rear end, elements can be inserted there too.

Ordinary queue gives queue overflow error when rear>=MAX. Even if we remove some elements from front of queue and make space, the error still persists because rear is still greater than MAX.

In order to add values to queue if there is place in it, we should be able to set rear to 0th element if rear is MAX and 0th element is empty.

That is the idea behind circular queue. In a circular queue enqueue and dequeue use %(modulo) operator to find the index of array to add or remove elements.

Enqueue:
arr[rear%MAX]=newvalue; rear++;
Dequeue
num= arr[front%MAX] ;
front++;
return num;

To find if the queue is empty we mainitain a variable - count. If count is 0, queue is empty. If count is MAX, queue is full.

#include<stdio.h>
#define MAX 5

struct queue 
{
    int arr[MAX];
    int front,rear;
    int count;
};

void init(struct queue *qp)
{
    qp->front = qp->rear = -1;
    qp->count = 0;
}

int is_empty(struct queue *qp)
{
    return qp->count==0;
}

int is_full(struct queue *qp)
{
    return qp->count==MAX;
}
 
void enqueue(struct queue *qp,int num)
{
     if(is_full(qp))
    {
     printf("The queue is full. Can not add elements...");
    }
    else
    {
     (qp->rear)++;
     int index  = qp->rear % MAX;      
     qp->arr[index] = num;
     
     (qp->count)++;
     if(qp->front==-1)
         qp->front  = 0;
    }
      
}
 

int dequeue(struct queue *qp)
{
    int temp = -1;
    if(is_empty(qp))
    {
      printf("Queue is empty");
    }
    else
    {
      int index =  qp->front %MAX;
      temp = qp->arr[index];
      (qp->front)++;
      (qp->count)--;
    }
    return temp;
}

void print_queue(struct queue *qp)
{
    int i;
    printf("Queue is ");
    for(i = qp->front;i<=qp->rear;i++)
    printf("%d---",qp->arr[i%MAX]);
    printf("\n");
}

    
int main()
{
   struct queue q1;
   init(&q1);
    
   while(1)
   {
    printf("Enter 1 - enqueue 2 - dequeue 3 - exit");
    int opt;
    scanf("%d",&opt);
    if(opt==1)
    {
      int n;
      printf("Enter a number:");
      scanf("%d",&n);
      enqueue(&q1,n);
      print_queue(&q1);      
    }
    else if(opt==2)
    {      
      int n;         
      n = dequeue(&q1);
      if (n!=-1){
         printf("Value dequed is %d\n",n);
      print_queue(&q1);
     }
     }  
    else
     break; 
   }
   return 0;
}

2. Explain how queue is implemented using a linked list. Write functions to insert and delete elements to such a queue.

A queue can be implemented using doubly linked list. Such a queue can have two pointers - front and rear which are actually head and tail pointers of linked list.

When an element is enqueued, it is inserted after rear and rear pointer is updated. So enqueue will add an element after tail of linked list and tail is changed to this new node.

When an element is dequeued, it is deleted from front and front is updated. Dequeue operation will remove a node from head of the list, and head is changed to head->next.

The queue is empty when rear is NULL.

All operations have a time complexity of O(1), just like array implementation. But unlike array implementation, there is no restriction on size of queue.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;  
   struct node *prev;  
 };  
 typedef struct node * NODEPTR;  
  
 struct queue 
 {
    NODEPTR front;
    NODEPTR rear;
  };

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->prev = temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 int dequeue(struct queue *qp)  
 {  
    if(qp->front==NULL)
    {
      printf("Queue empty...\n");
      return -1;
    }
    NODEPTR nd = qp->front;
    if(qp->rear==qp->front)//deleting the only node
       qp->rear = NULL;
    qp->front = qp->front->next;
    if(qp->front!=NULL)
          qp->front->prev= NULL;
    int num = nd->n;
    free(nd);
    return num;    
 } 
 void enqueue(struct queue *qp, int num)  
 {  
    NODEPTR newnode = create_node(num);
    if(qp->rear!=NULL)
    	qp->rear->next = newnode;  
    newnode->prev = qp->rear;  
    qp->rear = newnode; 
    if(qp->front==NULL)
      qp->front = qp->rear;     
 }  
 void display_queue(struct queue *qp)  
 {  
   NODEPTR temp = qp->front; 
   while(temp!=NULL)
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
 }  
 int main()  
 {  
     struct queue q1;
     q1.front = q1.rear = NULL;
     while(1)
     {
       int option, number;
       printf("Enter 1-enqueue 2 - dequeue 3- display 4 - exit:");
       scanf("%d",&option);
       if(option==1)
       {
             printf("Enter number to enqueue:");
             scanf("%d",&number);
             enqueue(&q1,number);
       }
       else if(option==2)
       { 
             number = dequeue(&q1);
	     if(number !=-1)
                printf("Number dequeued is %d\n",number);
       }
       else if(option==3)
            display_queue(&q1);
       else if(option==4)
            break;
      }    
 }

3. Implement a queue with two stacks. Please implement two functions: appendTail to append an element into tail of a queue, and deleteHead to delete an element from head of a queue.

The idea here is that we need to have a FIFO behaviour using stacks. Stack is a LIFO data structure. But using two stacks, we can reverse already reversed input and we get back original data set.

To implement a queue using stack, we can make either push operation expensive or pop operation expensive.

we need to either make enqueue as simple push operation and dequeue as popping all elements and pushing them back to second stack

or we need to make enqueue with push,pop all elements and push operations and dequeue as just pop.

1) Enqueue n
push n into first stack

2) Dequeue
if second stack is emptu
while first stack is not empty
pop the value from first stack
push value to second stack
Now pop a value from second stack

#include<stdio.h>  
#include<stdlib.h>
#define ERROR -1000
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR push(NODEPTR top,int val)
 { 
     NODEPTR newnode = create_node(val);
     newnode->next = top;
     top = newnode;
     return top;
}
int isempty(NODEPTR top)
{
   return top==NULL;
}
int pop(NODEPTR *topPtr)
{
   if(isempty(*topPtr))
       return ERROR;
   int num = (*topPtr)->n;
   NODEPTR temp = *topPtr;
   *topPtr = (*topPtr)->next;
   free(temp);
   return num;
}
/*enqueue using push*/
void enqueue(NODEPTR *top1,int val)
{     
    *top1 = push(*top1,val);
}
/*dequeue is expensive*/
/*pop all to second stack from first
now return top value from second*/
int dequeue(NODEPTR *topptr1,NODEPTR *topptr2)
{
    if(isempty(*topptr2))
    while(!isempty(*topptr1))
        {
        int a = pop(topptr1);
        *topptr2 = push(*topptr2,a);
        }
    return pop(topptr2);
} 
 int main()  
 {  
     NODEPTR top1 = NULL,top2=NULL;
     NODEPTR nd;

     while(1)
     {  
       int option,value; 
       printf("Enter 1- nq 2- dq 3 - exit"); 
       scanf("%d",&option);
       if(option==3)
          break;
       switch(option)
       {
           case 1:  printf("new value to enqueue=");  
            scanf("%d",&value);   
            enqueue(&top1,value);
            break;
           case 2:  value = dequeue(&top1,&top2);
            if(value==ERROR)
              printf("Queue empty\n");
            else
              printf("Value removed is %d\n",value);
            break; 
        }  
    }     
 }

4. What is a deque?

A deque is a double-ended queue. This is a data structure wherein elements can be inserted or removed from either end, but not from the middle.

In a normal queue - elements are added only from rear end and removed only from front end.

We can even have restricted deques -

input restricted deque - where values can be added only to rear end of queue but removed from both the ends of queue.

output restricted deque - where values can be removed only from front end of queue but added to both the ends of queue.

5. Write a function to count the number of nodes in a circular queue

#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;
}
void enqueue(QUEUE *q1,int n)
{
   NODEPTR temp = create_node(n);
   if(is_empty(q1))
      {
        q1->rear = q1->front = temp;
        temp->next = temp;
      }
    else{
      q1->rear->next = temp;
      q1->rear = temp;
      temp->next = q1->front;
   }  
}

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;
   else
      q1->rear->next = q1->front;
   return m;
}

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

int count(QUEUE q1)
{
    NODEPTR temp = q1.front;
    int c=0;
    do
    {
        c++;
        temp = temp->next;
    }while(temp!=q1.front);
    return c;
}
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;
     }
     printf("Number of nodes in the queue is %d\n",count(q1));
     return 0;
}

6. Write a program to implement a deque using linked list.

A deque or a double ended queue allows values to be added to front of queue as well as rear of queue.

In this program all functions except dequeue_rear have O(1) time complexity. dequeue_rear has O(n) time complexity. Because after removing a last node of queue, previous node of this should be set as q1->rear.

But we can avoid this by using doubly linked list for implementing a dequeue

#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;
   }  
}

void enqueue_front(QUEUE *q1,int n)
{
    NODEPTR temp = create_node(n);
    if(is_empty(q1))
        q1->rear = q1->front=temp;
    else
    {
        temp->next = q1->front;
        q1->front = temp;
     }
} 
NODEPTR find_previous(QUEUE q1,NODEPTR nd)
{
     NODEPTR temp=q1.front;
     while(temp!=NULL)
     {
        if(temp->next ==nd)
           return temp;
        temp = temp->next;
     }
     return 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;
}
int dequeue_rear(QUEUE *q1)
{
    if(is_empty(q1))
       return -1;
    NODEPTR temp = q1->rear;
    int val = temp->num;
    NODEPTR prevnode = find_previous(*q1,temp);
    if(prevnode==NULL)
       {
          q1->rear = q1->front = NULL;
       }
    else
      {
        prevnode->next = NULL;
        q1->rear = prevnode;
      }
   free(temp);
   return val;   
}
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 at rear 2 - remove a node from front 3 - Add a node at front 4 - Remove a node from rear  5 - quit\n");
       scanf("%d",&ans);
       if (ans==1 || ans==3)
       {
	   int n;
           printf("Node to enqueued:");
	   scanf("%d",&n);
           if(ans==1)
              enqueue(&q1,n);
           else
              enqueue_front(&q1,n);
           display(q1);
        }else if (ans==2 || ans==4)
        {
            int n;
            if(ans==2)
                n = dequeue(&q1);
            else if(ans==4)
                n = dequeue_rear(&q1);
            if(n==-1)
               printf("The queue is empty");
            else
              { printf("The value dequed is %d\n",n);                           
 
            display(q1);}
         }
         else if(ans==5)
            break;
     }
     return 0;
}

7. What is queue data structure? Write a program to implement a queue using an array

A queue is a linear data structure where elements are added to rear of queue and elements are removed from front of queue. A queue is similar to a bus stop queue.

Enqueue - enqueue is the adding a new value to the rear end of queue.
Dequeue - is removing a value from begining of a queue.
Both these operations have constant complexity. (O(1))

A queue can be implemented using an array or a linked list.

To implement a queue using an array, we need two integers to store front and rear ends of a queue.

enqueue -- arr[rear++]=val
dequeue return arr[front++]
isempty - return rear==front
isfull - return rear>=MAX

#include<stdio.h>
#define MAX 5
 
void enqueue(int  arr[],   int *rearptr,int num)
{
    if(*rearptr == MAX)
    {
        printf("Queue is full");
     }
    else
    {
        arr[*rearptr]=num;
       (*rearptr)++;
    }
      
}
int is_empty(int front,int rear)
{
   return front==rear;
}

int dequeue(int  arr[],int *frontptr,int *rearptr)
{
    int temp = -1;
    if(*frontptr==*rearptr)
    {
       printf("Queue is empty");
    }
    else
    {
        temp = arr[*frontptr];
        (*frontptr)++;
     }
     return temp;
}

void print_queue(int *arr,int front, int rear)
{
    int i;
    for(i = front;i<rear;i++)
       printf("%d---",arr[i]);
    printf("\n");
} 
 
int main()
{
   int arr[MAX];
   int i ;
   int front =0,rear = 0;
   while(1)
   {
       printf("Enter 1 - enqueue 2 - dequeue 3 - exit");
       int opt;
       scanf("%d",&opt);
       if(opt==1)
      {
         int n;
         printf("Enter a number:");
         scanf("%d",&n);
         enqueue(arr,&rear,n);
         print_queue(arr,front,rear);
      }
    else if(opt==2)
    {      
        int n;         
        n = dequeue(arr,&front,&rear);
        if (n!=-1)
           printf("Value dequed is %d\n",n);
        print_queue(arr,front,rear);
     }  
    else
     break;
   }
   return 0;
}

Queue Questions