Double Ended Queue Deque in DSA C - Build from Scratch

Double Ended Queue (Deque) Implementation in C

📖 Scenario: Imagine you are managing a line of customers at a store where people can join or leave from both the front and the back of the line. This line is called a double ended queue or deque.

🎯 Goal: You will build a simple double ended queue (deque) using an array in C. You will add elements to the front and back, remove elements from the front and back, and finally print the current state of the deque.

📋 What You'll Learn

Create an array-based deque with fixed size 5

Use two integer variables front and rear to track ends

Implement functions to add to front and rear

Implement functions to remove from front and rear

Print the deque elements from front to rear

💡 Why This Matters

🌍 Real World

Deques are used in real-world scenarios like managing tasks where you can add or remove from both ends, such as undo-redo operations or browser history.

💼 Career

Understanding deque implementation helps in software development roles where efficient data handling and queue management are required.

1

Create the deque data structure

Create an integer array called deque with size 5. Also create two integer variables called front and rear and set both to -1.

DSA C

# Create the deque array and front, rear variables
# Your code here

Hint

Use int deque[5]; to create the array. Initialize front and rear to -1 to show the deque is empty.

2

Add elements to the rear of the deque

Write a function called addRear that takes an integer value and adds it to the rear of the deque. Update rear and front accordingly when adding the first element.

DSA C

int deque[5];
int front = -1;
int rear = -1;

// Write addRear function below
// Your code here

Hint

Check if rear reached 4 (end of array). If empty, set front to 0. Then increase rear and store the value.

3

Add elements to the front of the deque

Write a function called addFront that takes an integer value and adds it to the front of the deque. Update front accordingly. If the deque is empty, set front and rear to 0.

DSA C

int deque[5];
int front = -1;
int rear = -1;

void addRear(int value) {
    if (rear == 4) {
        return; // deque full at rear
    }
    if (front == -1) {
        front = 0;
    }
    rear++;
    deque[rear] = value;
}

// Write addFront function below
// Your code here

Hint

If front is 0, no space to add front. If empty, set both front and rear to 0 and add value. Otherwise, decrease front and add value.

4

Print the current deque elements

Write a function called printDeque that prints all elements from front to rear separated by spaces. Then call addRear(10), addRear(20), addFront(5), and finally print the deque.

DSA C

Hint

Loop from front to rear and print each element with a space. Call the add functions as instructed before printing.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A queue where insertion happens only at the rear and deletion at the front

B. A data structure where insertion and deletion can happen at both ends

C. A stack where insertion and deletion happen only at one end

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows adding and removing elements from both front and rear ends.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, Deque supports operations at both ends.

3. Final Answer:

   A data structure where insertion and deletion can happen at both ends -> Option B

4. Quick Check:

   Deque = Both ends insertion/deletion [OK]

Hint: Deque means double-ended queue, both ends allowed [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking insertion is only at one end
• Assuming random access like arrays

2. Which of the following is the correct syntax to initialize an empty deque in C using an array implementation?

easy

A. int deque[] = {}; int front = 0, rear = 0;

B. int deque[SIZE] = NULL; int front = 0, rear = 0;

C. int deque[SIZE]; int front = -1, rear = -1;

D. int deque[SIZE]; int front = 0, rear = -1;

Solution

1. Step 1: Understand initialization of deque with front and rear

   Front and rear are set to -1 to indicate empty deque.

2. Step 2: Check array declaration and initial values

   int deque[SIZE]; int front = -1, rear = -1; correctly declares array and sets front and rear to -1.

3. Final Answer:

   int deque[SIZE]; int front = -1, rear = -1; -> Option C

4. Quick Check:

   Empty deque front and rear = -1 [OK]

Hint: Empty deque front and rear start at -1 [OK]

Common Mistakes:

• Setting front or rear to 0 initially
• Using NULL for array initialization
• Leaving array size unspecified

3. Consider the following operations on an empty deque of size 5 implemented using an array:
insertRear(10); insertRear(20); insertFront(5); deleteRear(); insertFront(15);
What is the content of the deque from front to rear after these operations?

medium

A. 15 -> 5 -> 10 -> null

B. 5 -> 15 -> 10 -> null

C. 15 -> 5 -> null

D. 10 -> 5 -> 15 -> null

Solution

1. Step 1: Perform insertRear(10) and insertRear(20)

   Deque: 10 -> 20

2. Step 2: Perform insertFront(5)

   Deque: 5 -> 10 -> 20

3. Step 3: Perform deleteRear()

   Removes 20, Deque: 5 -> 10

4. Step 4: Perform insertFront(15)

   Deque: 15 -> 5 -> 10

5. Final Answer:

   15 -> 5 -> 10 -> null -> Option A

6. Quick Check:

   Operations result in 15,5,10 order [OK]

Hint: Track front and rear insertions stepwise [OK]

Common Mistakes:

• Forgetting deleteRear removes last element
• Mixing order of insertFront and insertRear
• Assuming insertFront adds at rear

4. Given the following code snippet for deque insertion at front, identify the error:

void insertFront(int deque[], int *front, int *rear, int value) {
  if (*front == 0) {
    printf("Deque is full at front\n");
    return;
  }
  (*front)--;
  deque[*front] = value;
}

medium

A. It incorrectly checks full condition only at front == 0

B. It decrements front before insertion causing invalid index

C. It does not check if deque is empty before insertion

D. It should increment front instead of decrement

Solution

1. Step 1: Analyze the full condition check

   Checking only if front == 0 is not enough to detect full deque.

2. Step 2: Understand circular deque logic

   Deque can be full even if front != 0, so this check is incomplete.

3. Final Answer:

   It incorrectly checks full condition only at front == 0 -> Option A

4. Quick Check:

   Full check must consider rear position too [OK]

Hint: Full deque check needs both front and rear positions [OK]

Common Mistakes:

• Assuming front == 0 means full always
• Not handling circular wrap-around
• Decrementing front without boundary check

5. You have a deque of size 4 implemented using a circular array. Initially empty, you perform:
insertRear(1); insertRear(2); insertFront(3); insertFront(4); deleteRear(); insertRear(5);
What is the final state of the deque from front to rear?

hard

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

B. 4 -> 3 -> 5 -> null

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

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

Solution

1. Step 1: InsertRear(1), InsertRear(2)

   Deque: 1 -> 2

2. Step 2: InsertFront(3), InsertFront(4)

   Deque: 4 -> 3 -> 1 -> 2 (deque full)

3. Step 3: DeleteRear()

   Removes 2, Deque: 4 -> 3 -> 1

4. Step 4: InsertRear(5)

   Deque: 4 -> 3 -> 1 -> 5 (full again)

5. Final Answer:

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

6. Quick Check:

   Circular deque final state matches 4 -> 3 -> 1 -> 5 -> null [OK]

Hint: Track circular wrap and full capacity carefully [OK]

Common Mistakes:

• Ignoring circular wrap-around
• Misordering front and rear elements
• Forgetting deleteRear removes last element