Double-ended Queue or Deque

Introduction of  Deque...


In c or c++, the double-ended queue is define as a linear data structure in which addition and deletion of a node is  from the both side either front or rear.

When we use Deque...


Advantages of Deque...


Disadvantages of Deque...




Operations on Deque...

struct deque

{

   int data;

   struct deque * link;

};

void addatbeg( struct deque**, struct deque** , int);

void addatend( struct deque**, struct deque** , int);

int deleteafrombeg( struct deque**, struct deque** );

int deleteafromend( struct deque**, struct deque** );
void deleteall( struct deque**, struct deque**);

void display( struct deque* );

int count( struct deque* );

void main()

{

   struct deque* frontptr= NULL;

   struct deque* rearptr= NULL,

   addatbeg( &frontptr, &rearptr, value);

   addatbeg( &frontptr, &rearptr, value);

   addatend( &frontptr, &rearptr, value);

   addatend( &frontptr, &rearptr, value);

   deletefrombeg( &frontptr, &rearptr);

   deletefromend( &frontptr, &rearptr);

   display( frontptr);

   count( frontptr);
   deleteall( &frontptr, &rearptr);

}

voidaddatbeg( struct deque** front, struct deque**rear, int value)
{
   struct deque* temp= NULL;
   temp= ( struct deque*)malloc(sizeof( struct deque));
   temp-->data= value;
   temp-->link= *front;
   if( *front== NULL)
   {
      *front=*rear= temp;
      temp= NULL;
   }
   else
   {
      *front= temp;
      temp= NULL;
   }
}

voidaddatend( struct deque** front, struct deque** rear, int value)
{
   struct deque* temp= NULL;
   temp= ( struct deque*)malloc(sizeof( struct deque));

   temp-->data= value;

   temp-->link= NULL;

   if( *rear== NULL)

   {

      *front=*rear= temp;

      temp= NULL;

   } 

   else

   {

      struct deque* temp1= *rear;

      temp1-->link= temp;

      *rear= temp;

      temp= temp1= NULL;

   }

}


int deletefrombeg( struct deque** front, struct deque** rear)
{
   struct deque* temp= *front;
   if( temp-->link== NULL)
  {
     int a= temp-->data;
     *front= *rear= NULL;
     free( temp);
     temp= NULL;
  }
  else
  {
     int a= temp-->data;
     *front= temp-->link;
     temp-->link= NULL;
     free( temp)
     temp= NULL;
  }
  return a;
}

int deletefromend( struct deque** front, struct deque** rear)
{
   struct deque* temp= *front;
   if( temp-->link== NULL)

  {

     int a= temp-->data;

     *front= *rear= NULL;

     free( temp);

     temp= NULL;

  }

  else

  {

     struct deque* temp1= temp-->link;

     while( temp1!= NULL)

     {     

        temp= temp-->link;

        temp1= temp1-->link;

     }

      int a= temp1-->data;

      *rear= temp;

       temp-->link= NULL;

       free( temp1)

       temp1= temp= NULL;

  }

   return a;

}

void deleteall( struct deque** front, struct deque** rear)
{
   struct qnode **temp= *front;

   if( *front== NULL)

   {

      cout<< "queue is empty";

   }

   else

   {

      if( temp-->link== NULL)

     {

        *front= *rear= NULL;

        free( temp);

        temp= NULL;

     }

     else

     {

        struct qnode *temp1= temp-->link;

        while( temp!= NULL)

        {

           temp-->link= NULL;

           free( temp);

           *front= temp1;

           temp= *front;

           temp1= temp1-->link;

        }

        *front= *rear= NULL;

        free( temp);

        temp= NULL;

     }

  }

}

void display( struct deque* front);
{
   if( front== NULL)
   {
      cout<< "deque is empty";
   }
   else
   {
      while( front!= NULL)
      {
         cout<< front-->data;
         front= front-->link;
      }
   }
}

int count( struct deque* front)
{
   int c=0;
   if( front== NULL)
   {
      cout<< "deque is empty";
   }
   else
   {
      while( front!= NULL)
      {
         c++;
         front= front-->link;
      }
   }
   return c;
}