C++ Program to Implement Doubly Ended Queue

«
»
This C++ Program demonstrates operations on Doubly Ended Queue.

Here is source code of the C++ Program to demonstrate Doubly Ended Queue operations. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program To Implement Doubly Ended Queue
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.     int info;
  13.     node *next;
  14.     node *prev;
  15.  
  16. }*head, *tail;
  17.  
  18. /*
  19.  * Class Declaration
  20.  */
  21. class dqueue
  22. {
  23.     public:
  24.         int top1, top2;
  25.         void insert();
  26.         void del();
  27.         void display();
  28.         dqueue()
  29.         {
  30.             top1 = 0;
  31.             top2 = 0;
  32.             head = NULL;
  33.             tail = NULL;
  34.         }
  35. };
  36.  
  37. /*
  38.  * Main: Contains Menu
  39.  */
  40. int main()
  41. {
  42.     int choice;
  43.     dqueue dl;
  44.     while (1)
  45.     {
  46.         cout<<"\n-------------"<<endl;
  47.         cout<<"Operations on Deque"<<endl;
  48.         cout<<"\n-------------"<<endl;
  49.         cout<<"1.Insert Element into the Deque"<<endl;
  50.         cout<<"2.Delete Element from the Deque"<<endl;
  51.         cout<<"3.Traverse the Deque"<<endl;
  52.         cout<<"4.Quit"<<endl;
  53.         cout<<"Enter your Choice: ";
  54.         cin>>choice;
  55.         cout<<endl;
  56.         switch(choice)
  57.         {
  58.         case 1:
  59.             dl.insert();
  60.             break;
  61.         case 2:
  62.             dl.del();
  63.             break;
  64.         case 3:
  65.             dl.display();
  66.             break;
  67.         case 4:
  68.             exit(1);
  69.             break;
  70.         default:
  71.             cout<<"Wrong Choice"<<endl;
  72.         }
  73.     }
  74.     return 0;    
  75. }
  76.  
  77. /*
  78.  * Insert Element in Doubly Ended Queue
  79.  */
  80. void dqueue::insert()
  81. {
  82.     struct node *temp;
  83.     int ch, value;
  84.     if (top1 + top2 >= 50)
  85.     {
  86.         cout<<"Dequeue Overflow"<<endl;
  87.         return;
  88.     }
  89.     if (top1 + top2 == 0)
  90.     {
  91.         cout<<"Enter the value to be inserted: ";
  92.         cin>>value;
  93.         head = new (struct node);
  94.         head->info = value;
  95.         head->next = NULL;
  96.         head->prev = NULL;
  97.         tail = head;
  98.         top1++;
  99.         cout<<"Element Inserted into empty deque"<<endl; 
  100.     }
  101.     else
  102.     {
  103.         while (1)
  104.         {
  105.             cout<<endl;
  106.             cout<<"1.Insert Element at first"<<endl;
  107.             cout<<"2.Insert Element at last"<<endl;
  108.             cout<<"3.Exit"<<endl;
  109.             cout<<endl;
  110.             cout<<"Enter Your Choice: ";
  111.             cin>>ch;
  112.             cout<<endl;
  113.             switch(ch)
  114.             {
  115.             case 1:
  116.                 cout<<"Enter the value to be inserted: ";
  117.                 cin>>value;  
  118.                 temp = new (struct node);
  119.                 temp->info = value;
  120.                 temp->next = head;
  121.                 temp->prev = NULL;
  122.                 head->prev = temp;
  123.                 head = temp;
  124.                 top1++;
  125.                 break;
  126.             case 2:
  127.                 cout<<"Enter the value to be inserted: ";
  128.                 cin>>value; 
  129.                 temp = new (struct node);
  130.                 temp->info = value;
  131.                 temp->next = NULL;
  132.                 temp->prev = tail;
  133.                 tail->next = temp;
  134.                 tail = temp;
  135.                 top2++;
  136.                 break;
  137.             case 3:
  138.                 return;
  139.                 break;
  140.             default:
  141.                 cout<<"Wrong Choice"<<endl;
  142.             }
  143.         }
  144.     }
  145. }
  146.  
  147. /*
  148.  * Delete Element in Doubly Ended Queue
  149.  */
  150. void dqueue::del()
  151. {
  152.     if (top1 + top2 <= 0)
  153.     {
  154.         cout<<"Deque Underflow"<<endl;
  155.         return;
  156.     }
  157.     int ch;
  158.     while (1)
  159.     {
  160.         cout<<endl;
  161.         cout<<"1.Delete Element at first"<<endl;
  162.         cout<<"2.Delete Element at last"<<endl;
  163.         cout<<"3.Exit"<<endl;
  164.         cout<<endl;
  165.         cout<<"Enter Your Choice: ";
  166.         cin>>ch;
  167.         cout<<endl;
  168.         switch(ch)
  169.         {
  170.         case 1:  
  171.             head = head->next;
  172.             head->prev = NULL;
  173.             top1--;
  174.             break;
  175.         case 2:
  176.             tail = tail->prev;
  177.             tail->next = NULL;
  178.             top2--;
  179.             break;
  180.         case 3:
  181.             return;
  182.             break;
  183.         default:
  184.             cout<<"Wrong Choice"<<endl;
  185.         }
  186.     }
  187. }
  188.  
  189. /*
  190.  * Display Doubly Ended Queue
  191.  */
  192. void dqueue::display()
  193. {
  194.     struct node *temp;
  195.     int ch;
  196.     if (top1 + top2 <= 0)
  197.     {
  198.         cout<<"Deque Underflow"<<endl;
  199.         return;
  200.     }
  201.     while (1)
  202.     {
  203.         cout<<endl;
  204.         cout<<"1.Display Deque from Beginning"<<endl;
  205.         cout<<"2.Display Deque from End"<<endl;
  206.         cout<<"3.Exit"<<endl;
  207.         cout<<endl;
  208.         cout<<"Enter Your Choice: ";
  209.         cin>>ch;
  210.         cout<<endl;
  211.         switch (ch)
  212.         {
  213.         case 1:  
  214.             temp = head;
  215.             cout<<"Deque from Beginning:"<<endl;
  216.             while (temp != NULL)
  217.             {
  218.                 cout<<temp->info<<" ";
  219.                 temp = temp->next;                       
  220.             }
  221.             cout<<endl;
  222.             break;
  223.         case 2:
  224.             cout<<"Deque from End:"<<endl;
  225.             temp = tail;
  226.             while (temp != NULL)
  227.             {
  228.                 cout<<temp->info<<" ";
  229.                 temp = temp->prev;                      
  230.             }
  231.             temp = tail;
  232.             cout<<endl;
  233.             break;
  234.         case 3:
  235.             return;
  236.             break;
  237.         default:
  238.             cout<<"Wrong Choice"<<endl;
  239.         }
  240.     }
  241. }

