C++ Program to Implement Dequeue
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:
using namespace std;
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
