Hits: 6

# Deque Data Structure

#### In this tutorial, you will learn what a double ended queue (deque) is. Also, you will find working examples of different operations on a deque in C.

Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow FIFO rule (First In First Out).

## Types of Deque

• Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both the ends.
• Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both the ends.

## Operations on a Deque

Below is the circular array implementation of deque. In a circular array, if the array is full, we start from the beginning.

But in a linear array implementation, if the array is full, no more elements can be inserted. In each of the operations below, if the array is full, “overflow message” is thrown.

Before performing the following operations, these steps are followed.

1. Take an array (deque) of size n.
2. Set two pointers at the first position and set `front = -1` and `rear = 0`.

### 1. Insert at the Front

This operation adds an element at the front.

1. Check the position of front.
2. If `front < 1`, reinitialize `front = n-1` (last index).
3. Else, decrease front by 1.
4. Add the new key 5 into `array[front]`.

### 2. Insert at the Rear

This operation adds an element to the rear.

1. Check if the array is full.
2. If the deque is full, reinitialize `rear = 0`.
3. Else, increase rear by 1.
4. Add the new key 5 into `array[rear]`.

### 3. Delete from the Front

The operation deletes an element from the front.

1. Check if the deque is empty.
2. If the deque is empty (i.e. `front = -1`), deletion cannot be performed (underflow condition).
3. If the deque has only one element (i.e. `front = rear`), set `front = -1` and `rear = -1`.
4. Else if front is at the end (i.e. `front = n - 1`), set go to the front `front = 0`.
5. Else, `front = front + 1`.

### 4. Delete from the Rear

This operation deletes an element from the rear.

1. Check if the deque is empty.
2. If the deque is empty (i.e. `front = -1`), deletion cannot be performed (underflow condition).
3. If the deque has only one element (i.e. `front = rear`), set `front = -1` and `rear = -1`, else follow the steps below.
4. If rear is at the front (i.e. `rear = 0`), set go to the front `rear = n - 1`.
5. Else, `rear = rear - 1`.

### 5. Check Empty

This operation checks if the deque is empty. If `front = -1`, the deque is empty.

### 6. Check Full

This operation checks if the deque is full. If `front = 0` and `rear = n - 1` OR `front = rear + 1`, the deque is full.

## Deque Implementation in C

``````// Deque implementation in C

#include <stdio.h>

#define MAX 10

void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);

int main(){
int arr[MAX];
int front, rear, i, n;

front = rear = -1;
for (i = 0; i < MAX; i++)
arr[i] = 0;

printf("nElements in a deque: ");
display(arr);

i = delFront(arr, &front, &rear);
printf("nremoved item: %d", i);

printf("nElements in a deque after deletion: ");
display(arr);

printf("nElements in a deque after addition: ");
display(arr);

i = delRear(arr, &front, &rear);
printf("nremoved item: %d", i);

printf("nElements in a deque after deletion: ");
display(arr);

n = count(arr);
printf("nTotal number of elements in deque: %d", n);
}

void addFront(int *arr, int item, int *pfront, int *prear){
int i, k, c;

if (*pfront == 0 && *prear == MAX - 1) {
printf("nDeque is full.n");
return;
}

if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}

if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}

void addRear(int *arr, int item, int *pfront, int *prear){
int i, k;

if (*pfront == 0 && *prear == MAX - 1) {
printf("nDeque is full.n");
return;
}

if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}

if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}

int delFront(int *arr, int *pfront, int *prear){
int item;

if (*pfront == -1) {
printf("nDeque is empty.n");
return 0;
}

item = arr[*pfront];
arr[*pfront] = 0;

if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;

return item;
}

int delRear(int *arr, int *pfront, int *prear){
int item;

if (*pfront == -1) {
printf("nDeque is empty.n");
return 0;
}

item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}

void display(int *arr){
int i;

printf("n front:  ");
for (i = 0; i < MAX; i++)
printf("  %d", arr[i]);
printf("  :rear");
}

int count(int *arr){
int c = 0, i;

for (i = 0; i < MAX; i++) {
if (arr[i] != 0)
c++;
}
return c;
}``````

## Time Complexity

The time complexity of all the above operations is constant i.e. `O(1)`.

## Applications of Deque Data Structure

1. In undo operations on software.
2. To store history in browsers.
3. For implementing both stacks and queues.

# Special 95% discount

## 2000+ Applied Machine Learning & Data Science Recipes

### Portfolio Projects for Aspiring Data Scientists: Tabular Text & Image Data Analytics as well as Time Series Forecasting in Python & R ## Two Machine Learning Fields

There are two sides to machine learning:

• Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
• Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

`Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  `