Double Ended Queue using Singly Linked List

 A Double-Ended Queue (Deque) is a linear data structure that allows insertion and deletion of elements from both the front and rear ends.

---

🔍 What is a Double-Ended Queue (Deque)?

• Pronounced “deck”

• Supports four operations:

  • insertFront(): Insert an element at the front

  • insertRear(): Insert an element at the rear

  • deleteFront(): Delete an element from the front

  • deleteRear(): Delete an element from the rear

There are two types of Deques:

1. Input-restricted Deque – insertion at only one end but deletion at both ends

2. Output-restricted Deque – deletion at only one end but insertion at both ends

Implementing a Double-Ended Queue (Deque) using a singly linked list is a bit more limited compared to using a doubly linked list, because in singly linked lists you can only traverse in one direction (from front to rear).

✅ Basic Structure

Each node contains:

• data: the value

• next: pointer to the next node

The Deque has two pointers:

• front: points to the first node

• rear: points to the last node

---

💡 Algorithm 1: Insert at Front

• x: Element to insert

Steps:

1. Create a new node newNode with data = x and next = NULL.

2. If  front is NULL (deque is empty):

   • Set front = rear = newNode.

3. Else:

   • Set newNode->next = front.

   • Set front = newNode.

---

💡 Algorithm 2: Insert at Rear

Input:

• x: Element to insert

Steps:

1. Create a new node newNode with data = x and next = NULL.

2. If  rear is NULL (deque is empty):

   • Set  front = rear = newNode.

3. Else:

   • Set  rear->next = newNode.

   • Set  rear = newNode.

---

💡 Algorithm 3: Delete from Front

Steps:

1. If  front == NULL:

   • Print “Deque is empty” and return.

2. Store front in a temporary pointer temp.

3. Move front = front->next.

4. If  front == NULL, set rear = NULL.

5. Free temp.

or

1. If  front == NULL:

   • Print “Deque is empty” and return.

2. if front==rear // only one node

• set front=rear=NULL

        else
       3.Store front in a temporary pointer temp.

       4.Move front = front->next.

       5.Free temp.

---

💡 Algorithm 4: Delete from Rear

Steps:

1. If  rear == NULL:

   • Print “Deque is empty” and return.

2. If  front == rear (only one element):

   • Free front and set both  front = rear = NULL.

   • Return.

3. Else:

   • Start from front, traverse nodes using temp until temp->next == rear.

   • Free rear.

   • Set rear = temp and rear->next = NULL.

---

💡 Algorithm 5: Display Deque

Steps:

1. If  front == NULL, print “Deque is empty”.

2. Else:

   • Start from front and traverse each node.

   • Print data of each node.

C Implementation- dqueue

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

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

// Create a new node

struct Node* createNode(int data) {

    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}

// Insert at front

void insertFront(int data) {

    struct Node* newNode = createNode(data);

    if (front == NULL) {

        front = rear = newNode;

    } else {

        newNode->next = front;

        front = newNode;

    }

}

// Insert at rear

void insertRear( int data) {

    struct Node* newNode = createNode(data);

    if (rear == NULL) {

        front = rear = newNode;

    } else {

        rear->next = newNode;

        rear = newNode;

    }

}

// Delete from front

void deleteFront() {

    if (front == NULL) {

        printf("Deque is empty!\n");

        return;

    }

    struct Node* temp = front;

    printf("Deleted from front: %d\n", temp->data);

    front = front->next;

    if (front == NULL) {

        rear = NULL;

    }

    free(temp);

}

// Delete from rear (O(n))

void deleteRear() {

    if (rear == NULL) {

        printf("Deque is empty!\n");

        return;

    }

    struct Node* temp = front;

    if (front == rear) {

        printf("Deleted from rear: %d\n", temp->data);

        free(temp);

        front = rear = NULL;

        return;

    }

    while (temp->next != rear) {

        temp = temp->next;

    }

    printf("Deleted from rear: %d\n", rear->data);

    free(rear);

    rear = temp;

    rear->next = NULL;

}

// Display deque

void display() {

    struct Node* temp = front;

    printf("Deque: ");

    while (temp != NULL) {

        printf("%d-->", temp->data);

        temp = temp->next;

    }

    printf("NULL\n");

}

// Main

int main() {

      int choice, item;

    while (1) {

        printf("\n***** MENU *****\n");

        printf("1. Insert Front\n");

        printf("2. Insert Rear\n");

        printf("3. Delete Front\n");

        printf("4. Delete Rear\n");

        printf("5. Display\n");

        printf("6. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        

        switch (choice) {

            case 1:

                printf("Enter the element to insert at front: ");

                scanf("%d", &item);

                insertFront(item);

                break;

            case 2:

                printf("Enter the element to insert at rear: ");

                scanf("%d", &item);

                insertRear(item);

                break;

            case 3:

                deleteFront();

                break;

            case 4:

                deleteRear();

                break;

            case 5:

                display();

                break;

            case 6:

                printf("Exiting program.\n");

                exit(0);

            default:

                printf("Invalid choice! Please try again.\n");

        }

    }

    return 0;

}