C++ Deque

In this article, we will explore the concepts around Deque data structure. We will also write some simple implementation of Deque.

Deque Introduction

1. Deque is an abbreviation for double-ended queue.
2. It is a data structure in which the elements can only be added or removed from front and back of the queue.
3. A typical deque implementation support the following operations. Insert at front an element, insert at back an element, remove from back an element, remove from front an element, list the front element and list the back element.
4. Simple method of implementing a deque is using a doubly linked list.
5. The time complexity of all the deque operations using a doubly linked list can be achieced O(1).
6. A general purpose deque implementation can be used to mimic specialized behaviors like stacks and queues.
7. For example to use deque as a stack. Insert at back an element (Push) and Remove at back an element (Pop) can behave as a stack.
8. For example to use deque as a queue. Insert at back an element (Enqueue) and Remove at front an element (Dequeue) can behave as a queue.
9. Deque is also supported in C++ Standard Template Library.

Deque Implementation

EXAMPLE:- Implement a deque using doubly linked lists.

#include <iostream>
using namespace std;

class DequeEmptyException
{
public:
    DequeEmptyException()
    {
        cout << "Deque empty" << endl;
    }
};

// Each node in a doubly linked list
class Node
{
public:
    int data;
    Node* next;
    Node* prev;
};

class Deque
{  
private:
    Node* front;
    Node* rear;
    int count;

public:
    Deque()
    {
        front = NULL;
        rear = NULL;
        count = 0;
    }      
  
    void InsertFront(int element)
    {
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Prepend to the list and fix links
            tmp->next = front;
            front->prev = tmp;
            front = tmp;
        }

        count++;
    }

    int RemoveFront()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the front node
        int ret = front->data;

        // Delete the front node and fix the links
        Node* tmp = front;
        if ( front->next != NULL )
        {
            front = front->next;
            front->prev = NULL;
        }
        else
        {
            front = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }

    void InsertBack(int element)
    {          
        // Create a new node
        Node* tmp = new Node();
        tmp->data = element;
        tmp->next = NULL;
        tmp->prev = NULL;

        if ( isEmpty() ) {
            // Add the first element
            front = rear = tmp;
        }
        else {
            // Append to the list and fix links
            rear->next = tmp;
            tmp->prev = rear;
            rear = tmp;
        }

        count++;
    }

    int RemoveBack()
    {
        if ( isEmpty() ) {
            throw new DequeEmptyException();
        }

        //  Data in the rear node
        int ret = rear->data;

        // Delete the front node and fix the links
        Node* tmp = rear;
        if ( rear->prev != NULL )
        {
            rear = rear->prev;
            rear->next = NULL;
        }
        else
        {
            rear = NULL;
        }
        count--;
        delete tmp;

        return ret;
    }
  
    int Front()
    {          
        if ( isEmpty() )
            throw new DequeEmptyException();

        return front->data;
    }

    int Back()
    {
        if ( isEmpty() )
            throw new DequeEmptyException();

        return rear->data;
    }
  
    int Size()
    {
        return count;
    }

    bool isEmpty()
    {
        return count == 0 ? true : false;
    }
};

int main()
{      
    // Stack behavior using a general dequeue
    Deque q;
    try {
        if ( q.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.InsertBack(100);
        q.InsertBack(200);
        q.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q.Size() << endl;

        // Pop elements
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
        cout << q.RemoveBack() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a general dequeue
    Deque q1;
    try {
        if ( q1.isEmpty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.InsertBack(100);
        q1.InsertBack(200);
        q1.InsertBack(300);

        // Size of queue
        cout << "Size of dequeue = " << q1.Size() << endl;

        // Pop elements
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
        cout << q1.RemoveFront() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:

Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300

EXAMPLE:- Using the STL deque

#include <iostream>
#include <deque>
using namespace std;

int main()
{
    // Stack behavior using a STL deque
    deque<int> q;
    try {
        if ( q.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q.push_back(100);
        q.push_back(200);
        q.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q.size() << endl;

        // Pop elements
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
        cout << q.back() << endl;
        q.pop_back();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }

    // Queue behavior using a STL deque
    deque<int> q1;
    try {
        if ( q1.empty() )
        {
            cout << "Deque is empty" << endl;
        }

        // Push elements
        q1.push_back(100);
        q1.push_back(200);
        q1.push_back(300);

        // Size of queue
        cout << "Size of deque = " << q1.size() << endl;

        // Pop elements
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
        cout << q1.front() << endl;
        q1.pop_front();
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-

Deque is empty
Size of dequeue = 3
300
200
100
Deque is empty
Size of dequeue = 3
100
200
300