Double ended Queue using doubly linked list

 

What is a Double Ended Queue (Deque)?

  • A Double Ended Queue (Deque) is a linear data structure where insertion and deletion operations can be performed from both the front and rear ends.

  • It is more flexible than a normal queue (which only allows operations at one end).

✅ Think of it like a queue where you can push and pop from both sides.

✍️ Basic Operations in Deque

OperationMeaning
insertFront(x)            Insert an element x at the front.
insertRear(x)            Insert an element x at the rear.
deleteFront()            Remove an element from the front.
deleteRear()            Remove an element from the rear.
display()            Display all elements from front to rear.

How to Implement Deque Using Doubly Linked List

Since a doubly linked list already has next and prev pointers, it is ideal for deque operations.

Each node contains:

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

We maintain two pointers:

  • front (points to the first node)

  • rear (points to the last node)

📚 Algorithms for Deque Operations

1. Insert at Front

  • Create a new node.

  • If deque is empty, front and rear point to the new node.

  • Else, set newNode->next = front, front->prev = newNode, and move front = newNode.

2. Insert at Rear

  • Create a new node.

  • If deque is empty, front and rear point to the new node.

  • Else, set rear->next = newNode, newNode->prev = rear, and move rear = newNode.

3. Delete from Front

  • If deque is empty, show underflow.

  • Else, move front = front->next. If front becomes NULL, set rear = NULL too.

4. Delete from Rear

  • If deque is empty, show underflow.

  • Else, move rear = rear->prev. If rear becomes NULL, set front = NULL too.

5. Display

  • Traverse from front to rear and print data.

C Program Deque Implemenation

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

// Node structure
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

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

// Insert at front
void insertFront(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = front;

    if (front == NULL)
        rear = newNode;
    else
        front->prev = newNode;

    front = newNode;
    printf("%d inserted at front\n", value);
}

// Insert at rear
void insertRear(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = rear;

    if (rear == NULL)
        front = newNode;
    else
        rear->next = newNode;

    rear = newNode;
    printf("%d inserted at rear\n", value);
}

// Delete from front
void deleteFront() {
    if (front == NULL) {
        printf("Deque is empty\n");
        return;
    }

    struct Node* temp = front;
    printf("Deleted %d from front\n", temp->data);
    front = front->next;

    if (front == NULL)
        rear = NULL;
    else
        front->prev = NULL;

    free(temp);
}

// Delete from rear
void deleteRear() {
    if (rear == NULL) {
        printf("Deque is empty\n");
        return;
    }

    struct Node* temp = rear;
    printf("Deleted %d from rear\n", temp->data);
    rear = rear->prev;

    if (rear == NULL)
        front = NULL;
    else
        rear->next = NULL;

    free(temp);
}

// Display the deque
void display() {
    if (front == NULL) {
        printf("Deque is empty\n");
        return;
    }

    struct Node* temp = front;
    printf("Deque elements: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Main function
int main() {
    int choice, value;

    while (1) {
        printf("\n--- Deque Menu ---\n");
        printf("1. Insert at Front\n");
        printf("2. Insert at Rear\n");
        printf("3. Delete from Front\n");
        printf("4. Delete from Rear\n");
        printf("5. Display\n");
        printf("6. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to insert at front: ");
                scanf("%d", &value);
                insertFront(value);
                break;
            case 2:
                printf("Enter value to insert at rear: ");
                scanf("%d", &value);
                insertRear(value);
                break;
            case 3:
                deleteFront();
                break;
            case 4:
                deleteRear();
                break;
            case 5:
                display();
                break;
            case 6:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more