Double Ended Queue

A double-ended queue is an abstract data type similar to an simple queue, it allows you to insert and delete from both sides means items can be added or deleted from the front or rear end.

Algorithm:

  1. enqueue_rear
    Step-1: [Check for overflow]
    	if(rear==MAX)
    		Print("Queue is Overflow”);
            return;
    Step-2: [Insert element]
    	else
    		rear=rear+1;
    		q[rear]=no;      
    		[Set rear and front pointer]               
    		if rear=0
    			rear=1;
    		if front=0
    			front=1;
    Step-3: return
    
  2. enqueue_front
    Step-1: [Check for the front position]
    	if(front<=1)
    		Print (“Cannot add item at front end”);
    	return;
    Step-2: [Insert at front]
    	else
    		front=front-1;
    		q[front]=no;
    Step-3: Return
    
  3. dequeue_front
    Step-1: [ Check for front pointer]
    	if front=0
    		print(" Queue is Underflow”);
    	return;
    Step-2: [Perform deletion]        
    	else
    		no=q[front];
    		print(“Deleted element is”,no);
    		[Set front and rear pointer]     
    	if front=rear
    		front=0;
    		rear=0;
    	else
    		front=front+1;
    Step-3: Return
  4. dequeue_rear
    Step-1: [Check for the rear pointer]
    	if rear=0
    		print(“Cannot delete value at rear end”);
    	return;
    Step-2: [ perform deletion]
    	else
    		no=q[rear];
    		[Check for the front and rear pointer]
    	if front= rear
    		front=0;
    		rear=0;
    	else
    		rear=rear-1;
    		print(“Deleted element is”,no);
    Step-3: Return

Implementation

class node
{
public:
int data;
class  node *next;
class node *prev;
};
 
class dqueue: public node
{
  node *head,*tail;
  int top1,top2;
  public:
   dqueue()
   {
   top1=0;
   top2=0;
   head=NULL;
   tail=NULL;
   }
  void push(int x){
	node *temp;
	int ch;
	if(top1+top2 >=5)
	{
	  cout <<"dqueue overflow"; 	  
          return ; 	
        } 	
        if( top1+top2 == 0) 	  
        { 	    
            head = new node; 	    
            head->data=x;
	    head->next=NULL;
	    head->prev=NULL;
	    tail=head;
	    top1++;
	  }
	 else
	 {
	   cout <<" Add element 1.FIRST 2.LAST\n enter ur choice:"; 	   
           cin >> ch;
	   if(ch==1)
	   {
	     top1++;
	     temp=new node;
	     temp->data=x;
	     temp->next=head; 
	     temp->prev=NULL;
	     head->prev=temp;
	     head=temp;
	   }
	   else
	   {
	     top2++;
	     temp=new node;
	     temp->data=x;
	     temp->next=NULL;
	     temp->prev=tail;
	     tail->next=temp;
	     tail=temp;
	   }
	 }
  }
  void pop()
  {
   int ch;
   cout <<"Delete 1.First Node 2.Last Node\n Enter ur choice:";    
   cin >>ch;
   if(top1 + top2 <=0)
   {
     cout <<"\nDqueue under flow";      
     return;    
   }    
   if(ch==1)    
   {      
     head=head->next;
     head->prev=NULL;
     top1--;
   }
   else
   {
     top2--;
     tail=tail->prev;
     tail->next=NULL;
   }
  }
 
  void display()
  {
   int ch;
   node *temp;
   cout <<"display from 1.Staring 2.Ending\n Enter ur choice";    
   cin >>ch;
   if(top1+top2 <=0)
   {
     cout <<"under flow";
     return ;
   }
   if (ch==1)
   {
    temp=head;
    while(temp!=NULL)
    {
      cout << temp->data <<" ";       
      temp=temp->next;
    }
   }
   else
   {
    temp=tail;
    while( temp!=NULL) 
    {
      cout <data << " ";       
      temp=temp->prev;
    }
   }
    }
  };