advertisement
$ g++ deque.cpp
$ a.out
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
Deque Underflow
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 2
 
Deque Underflow
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 1
 
Enter the value to be inserted: 100
Element Inserted into empty deque
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 1
 
Deque from Beginning:
100 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 2
 
Deque from End:
100 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 1
 
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 1
 
Enter the value to be inserted: 200
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 2       
 
Enter the value to be inserted: 150
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 1
 
Deque from Beginning:
200 100 150 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 2
 
Deque from End:
150 100 200 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 2
 
 
1.Delete Element at first
2.Delete Element at last
3.Exit
 
Enter Your Choice: 1
 
 
1.Delete Element at first
2.Delete Element at last
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 1
 
Deque from Beginning:
100 150 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 2
 
Deque from End:
150 100 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 1
 
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 1
 
Enter the value to be inserted: 1010
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 2
 
Enter the value to be inserted: 1111
 
1.Insert Element at first
2.Insert Element at last
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 1
 
Deque from Beginning:
1010 100 150 1111 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 2
 
Deque from End:
1111 150 100 1010 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 2
 
 
1.Delete Element at first
2.Delete Element at last
3.Exit
 
Enter Your Choice: 2
 
 
1.Delete Element at first
2.Delete Element at last
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 3
 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 1
 
Deque from Beginning:
1010 100 150 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 2
 
Deque from End:
150 100 1010 
 
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
 
Enter Your Choice: 3
 
 
-------------
Operations on Deque
 
-------------
1.Insert Element into the Deque
2.Delete Element from the Deque
3.Traverse the Deque
4.Quit
Enter your Choice: 4
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn