Double ended queue is a more generalized form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front and back.
Here we will implement a double ended queue using a circular array. It will have the following methods:
// Maximum size of array or Dequeue
#define SIZE 5
class Dequeue
{
//front and rear to store the head and tail pointers
int *arr;
int front, rear;
public :
Dequeue()
{
//Create the array
arr = new int[SIZE];
//Initialize front and rear with -1
front = -1;
rear = -1;
}
// Operations on Deque
void push_front(int );
void push_back(int );
void pop_front();
void pop_back();
int get_front();
int get_back();
bool full();
bool empty();
};
First we check if the queue is full. If its not full we insert an element at front end by following the given conditions :
void Dequeue :: push_front(int key)
{
if(full())
{
cout << "OVERFLOW\n";
}
else
{
//If queue is empty
if(front == -1)
front = rear = 0;
//If front points to the first position element
else if(front == 0)
front = SIZE-1;
else
--front;
arr[front] = key;
}
}
Again we check if the queue is full. If its not full we insert an element at back by following the given conditions:
void Dequeue :: push_back(int key)
{
if(full())
{
cout << "OVERFLOW\n";
}
else
{
//If queue is empty
if(front == -1)
front = rear = 0;
//If rear points to the last element
else if(rear == SIZE-1)
rear = 0;
else
++rear;
arr[rear] = key;
}
}
In order to do this, we first check if the queue is empty. If its not then delete the front element by following the given conditions :
void Dequeue :: pop_front()
{
if(empty())
{
cout << "UNDERFLOW\n";
}
else
{
//If only one element is present
if(front == rear)
front = rear = -1;
//If front points to the last element
else if(front == SIZE-1)
front = 0;
else
++front;
}
}
Inorder to do this, we again first check if the queue is empty. If its not then we delete the last element by following the given conditions :
void Dequeue :: pop_back()
{
if(empty())
{
cout << "UNDERFLOW\n";
}
else
{
//If only one element is present
if(front == rear)
front = rear = -1;
//If rear points to the first position element
else if(rear == 0)
rear = SIZE-1;
else
--rear;
}
}
It can be simply checked by looking where front points to. If front is still intialized with -1, the queue is empty.
bool Dequeue :: empty()
{
if(front == -1)
return true;
else
return false;
}
Since we are using circular array, we check for following conditions as shown in code to check if queue is full.
bool Dequeue :: full()
{
if((front == 0 && rear == SIZE-1) ||
(front == rear + 1))
return true;
else
return false;
}
If the queue is not empty then we simply return the value stored in the position which front points.
int Dequeue :: get_front()
{
if(empty())
{ cout << "f=" <<front << endl;
cout << "UNDERFLOW\n";
return -1;
}
else
{
return arr[front];
}
}
If the queue is not empty then we simply return the value stored in the position which rear points.
int Dequeue :: get_back()
{
if(empty())
{
cout << "UNDERFLOW\n";
return -1;
}
else
{
return arr[rear];
}
}