Double Ended Queue

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.

Implementation of Double ended Queue

Here we will implement a double ended queue using a circular array. It will have the following methods:

• push_back : inserts element at back
• push_front : inserts element at front
• pop_back : removes last element
• pop_front : removes first element
• get_back : returns last element
• get_front : returns first element
• empty : returns true if queue is empty
• full : returns true if queue is full

// 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();   
};

Insert Elements at Front

First we check if the queue is full. If its not full we insert an element at front end by following the given conditions :

• If the queue is empty then intialize front and rear to 0. Both will point to the first element.


• Else we decrement front and insert the element. Since we are using circular array, we have to keep in mind that if front is equal to 0 then instead of decreasing it by 1 we make it equal to SIZE-1.

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;
    }
}

Insert Elements at back

Again we check if the queue is full. If its not full we insert an element at back by following the given conditions:

• If the queue is empty then intialize front and rear to 0. Both will point to the first element.
• Else we increment rear and insert the element. Since we are using circular array, we have to keep in mind that if rear is equal to SIZE-1 then instead of increasing it by 1 we make it equal to 0.

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;
    }    
}

Delete First Element

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 :

• If only one element is present we once again make front and rear equal to -1.
• Else we increment front. But we have to keep in mind that if front is equal to SIZE-1 then instead of increasing it by 1 we make it equal to 0.

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;		
    }
}

Delete Last Element

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 :

• If only one element is present we make front and rear equal to -1.
• Else we decrement rear. But we have to keep in mind that if rear is equal to 0 then instead of decreasing it by 1 we make it equal to SIZE-1.

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;		
    }
}

Check if Queue is empty

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;
}

Check if Queue is full

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;
}

Return First Element

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];
    }
}

Return Last Element

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];
    }
}