C++ Program to Implement Dequeue














































C++ Program to Implement Dequeue



  
 DEQUE: 
                  Unlike the conventional queue data structure ( where insertion is done on one end and deletion is done at the other end) , in a doubly ended queue, both insertion and deletion can be done at both the ends. It is also called head-tail linked list.  Just like a regular queue, it is handled by two pointers i.e., front and rear.

 

    The prominent applications of doubly ended queue are:


  • It can be used to implement both conventional stack and queue because of its property of insertion and deletion  from both ends.

  • In the real world it is used to implement A-steal job scheduling algorithm.


In the below code we have four prominent functions.


   1. F_Insert(x): It is used to insert element %u2018x%u2019 from the front side. We have 3 cases here:

                         

                         Case 1: If the array is empty, then we insert the element in the start i.e., at arr[0].

         

                         Case 2: If the front pointer is at first location i.e., arr[0] , then since we are implementing using a circular  


                                       array, we move front to the last location i.e, size-1.

 

                         Case 3: If the above two cases are not true, then we simply decrement the front pointer and insert the  


                                       element.


   2. R_Insert(x): It is used to insert element %u2018x%u2019 from the rear side. We have 3 cases here:


                         Case 1: If the array is empty, then we insert the element in the start i.e., at arr[0].


                         Case 2: If the rear pointer is at last location i.e., arr[size-1] , then since we are implementing using a 


                                      circular array, we move front to the first location i.e, 0.


                         Case 3: If the above two cases are not true, then we simply increment the rear pointer and insert the 


                                      element.


   3. F_Remove(): It is used to remove the element from the front side. We again have three cases:


                          Case 1: If there is only one element, then we move both front and rear to -1.


                          Case 2: If the front pointer is at the last location i.e., size-1, then we move front to first location i.e., 0.


                          Case 3: If the above two cases are not true, then we simply increment the front pointer.


   4. R_Remove() : It is used to remove the element from the rear side. We again have three cases:


                           Case 1: If there is only one element, then we move both front and rear to -1.


                           Case 2: If the rear pointer is at the first location i.e., 0, then we move front to last location i.e., size-1.


                           Case 3: If the above two cases are not true, then we simply decrement the rear pointer.




   Apart from the above 4 methods we also have two functions Front_Element() and Rear_Element() which are used to


   return the front value and the rear value respectively.




   CODE:



#include<iostream> using namespace std; #define SIZE 10 template<typename T> class deque { private: T que[SIZE]; int front; int rear; int len; bool Full() { if((front==0 && rear==SIZE-1) || (front==rear+1)) return(true); else return(false); } bool Empty() { if(front == -1) return(true); else return(false); } public: deque() { front = -1; rear = -1; } template<class F> void F_Insert(F x) { if(Full()) { cout<<"Queue Overflow\n"; } else { if(front==-1) { front = 0; rear = 0; que[front] = x; } else if(front == 0) { front = SIZE-1; que[front] = x; } else que[--front] = x; } } template<class F> void R_Insert(F x) { if(Full()) { cout<<"Queue Overflow\n"; } else { if(front==-1) { front = 0; rear = 0; que[front] = x; } else if(rear == SIZE-1) { rear = 0; que[rear] = x; } else { que[++rear] = x; } } } template<class F> void F_Remove() { if(Empty()) cout<<"Queue Underflow\n"; else { if(front == rear) { front =-1; rear = -1; } else { if(front == SIZE-1) front = 0; else front++; } } } template<class F> void R_Remove() { if(Empty()) cout<<"Queue Underflow\n"; else { if(front == rear) { front = -1; rear = -1; } else { if(rear == 0) rear = SIZE-1; else rear--; } } } template<class F> F Front_Element() { if(Empty()) { cout<<"Queue Underflow\n"; return -999; } return que[front]; } template<class F> F Rear_Element() { if(Empty()) { cout<<"Queue Underflow\n"; return -999; } return que[rear]; } }; int main() { deque<int> d; cout << "Inserting element from rear: 2\n"; d.R_Insert<int>(2); cout << "Inserting element from rear: 7\n"; d.R_Insert<int>(7); cout << "The rear element is "<<d.Rear_Element<int>()<<endl; cout << "Removing the rear element\n"; d.R_Remove<int>(); cout << "After removal,rear element is "<< d.Rear_Element<int>()<<endl; cout << "Inserting element from front: 4\n"; d.F_Insert<int>(4); cout << "Inserting element from front: 18\n"; d.F_Insert<int>(18); cout << "The front element is "<< d.Front_Element<int>()<<endl; cout <<"Removing the front element\n"; d.F_Remove<int>(); cout << "After removal,front element is "<< d.Front_Element<int>()<<endl; return 0; }  


OUTPUT:


  

Inserting element from rear: 2


Inserting element from rear: 7


The rear element is 7


Removing the rear element


After removal,rear element is 2


Inserting element from front: 4


Inserting element from front: 18


The front element is 18


Removing the front element


After removal,front element is 4







        


More Articles of Md Safi Ur Rahman Khan:

Name Views Likes
C++ boost::algorithm::string::find_token() 1352 0
C++ boost::algorithm::string::trim() 10927 0
C++ boost::algorithm::string::replace_first() 1922 0
C++ Program to Implement Dequeue 5075 5
C++ boost::algorithm::string::replace_nth() 722 0
C++ boost::algorithm::string::find_tail() 702 1
C++ boost::algorithm::string::find_first() 2472 1
C++ boost::algorithm::string::join() 2596 0
C++ boost::algorithm::string::erase_first() 817 1
C++ boost::algorithm::string::erase_last() 666 0
C++ boost::algorithm::string::trim_right() 1390 3
C++ boost::algorithm::string::replace_head() 583 0
C++ boost::algorithm::string::starts_with() 7618 0
C++ boost::algorithm::string::trim_right_if() 1610 1
C++ boost::algorithm::string::erase_head() 714 0
C++ boost::algorithm::string::trim_left_if() 1219 1
C++ boost::algorithm::string::replace_last() 914 0
C++ boost::algorithm::string::find_all() 2476 0
C++ Program to Implement Dequeue 626 3
C++ boost::algorithm::string::find_head() 578 0
C++ boost::algorithm::string::ends_with() 4655 0
C++ boost::algorithm::string::equals() 2618 0
C++ boost::algorithm::string::split() 3949 0
C++ boost::algorithm::string::contains() 6368 0
C++ boost::algorithm::string::trim_left() 1493 1
C++ boost::algorithm::string::erase_tail() 744 0
C++ boost::algorithm::string::all() 618 1
C++ boost::algorithm::string::replace_tail() 570 0
C++ boost::algorithm::string::trim_if() 2249 1
C++ boost::algorithm::string::erase_all() 3010 1
C++ boost::algorithm::string::lexicographical_compare() 767 0
C++ boost::algorithm::string::to_lower() 7060 1
C++ boost::algorithm::string::to_upper() 3076 1
C++ boost::algorithm::string::find_last() 1075 1
C++ boost::algorithm::replace_all() 8513 0
C++ boost::algorithm::string::erase_nth() 570 0

Comments