C++ Deque

What is a deque? How to implement deques using C++?

  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.

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 listclass 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 nodeNode* tmp = new Node();tmp->data = element;tmp->next = NULL;tmp->prev = NULL;if ( isEmpty() ) {// Add the first elementfront = rear = tmp;}else {// Prepend to the list and fix linkstmp->next = front;front->prev = tmp;front = tmp;}count++;}int RemoveFront(){if ( isEmpty() ) {throw new DequeEmptyException();}//  Data in the front nodeint ret = front->data;// Delete the front node and fix the linksNode* 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 nodeNode* tmp = new Node();tmp->data = element;tmp->next = NULL;tmp->prev = NULL;if ( isEmpty() ) {// Add the first elementfront = rear = tmp;}else {// Append to the list and fix linksrear->next = tmp;tmp->prev = rear;rear = tmp;}count++;}int RemoveBack(){if ( isEmpty() ) {throw new DequeEmptyException();}//  Data in the rear nodeint ret = rear->data;// Delete the front node and fix the linksNode* 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 dequeueDeque q;try {if ( q.isEmpty() ){cout << "Deque is empty" << endl;}// Push elementsq.InsertBack(100);q.InsertBack(200);q.InsertBack(300);// Size of queuecout << "Size of dequeue = " << q.Size() << endl;// Pop elementscout << q.RemoveBack() << endl;cout << q.RemoveBack() << endl;cout << q.RemoveBack() << endl;}catch (...) {cout << "Some exception occured" << endl;}// Queue behavior using a general dequeueDeque q1;try {if ( q1.isEmpty() ){cout << "Deque is empty" << endl;}// Push elementsq1.InsertBack(100);q1.InsertBack(200);q1.InsertBack(300);// Size of queuecout << "Size of dequeue = " << q1.Size() << endl;// Pop elementscout << q1.RemoveFront() << endl;cout << q1.RemoveFront() << endl;cout << q1.RemoveFront() << endl;}catch (...) {cout << "Some exception occured" << endl;}}

OUTPUT:

Deque is emptySize of dequeue = 3300200100Deque is emptySize of dequeue = 3100200300

EXAMPLE:- Using the STL deque

#include <iostream>#include <deque>using namespace std;int main(){// Stack behavior using a STL dequedeque<int> q;try {if ( q.empty() ){cout << "Deque is empty" << endl;}// Push elementsq.push_back(100);q.push_back(200);q.push_back(300);// Size of queuecout << "Size of deque = " << q.size() << endl;// Pop elementscout << 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 dequedeque<int> q1;try {if ( q1.empty() ){cout << "Deque is empty" << endl;}// Push elementsq1.push_back(100);q1.push_back(200);q1.push_back(300);// Size of queuecout << "Size of deque = " << q1.size() << endl;// Pop elementscout << 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 emptySize of dequeue = 3300200100Deque is emptySize of dequeue = 3100200300