/**************************************************************************  **************************************************************************   A C++ Program to illustrate the implementation of Double Ended linked list   as a Queue.  **************************************************************************  **************************************************************************/

 # include <iostream.h>
 # include <graphics.h>
 # include <stdlib.h>
 # include <conio.h>
 # include <dos.h>

 # define INSERT 0
 # define DELETE 1

 # define NORMAL 0
 # define WARNING 1


 /**************************************************************************///------------------  Double_Ended_Linked_list_as_Queue ------------------///**************************************************************************/class Double_Ended_Linked_list_as_Queue
    {
       private:
        char fill_pattern[8];

        int inserted_element_count;

        struct node
            {
               long data;
               node *next;
               node *previous;
            };

        node *rear;
        node *entry;
        node *print;
        node *front;

       public:
        Double_Ended_Linked_list_as_Queue( );

        long get_element( );

        void Delete( );
        void Insert( );
        void print_linked_list( );
        void show_working( );
        void show_main_screen( );
        void waiting_for_input( );
        void show_element_screen(int);
        void clear_element_screen(int);
        void show_insert_delete_screen(int);
        void show_output_screen( );
        void show_window(int,int,int,int);
    };


 /**************************************************************************///------------------  Double_Ended_Linked_list_as_Queue ( )  --------------///**************************************************************************/

 Double_Ended_Linked_list_as_Queue::Double_Ended_Linked_list_as_Queue  ( )
    {
       rear=NULL;
       front=NULL;
       inserted_element_count=0;

       fill_pattern[0]=0xAA;
       fill_pattern[1]=0x55;
       fill_pattern[2]=0xAA;
       fill_pattern[3]=0x55;
       fill_pattern[4]=0xAA;
       fill_pattern[5]=0x55;
       fill_pattern[6]=0xAA;
       fill_pattern[7]=0x55;
    }

 /**************************************************************************///--------------------  show_window(int,int,int,int)  --------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::
                show_window(int x_1,int y_1,int x_2,int y_2)
    {
       setcolor(15);
     rectangle(x_1,y_1,x_2,y_2);
     rectangle(x_1+1,y_1+1,x_2-1,y_2-1);

       setcolor(7);
     rectangle(x_1+2,y_1+2,x_2-2,y_2-2);
     rectangle(x_1+3,y_1+3,x_2-3,y_2-3);
     rectangle(x_1+4,y_1+4,x_2-4,y_2-4);

       setcolor(8);
     rectangle(x_1+5,y_1+5,x_2-5,y_2-5);
     rectangle(x_1+6,y_1+6,x_2-6,y_2-6);
     rectangle(x_1+7,y_1+7,x_2-7,y_2-7);
    }

 /**************************************************************************///----------------------  show_main_screen( )  ---------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::show_main_screen( )
    {
       cleardevice( );

       setcolor(15);
       setlinestyle(1,0,3);
     rectangle(5,5,getmaxx( )-5,getmaxy( )-5);

       setlinestyle(0,0,0);

       show_window(5,5,getmaxx( )-5,80);

       setfillpattern(fill_pattern,4);
     bar(13,13,getmaxx( )-13,72);

       settextstyle(2,0,7);
     setcolor(0);
       outtextxy(18,17,"Implementation of");
       outtextxy(18,16,"Implementation of");

     setcolor(12);
       outtextxy(19,15,"Implementation of");
       outtextxy(20,15,"Implementation of");

       settextstyle(2,0,9);
     setcolor(0);
       outtextxy(37,37,"Double Ended Linked List as Queue");
       outtextxy(38,37,"Double Ended Linked List as Queue");
       outtextxy(38,36,"Double Ended Linked List as Queue");

     setcolor(14);
       outtextxy(39,35,"Double Ended Linked List as Queue");
       outtextxy(40,35,"Double Ended Linked List as Queue");
       outtextxy(41,35,"Double Ended Linked List as Queue");

       show_window(5,82,305,getmaxy( )-5);

       setfillpattern(fill_pattern,9);
     bar(14,91,296,getmaxy( )-14);

       setcolor(6);
       setfillstyle(1,6);
     pieslice(215,105,0,360,10);

       setcolor(2);
       setfillstyle(1,2);
     pieslice(245,105,0,360,10);

       setcolor(4);
       setfillstyle(1,4);
     pieslice(275,105,0,360,10);

       setcolor(7);
     circle(215,105,11);
     circle(245,105,11);
     circle(275,105,11);

       show_window(307,82,getmaxx( )-5,getmaxy( )-5);

       settextstyle(7,0,4);
     setcolor(0);
       outtextxy(16,111,"Press:");

     setcolor(10);
       outtextxy(17,110,"Press:");
       outtextxy(18,110,"Press:");

     settextstyle(2,0,6);
     setcolor(0);
       outtextxy(59,151,"<I> to Insert an Element");
       outtextxy(59,171,"<D> to Delete an Element");
       outtextxy(59,191,"<E> to Exit");

     setcolor(14);
       outtextxy(60,150,"<I> to Insert an Element");
       outtextxy(61,150,"<I> to Insert an Element");

       outtextxy(60,170,"<D> to Delete an Element");
       outtextxy(61,170,"<D> to Delete an Element");

       outtextxy(60,190,"<E> to Exit");
       outtextxy(61,190,"<E> to Exit");

       setfillstyle(2,1);
     bar(317,92,getmaxx( )-15,getmaxy( )-15);
    }

 /**************************************************************************///---------------------  show_output_screen( )  --------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::show_output_screen( )
    {
       for(int count=0;count<=187;count++)
      {
         setfillstyle(1,0);
           bar(317,280,getmaxx( )-15,278-count);
           bar(317,280,getmaxx( )-15,278+count);

         delay(5);
      }

       setcolor(12);
       settextstyle(2,0,5);
     outtextxy(415,405,"Double Ended Linked List");
     outtextxy(416,405,"Double Ended Linked List");

     outtextxy(560,425,"as Queue");
     outtextxy(561,425,"as Queue");

       setfillstyle(1,6);
     bar(414,420,600,422);
     bar(560,440,622,442);

       setcolor(15);
       setlinestyle(0,0,3);
     rectangle(330,405,400,435);

       setfillstyle(1,9);
     bar(346,406,384,434);

       setfillstyle(1,1);
     bar(331,406,344,434);
     bar(386,406,399,434);

       setcolor(15);
       setlinestyle(0,0,3);
     rectangle(345,405,385,435);

       setcolor(7);
       setlinestyle(0,0,0);
     line(337,420,337,460);  /* Entry->Previous pointing arrow */
     line(337,460,415,460);

     line(412,457,415,460);
     line(412,463,415,460);

     line(360,428,360,450);  /* Entry->Data pointing arrow */
     line(360,450,415,450);

     line(412,447,415,450);
     line(412,453,415,450);

     line(393,420,393,440);   /* Entry->Next pointing arrow */
     line(393,440,415,440);

     line(412,437,415,440);
     line(412,443,415,440);

       setcolor(15);
       setfillstyle(1,15);
     pieslice(337,420,0,360,2);
     pieslice(393,420,0,360,2);

       settextstyle(0,0,1);
     setcolor(15);
       outtextxy(320,402,"*");

     setcolor(9);
     settextstyle(2,0,4);
       outtextxy(420,454,"Entry->Previous (x=NULL)");
       outtextxy(420,442,"Entry->Data");
       outtextxy(420,430,"Entry->Next (x=NULL)");

       setcolor(11);
       settextstyle(0,0,1);
     outtextxy(350,417,"0000");
    }

 /**************************************************************************///---------------------  show_insert_delete_screen(int)  -----------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::
                show_insert_delete_screen(int NORMAL_WARNING)
    {
       int x_1;
       int x_2;
       int y_1;
       int y_2;

       if(NORMAL_WARNING==NORMAL)
      {
         x_1=20;
         x_2=280;
         y_1=277;
         y_2=350;
      }

       if(NORMAL_WARNING==WARNING)
      {
         x_1=20;
         x_2=280;
         y_1=277;
         y_2=367;
      }

       setcolor(15);
       setlinestyle(1,0,3);
     rectangle(x_1,y_1,x_2,y_2);

       setlinestyle(0,0,0);

       setcolor(15);
     rectangle(x_1,y_1,x_2,y_2);

       setcolor(7);
     rectangle(x_1+1,y_1+1,x_2-1,y_2-1);

       setcolor(8);
     rectangle(x_1+2,y_1+2,x_2-2,y_2-2);

       setfillstyle(1,9);
     bar(x_1+3,y_1+3,x_2-3,y_2-3);
    }

 /**************************************************************************///----------------------  show_element_screen(int)  ----------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::
                       show_element_screen(int INSERT_DELETE)
    {
       show_insert_delete_screen(NORMAL);

       if(INSERT_DELETE==INSERT)
      {
         settextstyle(2,0,6);
           setcolor(0);
         outtextxy(28,281,"Enter the Element :");

           setcolor(11);
         outtextxy(29,280,"Enter the Element :");
         outtextxy(30,280,"Enter the Element :");
      }

       elseif(INSERT_DELETE==DELETE)
      {
         settextstyle(2,0,6);
           setcolor(0);
         outtextxy(28,281,"Poped Element is :");

           setcolor(11);
         outtextxy(29,280,"Poped Element is :");
         outtextxy(30,280,"Poped Element is :");
      }

       delay(300);

       for(int count=1;count<=65;count++)
      {
         setcolor(0);
         setfillstyle(1,0);
           bar(180-count,306,180+count,330);

           pieslice(180-count,318,0,360,12);
           pieslice(180+count,318,0,360,12);

         setcolor(15);
           line(180-count,302,180+count,302);
           line(180-count,334,180+count,334);

           arc(180-count,318,90,270,16);
           arc(180+count,318,270,90,16);

         setcolor(7);
           arc(180-count,318,90,270,15);
           arc(180-count,318,90,270,14);

           line(180-count,303,180+count,303);
           line(180-count,304,180+count,304);

           line(180-count,333,180+count,333);
           line(180-count,332,180+count,332);

           arc(180+count,318,270,90,15);
           arc(180+count,318,270,90,14);

         setcolor(8);
           line(180-count,305,180+count,305);
           line(180-count,331,180+count,331);

           arc(180-count,318,90,270,13);
           arc(180+count,318,270,90,13);

         delay(4);
      }
    }

 /**************************************************************************///-------------------  clear_element_screen(int)  ------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::
                     clear_element_screen(int NORMAL_WARNING)
    {
       if(NORMAL_WARNING==WARNING)
     {
         for(int count=1;count<=50;count++)
        {
           setfillpattern(fill_pattern,9);
             bar(18,275,290,275+count);
             bar(18,375,290,375-count);

           delay(20);
        }
      }

       elseif(NORMAL_WARNING==NORMAL)
      {
         for(int count=1;count<=40;count++)
        {
           setfillpattern(fill_pattern,9);
             bar(18,275,290,275+count);
             bar(18,355,290,355-count);

           delay(20);
        }
      }
    }

 /**************************************************************************///----------------------------  get_element( )  --------------------------///**************************************************************************/long Double_Ended_Linked_list_as_Queue::get_element( )
    {
       show_element_screen(INSERT);

       int count=0;
       charstring[6]={'\0'};

       do
      {
         int key_code=0;

         char key=NULL;

         if(kbhit( ))
        key=getch( );

         key_code=int(key);

         if(key_code>=48 && key_code<=57)
        {
           string[count]=key;
           count++;
        }

         elseif(key_code==8 && count>0)
        {
           setfillstyle(1,0);
             bar(130,306,230,330);

           count--;
           string[count]='\0';
        }

         elseif(key_code==13 && count>0)
        break;

         setcolor(12);
         settextstyle(2,0,7);

           moveto(140,305);
         outtext(string);

           moveto(141,305);
         outtext(string);

         int x=getx( );
         int y=305;

         while(!kbhit( ))
        {
           settextstyle(2,0,7);
             setcolor(12);
               moveto(x+2,y);
             outtext("_");

           delay(250);

             setcolor(0);
               moveto(x+2,y);
             outtext("_");

           delay(200);
           }
      }
       while(count<4);

       if(count==4)
      while(int(getch( ))!=13);

       long element=atol(string);

       clear_element_screen(NORMAL);

       return element;
    }

 /**************************************************************************///-------------------------------  Insert( )  ----------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::Insert( )
    {
       long num=get_element( );

       for(int count=1;count<5;count++)
      {
         setcolor(0);
         setfillstyle(1,0);
           pieslice(215,105,0,360,10);

         delay(250);

         setcolor(6);
         setfillstyle(1,6);
           pieslice(215,105,0,360,10);

         delay(250);
      }

       if(inserted_element_count<15)
      {
         setcolor(10);
         setfillstyle(1,10);
           pieslice(245,105,0,360,10);

         sound(1500);
         delay(800);
         nosound( );

         setcolor(2);
         setfillstyle(1,2);
           pieslice(245,105,0,360,10);
      }

       if(inserted_element_count==15)
      {
         setcolor(12);
         setfillstyle(1,12);
           pieslice(275,105,0,360,10);

         sound(2500);
         delay(1000);
         nosound( );

         setcolor(4);
         setfillstyle(1,4);
           pieslice(275,105,0,360,10);

         delay(200);
      }

       entry=new(node);
       entry->next=NULL;
       entry->previous=NULL;

       if(inserted_element_count==15)
      {
         show_insert_delete_screen(WARNING);

         settextstyle(7,0,4);
           setcolor(0);
         outtextxy(25,277,"Error:");
         outtextxy(26,277,"Error:");

           setcolor(14);
         outtextxy(27,275,"Error:");
         outtextxy(28,275,"Error:");

         while(!kbhit( ))
        {
           settextstyle(2,0,8);
             setcolor(0);
               outtextxy(46,309,"Not enough heap");
               outtextxy(47,309,"Not enough heap");

               outtextxy(28,335,"space on Screen.");
               outtextxy(29,335,"space on Screen.");

             setcolor(12);
               outtextxy(48,308,"Not enough heap");
               outtextxy(49,308,"Not enough heap");
               outtextxy(50,308,"Not enough heap");

               outtextxy(30,334,"space on Screen.");
               outtextxy(31,334,"space on Screen.");
               outtextxy(32,334,"space on Screen.");

           delay(500);

           setfillstyle(1,9);
             bar(23,315,277,362);

           delay(400);
        }

         getch( );
         clear_element_screen(1);
      }

       elseif(rear==NULL)
      {
         entry->data=num;
         rear=entry;
         front=rear;
         rear->next=NULL;
         rear->previous=NULL;

         inserted_element_count++;
      }

       else
      {
         entry->data=num;
         rear->next=entry;
         entry->previous=rear;
         rear=entry;
         rear->next=NULL;

         inserted_element_count++;
      }

       print_linked_list( );
    }

 /**************************************************************************///----------------------------  Delete( )  -------------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::Delete( )
    {
       for(int count=1;count<5;count++)
      {
         setcolor(0);
         setfillstyle(1,0);
           pieslice(215,105,0,360,10);

         delay(250);

         setcolor(6);
         setfillstyle(1,6);
           pieslice(215,105,0,360,10);

         delay(250);
      }

       if(inserted_element_count==0)
      {
         setcolor(12);
         setfillstyle(1,12);
           pieslice(275,105,0,360,10);

         sound(2500);
         delay(1000);
         nosound( );

         setcolor(4);
         setfillstyle(1,4);
           pieslice(275,105,0,360,10);

         delay(200);
      }

       elseif(inserted_element_count>0)
      {
         setcolor(10);
         setfillstyle(1,10);
           pieslice(245,105,0,360,10);

         sound(3000);
         delay(800);
         nosound( );

         setcolor(2);
         setfillstyle(1,2);
           pieslice(245,105,0,360,10);
      }

       if(front==NULL)
      {
         show_insert_delete_screen(WARNING);

         settextstyle(7,0,4);
           setcolor(0);
         outtextxy(25,277,"Error:");
         outtextxy(26,277,"Error:");

           setcolor(14);
         outtextxy(27,275,"Error:");
         outtextxy(28,275,"Error:");

         while(!kbhit( ))
        {
           settextstyle(6,0,4);
             setcolor(0);
               outtextxy(48,306,"Nothing to Pop");
               outtextxy(49,306,"Nothing to Pop");

             setcolor(12);
               outtextxy(50,305,"Nothing to Pop");
               outtextxy(51,305,"Nothing to Pop");
               outtextxy(52,305,"Nothing to Pop");

           delay(500);

           setfillstyle(1,9);
             bar(23,315,277,350);

           delay(400);
        }
         getch( );
      }

       else
      {
         node *deleted_element;

         long poped_data=front->data;

         deleted_element=front;
         front=front->next;
         front->previous=NULL;

         delete(deleted_element);

         inserted_element_count--;

         char element[6]={'\0'};

         ltoa(poped_data,element,10);

         show_element_screen(DELETE);

         setcolor(12);
         settextstyle(2,0,7);
           outtextxy(140,305,element);
           outtextxy(141,305,element);

         delay(2500);
      }

       clear_element_screen(DELETE);
       print_linked_list( );
    }

 /**************************************************************************///-------------------------  print_linked_list( )  -----------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::print_linked_list( )
    {
       int count=0;
       int x=335;
       int y=100;

       print=front;

       setfillstyle(1,0);
     bar(317,92,getmaxx( )-15,getmaxy( )-80);

       while(print!=NULL)
      {
         setcolor(15);
         setlinestyle(0,0,3);
           rectangle(x,y,x+70,y+30);


         setfillstyle(1,1);
           bar(x+1,y+1,x+14,y+29);

         setfillstyle(1,9);
           bar(x+16,y+1,x+54,y+29);

         setfillstyle(1,1);
           bar(x+56,y+1,x+69,y+29);

           rectangle(x+15,y,x+55,y+30);

         char element[6]={'\0'};

         ltoa(print->data,element,10);

         settextstyle(0,0,1);
           setcolor(11);
         outtextxy(x+20,y+10,element);


         if(count==0 || count==1 || count==2 || count==6 || count==7 ||
                 count==8 || count==12 || count==13 || count==14)
        {
           if(count==0)
              {
             setcolor(15);
               outtextxy(x+4,y+11,"x");
              }

           if(count==inserted_element_count-1)
              {
             setcolor(15);
               rectangle(x+15,y,x+55,y+30);
               outtextxy(x+60,y+11,"x");
              }
        }

         else
        {
           if(count==inserted_element_count-1)
              {
             setcolor(15);
             rectangle(x+15,y,x+55,y+30);
             outtextxy(x+4,y+11,"x");
              }
        }


         if(count==1 || count==2 || count==7 || count==8 || count==13
                                || count==14)
        {
           setcolor(7);
           setlinestyle(0,0,3);
             line(x-40,y+10,x-2,y+10);

             line(x-6,y+6,x-2,y+10);
             line(x-6,y+14,x-2,y+10);

             line(x-28,y+20,x+7,y+20);

             line(x-28,y+20,x-24,y+16);
             line(x-28,y+20,x-24,y+24);

           setcolor(15);
           setfillstyle(1,15);
             pieslice(x-37,y+10,0,360,2);
             pieslice(x+7,y+20,0,360,2);
        }

         elseif(count==4 || count==5 || count==10 || count==11)
        {
           setcolor(7);
           setlinestyle(0,0,3);
             line(x+64,y+10,x+98,y+10);

             line(x+94,y+6,x+98,y+10);
             line(x+94,y+14,x+98,y+10);

             line(x+72,y+20,x+107,y+20);

             line(x+72,y+20,x+76,y+16);
             line(x+72,y+20,x+76,y+24);

           setcolor(15);
           setfillstyle(1,15);
             pieslice(x+63,y+10,0,360,2);
             pieslice(x+107,y+20,0,360,2);
        }

         elseif(count==3 || count==9)
        {
           setcolor(7);
           setlinestyle(0,0,3);
             line(x+60,y-50,x+80,y-50);
             line(x+80,y-50,x+80,y+20);
             line(x+72,y+20,x+80,y+20);

             line(x+72,y+20,x+76,y+16);
             line(x+72,y+20,x+76,y+24);

             line(x+63,y-30,x+63,y+10);

             line(x+63,y-28,x+59,y-24);
             line(x+63,y-28,x+67,y-24);

           setcolor(15);
           setfillstyle(1,15);
             pieslice(x+63,y+10,0,360,2);
             pieslice(x+63,y-50,0,360,2);
        }

         elseif(count==6 || count==12)
        {
           setcolor(7);
           setlinestyle(0,0,3);
             line(x-15,y-50,x+10,y-50);
             line(x-15,y-50,x-15,y+20);
             line(x-15,y+20,x,y+20);

             line(x-2,y+20,x-6,y+16);
             line(x-2,y+20,x-6,y+24);

             line(x+7,y-30,x+7,y+10);

             line(x+3,y-24,x+7,y-28);
             line(x+11,y-24,x+7,y-28);

           setcolor(15);
             setfillstyle(1,15);
               pieslice(x+7,y+10,0,360,2);
               pieslice(x+7,y-50,0,360,2);
        }

         setcolor(7);
         setlinestyle(0,0,3);
           line(360,125,360,138);  /* Front Arrow */
           line(356,134,360,138);
           line(364,134,360,138);

         setcolor(14);
         settextstyle(2,0,4);
           outtextxy(338,140,"front");

         if(count==inserted_element_count-1)
        {
           setcolor(7);
           setlinestyle(0,0,3);
            line(x+40,y+25,x+40,y+38);
            line(x+36,y+34,x+40,y+38);
            line(x+44,y+34,x+40,y+38);

           setcolor(14);
           settextstyle(2,0,4);
             outtextxy(x+38,y+40,"rear");
        }

         print=print->next;
         count++;

         if(count==0 || count==1 || count==2 || count==6 || count==7 ||
                 count==8 || count==12 || count==13 || count==14)
        x+=100;

         elseif(count==3 || count==4 || count==5 || count==9 ||
             count==10 ||  count==11)
        x-=100;

         if(count==3 || count==9)
        {
           x=535;
           y+=60;
        }

         elseif(count==6 || count==12)
        {
           x=335;
           y+=60;
        }

          if(count==15)
         break;
      }

       setlinestyle(0,0,0);
    }

 /**************************************************************************///------------------------  waiting_for_input( )  ------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::waiting_for_input( )
    {
       do
      {
         setfillstyle(1,4);
           bar(51,440,99,445);

         setfillstyle(1,10);
           bar(101,440,149,445);

         setfillstyle(1,11);
           bar(151,440,199,445);

         setfillstyle(1,14);
           bar(201,440,249,445);

         delay(300);

         setfillpattern(fill_pattern,9);
           bar(51,440,99,445);

         delay(150);

           bar(101,440,149,445);

         delay(150);

           bar(151,440,199,445);

         delay(150);

           bar(201,440,249,445);

         delay(150);

         setfillstyle(1,4);
           bar(51,440,99,445);

         delay(150);

         setfillstyle(1,10);
           bar(101,440,149,445);

         delay(150);

         setfillstyle(1,11);
           bar(151,440,199,445);

         delay(150);

         setfillstyle(1,14);
           bar(201,440,249,445);
      }
       while(!kbhit( ));

       setfillpattern(fill_pattern,9);
     bar(51,440,249,445);
    }

 /**************************************************************************///---------------------------  show_working( )  --------------------------///**************************************************************************/void Double_Ended_Linked_list_as_Queue::show_working( )
    {
       show_main_screen( );
       delay(1000);
       show_output_screen( );

       char ch;

       int selected=0;

       do
      {
         waiting_for_input( );
         ch=getch( );

         switch(ch)
        {
           case'i': Insert( );
                 break;

           case'I': Insert( );
                 break;

           case'd': Delete( );
                 break;

           case'D': Delete( );
                 break;

           case'e': selected=1;
                 break;

           case'E': selected=1;
                 break;
        }
      }
       while(!selected && int(ch)!=27);

       delay(500);
    }


 main( )
    {
       int driver=VGA;
       int mode=VGAHI;

       initgraph(&driver,&mode,"..\\Bgi");

       Double_Ended_Linked_list_as_Queue  obj;

       obj.show_working( );

       closegraph( );

       return 0;
    }