Queue: Implement dequeue using doubly linked list

Problem Statement:

Dequeue is a double ended queue.

It will allow for adding and removing elements from both front and rear end of the queue.

We can use double linked list to represent dequeue.

Solution Explanation:

For the solution, we need to take 2 pointers and keep track of the 2 pointers i.e front and rear.

Then we push the element in the front or rear end of the dequeue and pop the element from front and rear end of the queue.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <numeric>

using namespace std;

struct Node
{
    int data;
    Node* prev;
    Node* next;
};


class Deque
{
private:
    Node* front;
    
    Node* rear;
    
public:
    Deque() 
    { 
        front = nullptr; 
        rear = nullptr; 
    }

    void insertRear(int element);

    void deleteFront();

    void deleteRear();

    int getFront();

    int getRear();

    void display();
};


void Deque::insertRear(int element) 
{
    Node* new_node = new Node();

    if (new_node == NULL) 
    {
        cout << "Error" << endl;
        return;
    }

    new_node->data = element;

    if (front == NULL) 
    {
        new_node->prev = NULL;
        new_node->next = NULL;
        front = new_node;
        rear = new_node;
        return;
    }
    
    new_node->prev = rear;
    new_node->next = NULL;
    rear->next = new_node;
    
    rear = new_node;
}

void Deque::deleteFront() 
{
    if (front == NULL) {
        cout << "Deque is empty" << endl;
        return;
    }
    
    Node* tmp = front;
    
    if (front == rear) 
    {
        front = NULL;
        rear = NULL;
        
    } 
    else 
    {
        front = front->next;
        front->prev = NULL;
    }
    
    delete tmp;
}

void Deque::deleteRear() 
{
    if (front == NULL) 
    {
        cout << "Deque is empty" << endl;
        return;
    }
    
    Node* tmp = rear;
    
    if (front == rear) 
    {
        front = NULL;
        rear = NULL;
        
    } 
    else 
    {
        rear = rear->prev;
        rear->next = NULL;
    }
    
    delete tmp;
}

int Deque::getFront() 
{
    if (front == NULL) 
    {
        cout << "Deque is empty" << endl;
        return -1;
    }
    return front->data;
}

int Deque::getRear() 
{
    if (rear == NULL) 
    {
        cout << "Deque is empty" << endl;
        return -1;
    }

    return rear->data;
}

void Deque::display() 
{

    if (front == NULL) 
    {
        cout << "Deque is empty" << endl;
        return;
    }
    
    cout << "front ptr -->  ";
    for (Node* p = front ; p != NULL ; p = p->next) 
    {
        cout << "[" << p->data << "]" << ((p != rear)? " " : "");
    }
    cout << "  <-- rear ptr" << endl << endl;
}

int main()
{
    Deque queue;

    queue.insertRear(10);
    queue.insertRear(20);
    queue.insertRear(30);
    queue.display();
    
    int element = queue.getFront();
    queue.deleteFront();
    queue.display();

    element = queue.getRear();
    queue.deleteRear();
    queue.display();
}