Dequeue Operation in DSA C

Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway with doors at both ends. People can enter or exit from either door, not just one side.

front -> [1] -> [2] -> [3] ← rear
↑front pointer          ↑rear pointer

Dry Run Walkthrough

Input: dequeue with elements 1 -> 2 -> 3, perform dequeue from front and then from rear

Goal: Remove one element from the front and one from the rear, showing how the structure updates

Step 1: Remove element from front

front removed 1 -> 2 -> 3 ← rear
front now points to 2

Why: We remove the first element to simulate dequeue from front

Step 2: Remove element from rear

2 -> 3 removed from rear
front -> 2 ← rear now points to 2

Why: We remove the last element to simulate dequeue from rear

Result:

2 ← front and rear point to the same single element
final dequeue state: 2 -> null

Annotated Code

DSA C

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

#define MAX 5

typedef struct Dequeue {
    int arr[MAX];
    int front;
    int rear;
} Dequeue;

void init(Dequeue* dq) {
    dq->front = -1;
    dq->rear = -1;
}

int isEmpty(Dequeue* dq) {
    return (dq->front == -1);
}

int isFull(Dequeue* dq) {
    return ((dq->front == 0 && dq->rear == MAX - 1) || (dq->front == dq->rear + 1));
}

void enqueueRear(Dequeue* dq, int value) {
    if (isFull(dq)) {
        printf("Dequeue is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else if (dq->rear == MAX - 1) {
        dq->rear = 0;
    } else {
        dq->rear++;
    }
    dq->arr[dq->rear] = value;
}

void enqueueFront(Dequeue* dq, int value) {
    if (isFull(dq)) {
        printf("Dequeue is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = MAX - 1;
    } else {
        dq->front--;
    }
    dq->arr[dq->front] = value;
}

int dequeueFront(Dequeue* dq) {
    if (isEmpty(dq)) {
        printf("Dequeue is empty\n");
        return -1;
    }
    int data = dq->arr[dq->front];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->front == MAX - 1) {
        dq->front = 0;
    } else {
        dq->front++;
    }
    return data;
}

int dequeueRear(Dequeue* dq) {
    if (isEmpty(dq)) {
        printf("Dequeue is empty\n");
        return -1;
    }
    int data = dq->arr[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    } else {
        dq->rear--;
    }
    return data;
}

void printDequeue(Dequeue* dq) {
    if (isEmpty(dq)) {
        printf("Dequeue is empty\n");
        return;
    }
    int i = dq->front;
    printf("Dequeue elements: ");
    while (1) {
        printf("%d ", dq->arr[i]);
        if (i == dq->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Dequeue dq;
    init(&dq);
    enqueueRear(&dq, 1);
    enqueueRear(&dq, 2);
    enqueueRear(&dq, 3);
    printDequeue(&dq);

    int frontVal = dequeueFront(&dq);
    printf("Dequeued from front: %d\n", frontVal);
    printDequeue(&dq);

    int rearVal = dequeueRear(&dq);
    printf("Dequeued from rear: %d\n", rearVal);
    printDequeue(&dq);

    return 0;
}

if (isEmpty(dq)) { dq->front = dq->rear = 0; } else if (dq->rear == MAX - 1) { dq->rear = 0; } else { dq->rear++; } dq->arr[dq->rear] = value;

advance rear pointer circularly and insert value at rear

if (isEmpty(dq)) { dq->front = dq->rear = 0; } else if (dq->front == 0) { dq->front = MAX - 1; } else { dq->front--; } dq->arr[dq->front] = value;

move front pointer backward circularly and insert value at front

int data = dq->arr[dq->front]; if (dq->front == dq->rear) { dq->front = dq->rear = -1; } else if (dq->front == MAX - 1) { dq->front = 0; } else { dq->front++; } return data;

remove element at front and update front pointer circularly

int data = dq->arr[dq->rear]; if (dq->front == dq->rear) { dq->front = dq->rear = -1; } else if (dq->rear == 0) { dq->rear = MAX - 1; } else { dq->rear--; } return data;

remove element at rear and update rear pointer circularly

Output

Dequeue elements: 1 2 3 

Dequeued from front: 1

Dequeue elements: 2 3 

Dequeued from rear: 3

Dequeue elements: 2 

Complexity Analysis

Time: O(1) because dequeue operations just move pointers without traversing

Space: O(MAX) fixed size array used for storage

vs Alternative: Compared to linked list dequeue, array-based dequeue uses fixed space but faster index access; linked list uses dynamic space but more pointer overhead

Edge Cases

empty dequeue

dequeue operations print 'Dequeue is empty' and return -1

DSA C

if (isEmpty(dq)) { printf("Dequeue is empty\n"); return -1; }

single element dequeue

removing that element resets front and rear to -1 indicating empty

DSA C

if (dq->front == dq->rear) { dq->front = dq->rear = -1; }

front or rear pointer wrap around

pointers wrap circularly to start or end of array

DSA C

else if (dq->front == MAX - 1) { dq->front = 0; } and else if (dq->rear == 0) { dq->rear = MAX - 1; }

When to Use This Pattern

When you need to add or remove items from both ends efficiently, look for dequeue operations because they allow double-ended access with constant time updates.

Common Mistakes

Mistake: Not handling the circular wrap-around of front and rear pointers
Fix: Use modulo or conditional checks to wrap pointers to start/end of array

Mistake: Not resetting front and rear to -1 when dequeue becomes empty
Fix: Check if front equals rear after removal and reset both to -1

Summary

It removes elements from either the front or rear end of a dequeue.

Use it when you want to efficiently remove items from both ends of a collection.

Remember to update pointers circularly and reset when dequeue becomes empty.

Practice

1. What is a dequeue in data structures?

easy

A. A double-ended queue allowing insertion and deletion at both ends

B. A queue where elements are inserted only at the front

C. A stack that allows only last-in-first-out operations

D. A linked list with only one pointer per node

Solution

1. Step 1: Understand the definition of dequeue

   A dequeue is a data structure where elements can be added or removed from both front and rear ends.

2. Step 2: Compare options with definition

   A double-ended queue allowing insertion and deletion at both ends correctly describes a dequeue. Options B, C, and D describe other data structures.

3. Final Answer:

   A double-ended queue allowing insertion and deletion at both ends -> Option A

4. Quick Check:

   Dequeue = double-ended queue [OK]

Hint: Dequeue means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing dequeue with stack or simple queue
• Thinking insertion is only at one end
• Mixing dequeue with linked list structure

2. Which of the following is the correct syntax to insert an element 10 at the front of a dequeue named dq in C?

easy

A. dq.insertFront(10);

B. insertFront(dq, 10);

C. dq->insertFront(10);

D. insertFront(10, dq);

Solution

1. Step 1: Identify typical C function call syntax

   In C, functions are called with function_name(arguments). Here, insertFront is a function taking dequeue and value.

2. Step 2: Match options with C syntax

   insertFront(dq, 10); matches C style: insertFront(dq, 10);. Options B and C use object syntax (C++ style). insertFront(10, dq); reverses argument order.

3. Final Answer:

   insertFront(dq, 10); -> Option B

4. Quick Check:

   C function call = insertFront(dq, 10) [OK]

Hint: C uses function_name(dequeue, value) syntax [OK]

Common Mistakes:

• Using object method syntax in C
• Swapping argument order
• Using arrow operator without pointer

3. Consider the following C code for dequeue operations:

initialize dequeue dq
insertRear(dq, 5);
insertFront(dq, 3);
insertRear(dq, 7);
deleteFront(dq);
insertFront(dq, 2);
deleteRear(dq);

What is the final state of the dequeue (front to rear)?

medium

A. 2 -> 3 -> null

B. 3 -> 5 -> 7 -> null

C. 2 -> 5 -> null

D. 5 -> 7 -> null

Solution

1. Step 1: Trace each operation step-by-step

   Start empty: [] insertRear 5: [5] insertFront 3: [3,5] insertRear 7: [3,5,7] deleteFront: remove 3 -> [5,7] insertFront 2: [2,5,7] deleteRear: remove 7 -> [2,5]

2. Step 2: Write final dequeue state front to rear

   Final state is 2 at front, then 5, then null.

3. Final Answer:

   2 -> 5 -> null -> Option C

4. Quick Check:

   Trace ops carefully = 2 -> 5 [OK]

Hint: Track each insert/delete step in order [OK]

Common Mistakes:

• Forgetting which end deleteFront/deleteRear affects
• Mixing order of insertFront and insertRear
• Skipping an operation

4. The following code snippet for dequeue operations has a bug. What is the error?

initialize dequeue dq
insertFront(dq, 10);
deleteRear(dq);
deleteRear(dq);

medium

A. Deleting from rear when dequeue is empty causes underflow

B. insertFront syntax is incorrect

C. Cannot deleteRear twice in a row

D. Dequeue must be initialized with size

Solution

1. Step 1: Analyze operations and dequeue state

   Start empty: [] insertFront 10: [10] deleteRear: removes 10 -> [] deleteRear: tries to remove from empty dequeue

2. Step 2: Identify error from empty dequeue deletion

   Deleting from empty dequeue causes underflow error. This is the bug.

3. Final Answer:

   Deleting from rear when dequeue is empty causes underflow -> Option A

4. Quick Check:

   Deleting empty dequeue = underflow error [OK]

Hint: Check if dequeue is empty before delete [OK]

Common Mistakes:

• Ignoring empty dequeue before delete
• Assuming multiple deletes always safe
• Confusing insert syntax with error

5. You have a dequeue initially empty. You perform these operations:

insertRear(dq, 1);
insertRear(dq, 2);
insertFront(dq, 3);
deleteRear(dq);
insertFront(dq, 4);
deleteFront(dq);
insertRear(dq, 5);

What is the final state of the dequeue from front to rear?

hard

A. 4 -> 3 -> 1 -> null

B. 1 -> 5 -> null

C. 4 -> 1 -> 5 -> null

D. 3 -> 1 -> 5 -> null

Solution

1. Step 1: Execute each operation stepwise

   Start: [] insertRear 1: [1] insertRear 2: [1,2] insertFront 3: [3,1,2] deleteRear: remove 2 -> [3,1] insertFront 4: [4,3,1] deleteFront: remove 4 -> [3,1] insertRear 5: [3,1,5]

2. Step 2: Write final dequeue state front to rear

   Final state is 3 at front, then 1, then 5, then null.

3. Final Answer:

   3 -> 1 -> 5 -> null -> Option D

4. Quick Check:

   Trace carefully = 3 -> 1 -> 5 [OK]

Hint: Write state after each operation [OK]

Common Mistakes:

• Deleting wrong end element
• Mixing insertFront and insertRear order
• Skipping delete operations