How to Implement Double Ended Queue in C

Back to: Data Structures and Algorithms Tutorials

How to Implement Double-Ended Queue in C Language:

In this article, I will discuss how to implement a double-ended queue in C language with examples. Please read our previous article discussing How to Implement a Queue using Linked List in C Language with Examples.

Double Ended Queue in C Language:

Now, we will discuss the Double Ended Queue, also known as DEQueue. We will refer to it as “D E Queue,” not “Dequeue.” It doesn’t strictly follow FIFO (First In, First Out); it all depends on how you choose to use it. If you want, you can use it as FIFO. It can be implemented using an array or a linked list.

If we implement a queue using an array or a linked list, we need two pointers: Rear and Front. The rear is used for insertion, and the Front is used for deletion. However, in a DEQueue, we can use both pointers for both insertion and deletion. This means that with the Rear pointer, we can insert and delete an element, and the same applies to the Front pointer. Let us show you the difference between a Queue and a DEQueue using a table.

Difference Between Queue and DEQueue:

This table helps us understand the difference between a Queue and a DEqueue. In a Queue, the Front pointer is used for deletion, and the Rear pointer is used for insertion. We cannot insert using the Front pointer or delete using the Rear pointer. However, in a DEQueue (Double-Ended Queue), both the Front and Rear pointers are used for both insertion and deletion. Let us demonstrate the concept of DEQueue with the help of an example.

Example of DEQueue:

Here, we have an empty array of size 7. Both Rear and Front are pointing to -1, which indicates that the queue is empty. To insert any element, we first need to decide from which side we want to insert it. Since the queue is empty and the Front is at -1, we can start by inserting from the Rear side.

Insertion with the help of Rear Pointer in DEQueue:

We have incremented the Rear pointer and inserted the value. Similarly, we will insert some more values.

Deletion with the help of Rear Pointer in DEQueue:

We have completed the insertion using the Rear pointer. Now, we want to delete the elements using the Rear pointer. To do this, we will remove the value and decrement the Rear pointer.

It is possible to delete using the Rear pointer, but this does not follow the FIFO principle. As we have already discussed, a DEQueue does not strictly follow the FIFO principle. We have demonstrated both insertion and deletion using the Rear pointer. Since there is no space on the left side or Front side, we cannot insert elements there. Can we delete it from the Front side? Yes, let us show you how.

Deletion with the help of Front Pointer in DEQueue:

For deletion, we increment the Front pointer and remove the value.

Let’s delete one more element,

We are familiar with the method of deletion using the Front pointer. Now, let’s insert some elements using the Front pointer.

Insertion with the help of Front Pointer in DEQueue:

When we insert an element using the Front pointer, we insert the element and decrement the Front pointer afterward.

Here, we’ve inserted ‘1’ and decremented the Front pointer. Let’s insert one more value.

Can we insert more elements from the front side? No, since the Front pointer is at -1. So, that’s all about the DEQueue. We can insert and delete using the Front and Rear pointers. Both operations are allowed from both sides (Front and Rear). A DEQueue does not strictly follow the FIFO principle; you can use it according to your needs. Java supports the DEQueue data structure as a built-in structure. There are some variations in DEQueue. Let us show you with the help of a table.

Types of DEQueue:

There are two types of restricted DEQueue: Input Restricted DEQueue and Output Restricted DEQueue.

Input Restricted DEQueue: In a DEQueue, insertion, and deletion are allowed with the help of both pointers (front and rear). However, in this case, the input operation is restricted. How can we perform the input operation? Only the rear pointer is allowed to insert elements in this type of DEQueue, while both pointers can do deletion.

Output Restricted DEQueue: In this type of DEQueue, the deletion operation is restricted. Here, only the front can delete elements from the queue. However, insertion can be performed by both pointers, i.e., rear and front.

Implementation of Double-Ended Queue in C Language:

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

struct Deque {
    int size;
    int front;
    int rear;
    int *Q;
};

void create(struct Deque *q, int size) {
    q->size = size;
    q->front = q->rear = -1;
    q->Q = (int *)malloc(q->size * sizeof(int));
}

int isFull(struct Deque *q) {
    return (q->rear == q->size - 1);
}

int isEmpty(struct Deque *q) {
    return (q->front == q->rear);
}

