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::join() 691 0
C++ boost::algorithm::string::split() 833 0
C++ boost::algorithm::string::find_all() 747 0
C++ boost::algorithm::string::erase_tail() 270 0
C++ boost::algorithm::string::replace_tail() 229 0
C++ boost::algorithm::string::erase_head() 303 0
C++ boost::algorithm::string::replace_head() 232 0
C++ boost::algorithm::string::erase_all() 1049 1
C++ boost::algorithm::replace_all() 2455 0
C++ boost::algorithm::string::erase_nth() 232 0
C++ boost::algorithm::string::replace_nth() 238 0
C++ boost::algorithm::string::replace_last() 279 0
C++ boost::algorithm::string::erase_last() 271 0
C++ boost::algorithm::string::erase_first() 238 1
C++ boost::algorithm::string::replace_first() 492 0
C++ boost::algorithm::string::find_token() 413 0
C++ boost::algorithm::string::find_tail() 217 1
C++ boost::algorithm::string::find_head() 231 0
C++ boost::algorithm::string::find_last() 341 1
C++ boost::algorithm::string::find_first() 848 1
C++ boost::algorithm::string::all() 256 1
C++ boost::algorithm::string::lexicographical_compare() 234 0
C++ boost::algorithm::string::equals() 479 0
C++ boost::algorithm::string::contains() 2117 0
C++ boost::algorithm::string::ends_with() 1489 0
C++ boost::algorithm::string::starts_with() 2387 0
C++ boost::algorithm::string::trim_if() 797 1
C++ boost::algorithm::string::trim() 4510 0
C++ boost::algorithm::string::trim_right_if() 581 1
C++ boost::algorithm::string::trim_left_if() 447 1
C++ boost::algorithm::string::trim_right() 348 3
C++ boost::algorithm::string::trim_left() 419 1
C++ boost::algorithm::string::to_lower() 1076 1
C++ boost::algorithm::string::to_upper() 404 1
C++ Program to Implement Dequeue 1620 5
C++ Program to Implement Dequeue 262 3