Double Ended Queue

Algorithm : Deque

Let us consider a double ended Queue,DQ with front and rear.
Insert in the front,delete from the front,insert in the rear,
delete from the rear all these operations are done in DQ.This
algorithm helps us to perform these operations.

Initially,

	  front=-1,rear=-1

Insertrear(DQ[1..N],front,rear,item)
{
  if(front=(rear+1)%N)               //checks if the dequeue is full
  {
    print "Queue frontull."
  }
  else
  {
    rear=(rear+1)%N;
    DQ[rear]=item                   //element is inserted in rear side
    if(front=-1)         //if front is -1 then front is initialized to 0
    {
      front=0
    }
  }
}

Deletefront(DQ[1..N],front,rear)
{
   if(front=-1)                              //checks if dequeue is empty
   {
      print "Queue empty."
   }
   else
   {
      item=DQ[front]
      if(front=rear)            //if front and rear is equal then they
      {                            both are initialized to -1
         front=-1
         rear=-1
      }
      else
      {
         front=(front+1)%N       //front is incremented and the element
      }                             in front deleted
   }
 return item
}




Insertfront(DQ[1..N],front,rear,item)
{
   if(front=0)                  
   {
      next=N-1
      front=next
      DQ[front]=item
   }
   else if(front=-1)               //checks if dequeue is empty
   {
      next=0
      front=next
      DQ[front]=item             //item is inserted in the 1st position
   }
   else
   {
      next=front-1
      if(next=rear)                //checks if next reachs rear
      {
         print " Deque full."
      }
      else
      {
         front=next
         DQ[front]=item
      }
   }
}

Deleterear(DQ[1..N],front,rear)
{
 if(front=-1)                      //checks if the deque is empty
 {
   print " DEQUE empty."
 }
 else
 {
   item=DQ[r]
   if(front=rear)             //checks if there is only 1 element 
   {                            present in the deque
     front=rear=-1      //then front and rear both are initialized to -1 
   }
   else if(rear=0)
     rear=N-1
   else
     rear=rear-1
 }
 return item
}


C Program For Double-ended-queue

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int DQ[5],f=-1,r=-1;

void insertrear(int item)
{
 if(f==(r+1)%5)
 {
  printf("\nQueue full.");
 }
 else
 {
  r=(r+1)%5;
  DQ[r]=item;
  if(f==-1)
  {
   f=0;
  }
 }
}

int deletefront()
{
 int item;
 if(f==-1)
 {
  printf("\nQueue empty.");
 }
 else
 {
   item=DQ[f];
  if(f==r)
  {
   f=-1;
   r=-1;
  }
  else
  {
  f=(f+1)%5;
  }
 }
 return item;
}

void insertfront(int item)
{
  int next;
  if(f==0)
  {
   next=4;
   f=next;
   DQ[f]=item;
  }
  else if(f==-1)
  {
    next=0;
    f=next;
    DQ[f]=item;
  }
  else
  {
    next=f-1;
    if(next==r)
    {
     printf("\nDeque full.");
    }
    else
    {
      f=next;
      DQ[f]=item;
    }
  }
}

int deleterear()
{
 int item;
 if(f==-1)
 {
   printf("\nDEQUE empty.");
 }
 else
 {
   item=DQ[r];
   if(f==r)
   {
     f=-1;
     r=-1;
   }
   else if(r==0)
   {
     r=4;
   }
   else
   {
     r=r-1;
   }
 }
 return item;
}

void show()
{
 int i=0;
 if(f==-1 || f==(r+1)%5)
 {
   printf("\nQueue empty.");
 }
 else
 {
 printf("\nThe elements of the Queue are:");
  if(f=f && i<=r)
     printf("\t%d",DQ[i]);
   else
     printf("\t_");
  }
 }
 else if(f==r)
 {
  for(i=0;i<=4;i++)
  {
   if(i==f)
     printf("\t%d",DQ[i]);
   else
     printf("\t_");
   }
  }
 else
 {
 for(i=0;i<=4;i++)
 {
  if(i<=r)
    printf("\t%d",DQ[i]);
  else if(i>r && i %d",item);
	    }
	    break;
     case 3:
	    printf("\nEnter item:");
	    scanf("%d",&item);
	    insertfront(item);
	    break;
     case 4:
	    item=deleterear();
	    if(f!=-1)
	    {
	    printf("\nThe popped item is-> %d",item);
	    }
	    break;
     case 5:
	    show();
	    break;

     case 6:
	    exit(0);

   }
 }
}


 OUTPUT :
 
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:1

Enter item:11

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:1

Enter item:22

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:3

Enter item:55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:3

Enter item:44

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      22      _       44      55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

The popped item is-> 44
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      22      _       _       55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:4

The popped item is-> 22
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:5

The elements of the Queue are:  11      _       _       _       55

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:4

The popped item is-> 11
  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

  1.insertrear
  2.deletefront
  3.insertfront
  4.deleterear
  5.Show
  6.Exit
Enter your choice:2

Queue empty.