Double Ended Queue

The double ended queue is a queue in which insertion and deletion are performed from either both ends of the queue. This is called head-tail linked list, as an element can be added or removed from either the head and tail of the queue.

In dequeue, there are two pointers LEFT and RIGHT.

A dequeue can have two variations-

• Input Restricted Dequeue- In this, insertion can be done only from one end and deletion can be done from both ends.
• Output Restricted Dequeue- In this, deletion can be done only from one end and insertion can be done from both ends.

Doubly Ended Queue Program

#include 
#include 
#define MAX 30 

typedef struct dequeue 
{ 
    int data[MAX]; 
    int rear,front; 
}dequeue; 

void create_dequeue(dequeue *p); 
int empty(dequeue *p); 
int full(dequeue *p); 
void insert_rear(dequeue *p,int x); 
void insert_front(dequeue *p,int x); 
int delete_front(dequeue *p); 
int delete_rear(dequeue *p); 
void print(dequeue *p); 

void main() 
{ 
    int i,x,y,che; 
    dequeue q;     
    create_dequeue(&q);     
    do 
    { 
	printf("\n Enter 1 to create double-ended queue");
	printf("\n Enter 2 to insert into queue [REAR]");
	printf("\n Enter 3 to insert into queue [FRONT]");
	printf("\n Enter 4 to delete from queue [REAR]");
	printf("\n Enter 5 to delete from queue [FRONT]");
	printf("\n Enter 6 to display all elements");
	printf("\n Enter 7 to exit");
	printf("\n----------------------");
	printf("\n Please Enter Your Choice: ");
	
        scanf("%d",&che); 
        
        switch(che) 
        { 
            case 1: printf("\nEnter number of elements:"); 
                    scanf("%d",&y); 
                    create_dequeue(&q); 
                    printf("\nEnter the data: ");                     
                    for(i=0;irear=-1; 
    P->front=-1; 
}  
int empty(dequeue *P) 
{ 
    if(P->rear==-1) 
        return(1); 
    
    return(0); 
}  
int full(dequeue *P) 
{ 
    if((P->rear+1)%MAX==P->front) 
        return(1); 
    
    return(0); 
}  
void insert_rear(dequeue *P,int x) 
{ 
    if(empty(P)) 
    { 
        P->rear=0; 
        P->front=0; 
        P->data[0]=x; 
    } 
    else 
    { 
		if(full(P)) 
		{ 
			printf("\nQueue Overflow"); 
			exit(0); 
		}  
		else {
        P->rear=(P->rear+1)%MAX; 
        P->data[P->rear]=x; 
		}
    } 
}  
void insert_front(dequeue *P,int x) 
{ 
    if(empty(P)) 
    { 
        P->rear=0; 
        P->front=0; 
        P->data[0]=x; 
    } 
    else 
    { 	
		if(full(P)) 
		{ 
			printf("\nQueue Overflow"); 
			exit(0); 
		}  
		else {
			P->front=(P->front-1+MAX)%MAX; 
			P->data[P->front]=x; 
		}
    } 
}  
int delete_front(dequeue *P) 
{ 
	if(empty(P)) 
	{ 
		printf("\nEmpty Queue "); 
		exit(0); 
	}
    int x;     
    x=P->data[P->front];     
    if(P->rear==P->front)   
        create_dequeue(P); 
    else 
        P->front=(P->front+1)%MAX;     
    return(x); 
}   
int delete_rear(dequeue *P) 
{ 
	if(empty(P)) 
	{ 
		printf("\nEmpty Queue "); 
		exit(0); 
	}
    int x;     
    x=P->data[P->rear];     
    if(P->rear==P->front) 
        create_dequeue(P); 
    else 
        P->rear=(P->rear-1+MAX)%MAX;         
    return(x); 
}  
void print(dequeue *P) 
{ 
    if(empty(P)) 
    { 
        printf("\nEmpty Queue "); 
        exit(0); 
    }     
    int i; 
    i=P->front;     
    while(i!=P->rear) 
    { 
        printf("\n%d",P->data[i]); 
        i=(i+1)%MAX; 
    }     
    printf("\n%d\n",P->data[P->rear]); 
}

Output of the above program:

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 1

Enter number of elements:5

Enter the data: 20
30
43
23
45

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 2

Insert Element : 55

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 3

Insert Element :87

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 6

87
20
30
43
23
45
55

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 4

 Deleted Element is 55

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 5

Deleted Element is 87

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: 6

20
30
43
23
45

 Enter 1 to create double-ended queue
 Enter 2 to insert into queue [REAR]
 Enter 3 to insert into queue [FRONT]
 Enter 4 to delete from queue [REAR]
 Enter 5 to delete from queue [FRONT]
 Enter 6 to display all elements
 Enter 7 to exit
----------------------
 Please Enter Your Choice: