/************************************************************************** ************************************************************************** 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 :\"); } else if(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); } } else if(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; char string[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++; } else if(key_code==8 && count>0) { setfillstyle(1,0); bar(130,306,230,330); count--; string[count]=\'\\0\'; } else if(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); } else if(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); } else if(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); } else if(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); } else if(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); } else if(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; else if(count==3 || count==4 || count==5 || count==9 || count==10 || count==11) x-=100; if(count==3 || count==9) { x=535; y+=60; } else if(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; }