void enqueueRear(struct Deque *q, int x) {
    if (isFull(q))
        printf("Queue is Full\n");
    else {
        q->rear++;
        q->Q[q->rear] = x;
    }
}

void enqueueFront(struct Deque *q, int x) {
    if (q->front == -1)
        printf("Cannot enqueue at front\n");
    else {
        q->Q[q->front] = x;
        q->front--;
    }
}

int dequeueFront(struct Deque *q) {
    int x = -1;
    if (isEmpty(q))
        printf("Queue is Empty\n");
    else {
        q->front++;
        x = q->Q[q->front];
    }
    return x;
}

int dequeueRear(struct Deque *q) {
    int x = -1;
    if (isEmpty(q))
        printf("Queue is Empty\n");
    else {
        x = q->Q[q->rear];
        q->rear--;
    }
    return x;
}

void Display(struct Deque q) {
    int i;
    for (i = q.front + 1; i <= q.rear; i++)
        printf("%d ", q.Q[i]);
    printf("\n\n");
}

int main() {
    struct Deque q;
    int x = 0, s;

    printf("Enter the size of the deque: ");
    scanf("%d", &q.size);

    create(&q, q.size);

    printf("Enter the number of elements: ");
    scanf("%d", &s);

    printf("Enter the elements:\n");
    for (int i = 0; i < s; i++) {
        scanf("%d", &x);
        enqueueRear(&q, x);
    }
    printf("\n");

    enqueueRear(&q, 12);
    printf("Enqueue at Rear Operation has been performed: \n");
    Display(q);
    
    x = dequeueFront(&q);
    printf("Dequeue from Front Operation has been performed: %d\n", x);
    Display(q);

    enqueueFront(&q, 99);
    printf("Enqueue at Front Operation has been performed: \n");
    Display(q);

    x = dequeueRear(&q);
    printf("Dequeue from Rear Operation has been performed: %d\n", x);
    Display(q);

    return 0;
}

Output:

Implementation of Double-Ended Queue in C++ Language:

#include <iostream>
using namespace std;

class Deque {
private:
    int size;
    int front;
    int rear;
    int *Q;

public:
    Deque(int size) {
        this->size = size;
        front = rear = -1;
        Q = new int[this->size];
    }

    ~Deque() {
        delete[] Q;
    }

    bool isFull() {
        return (rear == size - 1);
    }

    bool isEmpty() {
        return (front == rear);
    }

    void enqueueRear(int x) {
        if (isFull())
            cout << "Queue is Full\n";
        else {
            rear++;
            Q[rear] = x;
        }
    }

    void enqueueFront(int x) {
        if (front == -1)
            cout << "Cannot enqueue at front\n";
        else {
            Q[front] = x;
            front--;
        }
    }

    int dequeueFront() {
        int x = -1;
        if (isEmpty())
            cout << "Queue is Empty\n";
        else {
            front++;
            x = Q[front];
        }
        return x;
    }

    int dequeueRear() {
        int x = -1;
        if (isEmpty())
            cout << "Queue is Empty\n";
        else {
            x = Q[rear];
            rear--;
        }
        return x;
    }

    void Display() {
        for (int i = front + 1; i <= rear; i++)
            cout << Q[i] << " ";
        cout << "\n\n";
    }
};

int main() {
    int size, s, x;

    cout << "Enter the size of the deque: ";
    cin >> size;

    Deque q(size);

    cout << "Enter the number of elements: ";
    cin >> s;

    cout << "Enter the elements:\n";
    for (int i = 0; i < s; i++) {
        cin >> x;
        q.enqueueRear(x);
    }
    cout << "\n";

    q.enqueueRear(12);
    cout << "Enqueue at Rear Operation has been performed: \n";
    q.Display();

    x = q.dequeueFront();
    cout << "Dequeue from Front Operation has been performed: " << x << "\n";
    q.Display();

    q.enqueueFront(99);
    cout << "Enqueue at Front Operation has been performed: \n";
    q.Display();

    x = q.dequeueRear();
    cout << "Dequeue from Rear Operation has been performed: " << x << "\n";
    q.Display();

    return 0;
}

Output:

In the next article, I will discuss Tree Data Structures in C Language with Examples. In this article, I explain how to Implement Double-Ended Queues in C Language with Examples. I hope you enjoy this Double-Ended Queue in C Language article.