Algorithm in C – Deque Data Structure

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).

representation of deque data structure
Representation of Deque

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.
initialize an array and pointers for deque operations
Initialize an array and pointers for deque

1. Insert at the Front

This operation adds an element at the front.

  1. Check the position of front.
    check the position of front
    Check the position of front
  2. If front < 1, reinitialize front = n-1 (last index).
    if front is less than 1 shift front to the end
    Shift front to the end
  3. Else, decrease front by 1.
  4. Add the new key 5 into array[front].
    Insert element at the position of front
    Insert the element at Front

2. Insert at the Rear

This operation adds an element to the rear.

  1. Check if the array is full.
    check if deque is full
    Check if deque is full
  2. If the deque is full, reinitialize rear = 0.
  3. Else, increase rear by 1.
    if deque is not full increase rear
    Increase the rear
  4. Add the new key 5 into array[rear].
    insert element at the rear
    Insert the element at rear

3. Delete from the Front

The operation deletes an element from the front.

  1. Check if the deque is empty.
    check if deque is empty
    Check if 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.
    increase the index of front
    Increase the front

4. Delete from the Rear

This operation deletes an element from the rear.

  1. Check if the deque is empty.
    check if deque is empty
    Check if 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.
    decrease the position of rear
    Decrease the rear

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;

  addRear(arr, 5, &front, &rear);
  addFront(arr, 12, &front, &rear);
  addRear(arr, 11, &front, &rear);
  addFront(arr, 5, &front, &rear);
  addRear(arr, 6, &front, &rear);
  addFront(arr, 8, &front, &rear);

  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);

  addRear(arr, 16, &front, &rear);
  addRear(arr, 7, &front, &rear);

  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.

 

Python Example for Beginners

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.  

Google –> SETScholars