Double Ended Queue

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

In dequeue, there are two pointer 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: