#double-ended-queue-using-linked-List-C-Data-Structure

Double-Ended Queue Using Linked List - Data Structure Algorithm

In this tutorial, we explore the double-ended queue (Deque) implemented using a linked list. The double-ended queue is an essential data structure that provides dynamic insertion and deletion of elements at both ends. This article offers a detailed explanation of Deques, their operations, and a C implementation. You’ll also find code examples in other programming languages like C++, Java, and Python to deepen your understanding.

What is a Double-Ended Queue (Deque)?

A double-ended queue, commonly referred to as a Deque, is an advanced form of a queue where elements can be added or removed from both ends (front and rear). It combines the features of stacks and queues, making it versatile for solving complex algorithmic problems.

Why Use a Linked List for Deques?

Using a linked list to implement Deques has the following advantages:

• Dynamic Memory Allocation: Unlike arrays, linked lists grow or shrink dynamically as elements are added or removed.
• Efficient Operations: Insertions and deletions at the front or rear occur in O(1) time.
• No Predefined Size: The size of the Deque is determined at runtime, making it suitable for dynamic datasets.

Operations in Double-Ended Queue

Below are the key operations performed on a Deque:

1. Insertion at Front
2. Insertion at Rear
3. Deletion from Front
4. Deletion from Rear
5. Display of Elements

Implementation of Double-Ended Queue Using Linked List in C

Here’s a step-by-step implementation in C:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct queue {
    int no;
    struct queue *next;
};

struct queue *front = NULL, *rear = NULL;

// Insert at the rear
void insertrear(int val) {
    struct queue *q;
    q = (struct queue *)malloc(sizeof(struct queue));
    q->no = val;
    q->next = NULL;
    if (front == NULL) {
        front = rear = q;
        return;
    }
    rear->next = q;
    rear = q;
}

// Insert at the front
void insertfront(int val) {
    struct queue *q;
    q = (struct queue *)malloc(sizeof(struct queue));
    q->no = val;
    q->next = front;
    if (front == NULL) {
        front = rear = q;
        return;
    }
    front = q;
}

// Delete from the front
int deletefront() {
    int val;
    struct queue *q;
    if (front == NULL) {
        printf("\nQueue is Empty");
        return -999;
    }
    q = front;
    val = front->no;
    if (front == rear) {
        front = rear = NULL;
    } else {
        front = front->next;
    }
    free(q);
    return val;
}

// Delete from the rear
int deleterear() {
    int val;
    struct queue *q = front;
    if (front == NULL) {
        printf("\nQueue is Empty");
        return -999;
    }
    val = rear->no;
    if (front == rear) {
        front = rear = NULL;
    } else {
        while (q->next->next != NULL)
            q = q->next;
        rear = q;
        q = q->next;
        rear->next = NULL;
    }
    free(q);
    return val;
}

// Display the Deque
void show() {
    struct queue *q = front;
    if (front == NULL) {
        printf("\nQueue is Empty");
        return;
    }
    while (q != NULL) {
        printf("%d\t", q->no);
        q = q->next;
    }
}

void main() {
    int ch, n;
    do {
        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");
        }
    } while (ch != 0);
}

Advantages of Double-Ended Queue (Deque)

1. Versatile Usage: Deques can be used in a variety of real-world applications, such as sliding window problems, scheduling tasks, and managing buffers.
2. Optimized Memory Usage: Linked list implementation reduces memory wastage compared to arrays.
3. Efficient Data Management: Supports insertion and deletion at both ends without the need for shifting elements.

Conclusion

The double-ended queue (Deque) is a powerful data structure that offers dynamic flexibility for adding and removing elements at both ends. By using a linked list implementation, we gain dynamic memory allocation and efficient operations. However, linked lists may require slightly more memory than arrays and could be slower due to pointer manipulations.

For developers and learners exploring data structures and algorithms, mastering Deques with linked lists is an essential skill that has applications in real-world scenarios such as process scheduling, cache management, and sliding window algorithms.

Explore more tutorials on data structures by DeveloperIndian for high-quality, step-by-step guidance!