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;
}

Introduction of Queue

In C or C++, queue is like a line of people whose standing for taking a ticket of movie in theater and standing in railway reservation counter. Queue is also called first-in-first-out ( FIFO) or last-in-last-out ( LILO) list. Its mean that any element added at last to the queue is remove last and first element remove first. In queue, insertion of a new element is at one end and deletion of a element at the other end. The end where the deletion of a element takes place is known as front. The end where the addition of a element takes place is known as rear. 

When we use Queue...


Advantages of Queue...





Disadvantage of Queue...




Operations on Queue...

struct qnode

{

   int value;

   struct qnode * link;

};

void add( struct qnode **,struct qnode **,  int);

int delete( struct qnode **, struct qnode ** );

int peek( struct qnode **, struct qnode ** );

void deleteallnode( struct qnode **, struct qnode ** );

int count( struct qnode * );

void display( struct qnode * );

void main()

{

   struct snode  * frontptr = NULL;

   struct snode  * rearptr = NULL;

   add( &frontptr, &rearptr, value);

   add( &frontptr, &rearptr, value);
   add( &frontptr, &rearptr, value);

   delete( &frontptr, &rearptr);

   peek( &frontptr, &rearptr );

   deleteallnode( &frontptr, &rearptr);

   count( frontptr);

   display( frontptr);

}

void add( struct qnode **front, struct qnode **rear, int value)
{
   struct qnode * temp= NULL;
   temp= ( struct qnode *) malloc( sizeof( struct qnode));
   temp-->data = value;
   temp-->link = NULL;
   if( *rear== NULL)
   {
      *front= *rear= temp;
      temp= NULL;
   }
   else
   {
      struct qnode *temp1= *rear;
      *rear= temp;
      temp1-->link= temp;
      temp= temp1= NULL;
   }
}

int delete(struct qnode ** front, struct qnode **rear)
{
   struct qnode *temp= *front;
   if( front== NULL)
   {
      cout<< "queue is empty";
   }
   if( temp-->link== NULL)
   {
      int value= temp-->data;
      *front= *rear= NULL;
      free( temp);
      temp= NULL;
   }
   else
   {
      struct qnode *temp1= *front;
      int value= temp-->data;
      temp1= temp1-->link;
      *front= temp1;
      temp-->link= NULL;
      free( temp);
      temp= temp1= NULL;
   }
   return value;
}

int peek( struct qnode **front, struct qnode **rear)
{
   struct qnode *temp= *front;
   if( temp== NULL)
   {
      cout<< "queue is empty";
      return -1;
   }
   else
   {
      int value= temp-->data;
      return value;
   }
}

void deleteallnode( struct qnode **front, struct qnode **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;
     }
  }
}

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

void display( struct qnode *frontptr)
{
   if( frontptr== NULL)

   {

      cout<< "queue is empty";

   }

   else

   {

      while( frontptr != NULL)

      {

         cout<< frontptr-->data;

         frontptr= frontptr-->link;

      }

   }

}