Deque is a hybrid data structure that combines the features of a stack and a queue. It allows us to insert and delete elements from both ends of the queue. The name Deque is an abbreviation of Double-Ended Queue.
Imagine an event where you have two gates to enter and exit a place. People are entering from the front gate and some are entering from the side gate. Now, when people are leaving, they are leaving from the front gate and some sneak from the side gate. Now, we need to manage flow of people from both ends. This is where Deque comes into play.
Operations on Deque
Following are the major operations on Deque −
- push_front(x): Insert element x at the front of the deque.
- push_back(x): Insert element x at the back of the deque.
- pop_front(): Remove the element from the front of the deque.
- pop_back(): Remove the element from the back of the deque.
- peek_front(): Get the element from the front of the deque.
- peek_back(): Get the element from the back of the deque.
- size(): Get the number of elements in the deque.
- isEmpty(): Check if the deque is empty.
Implementation of Deque
Let’s understand how we can implement deque using array. For this, we need to maintain two pointers, front and rear, to keep track of the front and back of the deque. We also need to define the size of the deque.
The push_front(x) Operation on Deque
When we insert an element at the front of the deque, we need to shift all the elements to the right by one position. We will increment the front pointer by one and insert the element at the front of the deque.
Algorithm for push_front(x)
Following are the steps to insert an element at the front of the deque −
1. Check if the deque is full. If it is full, return an error message. 2. Increment the front pointer by one. 3. Insert the element at the front position. 4. Increment the size of the deque.
implementation
Following is the implementation of push_front(x) operation on deque.
#include <stdio.h>#include <stdlib.h>#define SIZE 5int deque[SIZE];int front =-1, rear =-1;// Check if the deque is fullintisFull(){return(front ==0&& rear == SIZE -1)||(front == rear +1);}// Check if the deque is emptyintisEmpty(){return front ==-1;}// Insert element at the frontvoidpush_front(int element){if(isFull()){printf("Deque is full\n");return;}if(isEmpty()){// First element being inserted
front = rear =0;}else{// Circularly move front pointer
front =(front -1+ SIZE)% SIZE;}
deque[front]= element;printf("Inserted -> %d\n", element);}// Display the dequevoiddisplay(){if(isEmpty()){printf("Empty Deque\n");return;}int i = front;printf("Elements -> ");while(1){printf("%d ", deque[i]);if(i == rear)break;// Stop at the last element
i =(i +1)% SIZE;// Circular increment}printf("\n");}intmain(){push_front(1);push_front(2);push_front(3);push_front(4);push_front(5);display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Elements -> 5 4 3 2 1
push_back(x) Operation
This operation is used for inserting an element to the back of the deque. When we insert an element at the back of the deque, we need to increment the rear pointer by one and insert the element at the back of the deque.
Algorithm for push_back(x)
Following are the steps to insert an element at the back of the deque −
1. Check if the deque is full. 2. Increment the rear pointer by one. 3. Insert the element at the rear position. 4. Increment the size of the deque.
Implementation
Following is the implementation of push_back(x) operation on deque.
//C Program#include <stdio.h>#include <stdlib.h>#define SIZE 5int deque[SIZE];int front =-1, rear =-1;// Check if the deque is fullintisFull(){return((front ==0&& rear == SIZE -1)||(front == rear +1));}// Check if the deque is emptyintisEmpty(){return(front ==-1);}// Insert element at the backvoidpush_back(int element){if(isFull()){printf("Deque is full\n");}else{if(front ==-1){// If deque is initially empty
front = rear =0;}elseif(rear == SIZE -1){// Wrap around to the front
rear =0;}else{
rear++;}
deque[rear]= element;printf("Inserted -> %d\n", element);}}// Display the dequevoiddisplay(){if(isEmpty()){printf("Empty Deque\n");}else{printf("Elements -> ");int i = front;while(1){printf("%d ", deque[i]);if(i == rear)break;// Stop when the rear is reached
i =(i +1)% SIZE;// Circular increment}printf("\n");}}// Main functionintmain(){push_back(1);push_back(2);push_back(3);push_back(4);push_back(5);display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Elements -> 1 2 3 4 5
The pop_front() and pop_back() Operations on Deque
These operation is done when we need to remove elements from front or back. When we remove an element from the front of the deque, we need to increment the front pointer by one.
Similarly, when we remove an element from the back of the deque, we need to decrement the rear pointer by one.
Algorithm for pop_front() and pop_back()
Following are the steps to remove an element from the front or back of the deque −
1. Check if the deque is empty. 2. Remove the element from the front or back of the deque. 3. Increment or decrement the front or rear pointer. 4. Decrement the size of the deque.
Implementation
Following is the implementation of pop_front() and pop_back() operations on deque.
//C Program#include <stdio.h>#include <stdlib.h>#define SIZE 5int deque[SIZE];int front =-1, rear =-1;// Check if the deque is fullintisFull(){return((front ==0&& rear == SIZE -1)||(front == rear +1));}// Check if the deque is emptyintisEmpty(){return(front ==-1);}// Insert element at the backvoidpush_back(int element){if(isFull()){printf("Deque is full\n");}else{if(front ==-1){// If deque is initially empty
front = rear =0;}elseif(rear == SIZE -1){// Wrap around to the front
rear =0;}else{
rear++;}
deque[rear]= element;printf("Inserted -> %d\n", element);}}// Remove element from the frontvoidpop_front(){if(isEmpty()){printf("Deque is empty\n");}else{printf("Deleted from front -> %d\n", deque[front]);if(front == rear){// If only one element is present
front = rear =-1;}else{
front =(front +1)% SIZE;}}}// Remove element from the backvoidpop_back(){if(isEmpty()){printf("Deque is empty\n");}else{printf("Deleted from back -> %d\n", deque[rear]);if(front == rear){// If only one element is present
front = rear =-1;}elseif(rear ==0){
rear = SIZE -1;}else{
rear--;}}}// Display the dequevoiddisplay(){if(isEmpty()){printf("Empty Deque\n");}else{printf("Elements -> ");int i = front;while(1){printf("%d ", deque[i]);if(i == rear)break;// Stop when the rear is reached
i =(i +1)% SIZE;// Circular increment}printf("\n");}}// Main functionintmain(){push_back(1);push_back(2);push_back(3);push_back(4);push_back(5);pop_front();pop_back();display();return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Deleted -> 1 Deleted -> 5
The peek_front() and peek_back() Operations on Deque
When we want to get the element from the front or back of the deque, we can use the peek_front() and peek_back() operations.
Algorithm for peek_front() and peek_back()
Following are the steps to get the element from the front or back of the deque −
1. Check if the deque is empty. 2. If not empty, return the element from the front or back of the deque.
Implementation
Following is the implementation code of peek_front() and peek_back() operations on deque.
//C Program#include <stdio.h>#include <stdlib.h>#define SIZE 5int deque[SIZE];int front =-1, rear =-1;// Check if the deque is fullintisFull(){return((front ==0&& rear == SIZE -1)||(front == rear +1));}// Check if the deque is emptyintisEmpty(){return(front ==-1);}// Insert element at the backvoidpush_back(int element){if(isFull()){printf("Deque is full\n");}else{if(front ==-1){// If deque is initially empty
front = rear =0;}elseif(rear == SIZE -1){// Wrap around to the front
rear =0;}else{
rear++;}
deque[rear]= element;printf("Inserted -> %d\n", element);}}// Get the element from the frontintpeek_front(){if(isEmpty()){printf("Deque is empty\n");return-1;}else{return deque[front];}}// Get the element from the backintpeek_back(){if(isEmpty()){printf("Deque is empty\n");return-1;}else{return deque[rear];}}// Main functionintmain(){push_back(1);push_back(2);push_back(3);push_back(4);push_back(5);printf("\nElement at front: %d\n",peek_front());printf("Element at back: %d\n",peek_back());return0;}
Output
The output obtained is as follows −
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Element at front: 1 Element at back: 5
Time Complexity of Deque Operations
The time complexity of the deque operations is as follows −
- push_front(x) − O(1)
- push_back(x) − O(1)
- pop_front() − O(1)
- pop_back() − O(1)
- peek_front() − O(1)
- peek_back() − O(1)
Thus, the deque operations have a time complexity of O(1).
Applications of Deque
Some of the applications of deque are as follows −
- Deque is used for undo operation in text editors.
- It is also used in implementation of the sliding window algorithm.
- Deque is used in implementing the data structures like double-ended priority queue and double-ended stack.
In summary, we use deque when we need to perform insertion and deletion operations at both ends of the data structure.
