Double Ended Queue (Deque) - Data Structure

By DeveloperIndian.com

In this tutorial, we will dive deep into Double Ended Queue (Deque), an important data structure in computer science. You'll learn its definition, types, and implementation using C, C++, Java, and Python. We'll also analyze the deque's advantages, practical applications, and trade-offs.

What is a Double Ended Queue (Deque)?

A Double Ended Queue (Deque) is a linear data structure that allows insertion and deletion of elements from both the front and rear ends. Unlike a regular queue (FIFO), deques provide flexibility for managing data from both directions.

Why Use a Deque?

• Flexibility: Both ends allow enqueue and dequeue operations.
• Efficient Memory Usage: Deques dynamically resize, saving memory.
• Dynamic Input Handling: Ideal for scenarios requiring frequent insertions/removals at both ends (e.g., text editors, undo/redo).

Operations on a Deque

The key operations performed on a deque include:

1. Insert at Front
   Adds an element to the front of the deque.

2. Insert at Rear
   Adds an element to the rear of the deque.

3. Delete from Front
   Removes the element at the front.

4. Delete from Rear
   Removes the element at the rear.

5. Display/Traverse
   Shows all elements of the deque.

Implementation of Deque Using Arrays in C

Here's a working C code snippet to implement a deque using an array:

#include<stdio.h>
#include<conio.h>
#define MAX 10
int queue[MAX];
int f = -1, r = -1;

void insertrear(int no) {
    if ((f == 0 && r == MAX - 1) || (r + 1 == f)) {
        printf("\nQueue is Full");
        return;
    }
    if (r == -1)
        f = r = 0;
    else if (r == MAX - 1)
        r = 0;
    else
        r++;
    queue[r] = no;
}

void insertfront(int no) {
    if ((f == 0 && r == MAX - 1) || (r + 1 == f)) {
        printf("\nQueue is Full");
        return;
    }
    if (r == -1)
        f = r = 0;
    else if (f == 0)
        f = MAX - 1;
    else
        f--;
    queue[f] = no;
}

int deletefront() {
    if (f == -1) {
        printf("\nQueue is Empty");
        return -999;
    }
    int val = queue[f];
    if (f == r)
        f = r = -1;
    else if (f == MAX - 1)
        f = 0;
    else
        f++;
    return val;
}

int deleterear() {
    if (r == -1) {
        printf("\nQueue is Empty");
        return -999;
    }
    int val = queue[r];
    if (f == r)
        f = r = -1;
    else if (r == 0)
        r = MAX - 1;
    else
        r--;
    return val;
}

void show() {
    if (f == -1) {
        printf("\nQueue is Empty");
        return;
    }
    int i = f;
    while (1) {
        printf("%d  ", queue[i]);
        if (i == r) break;
        if (i == MAX - 1)
            i = 0;
        else
            i++;
    }
}

void main() {
    int ch, n;
    do {
        clrscr();
        printf("\n1. Insert in Front");
        printf("\n2. Insert in Rear");
        printf("\n3. Delete from Front");
        printf("\n4. Delete from Rear");
        printf("\n5. Show");
        printf("\n0. Exit");
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &ch);
        switch (ch) {
        case 1:
            printf("\nEnter Number: ");
            scanf("%d", &n);
            insertfront(n);
            break;
        case 2:
            printf("\nEnter Number: ");
            scanf("%d", &n);
            insertrear(n);
            break;
        case 3:
            n = deletefront();
            if (n != -999)
                printf("\n%d deleted", n);
            break;
        case 4:
            n = deleterear();
            if (n != -999)
                printf("\n%d deleted", n);
            break;
        case 5:
            show();
            break;
        case 0:
            break;
        default:
            printf("\nWrong Choice...Try Again");
        }
    } while (ch != 0);
}

Advantages of Using Deques

1. Efficient Operations: O(1) time complexity for insertion and deletion at both ends.
2. Versatile Applications: Used in sliding window problems, scheduling algorithms, undo operations, etc.
3. Dynamic Resizing: Grows and shrinks based on runtime needs.

Deque in Other Programming Languages

1. Java: The Deque interface in the Java Collections Framework provides built-in methods for deque operations.
2. Python: The collections.deque module is widely used for its performance and simplicity.
3. C++: The deque container in the Standard Template Library (STL) offers dynamic resizing and efficient operations.

Limitations of Array-Based Deque

1. Fixed Size: The maximum size is predefined and may require resizing.
2. Memory Overhead: Wastes space if the array is sparsely populated.

For scenarios with dynamic growth, linked list-based implementation is recommended.

Applications of Deques

1. Sliding Window Algorithms: Common in time-series analysis and max/min window problems.
2. Undo/Redo Operations: Frequently used in text editors and IDEs.
3. Task Scheduling: Used in operating systems for managing tasks or processes.

Conclusion

The double-ended queue (deque) is a flexible and efficient data structure that supports both ends for insertion and deletion. Its array-based implementation is suitable for static data, whereas the linked list version is ideal for dynamic inputs. Whether you're implementing algorithms, handling scheduling tasks, or designing undo features, deques are a vital tool for developers.