Double Ended Queue Deque in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Deque Operations Sequence

What is the printed state of the deque after performing these operations?

Start with an empty deque.
Operations:
1. Add 10 to front
2. Add 20 to rear
3. Add 30 to front
4. Remove from rear
5. Add 40 to rear

DSA C

Deque deque = createDeque();
addFront(&deque, 10);
addRear(&deque, 20);
addFront(&deque, 30);
removeRear(&deque);
addRear(&deque, 40);
printDeque(&deque);

A 10 -> 20 -> 40 -> null

B 10 -> 30 -> 40 -> null

C 30 -> 20 -> 40 -> null

D 30 -> 10 -> 40 -> null

💡 Hint

Remember that addFront adds to the front and addRear adds to the end. Removing from rear removes the last element.

Step-by-step:
1. addFront 10: deque = 10
2. addRear 20: deque = 10 -> 20
3. addFront 30: deque = 30 -> 10 -> 20
4. removeRear: removes 20, deque = 30 -> 10
5. addRear 40: deque = 30 -> 10 -> 40

🧠 Conceptual

intermediate

Deque Behavior on Mixed Operations

If you perform these operations on an empty deque:
addRear(5), addRear(10), addFront(3), removeFront(), removeRear()
What is the final state of the deque?

A 5 -> null

B 3 -> 5 -> 10 -> null

C 10 -> null

D 3 -> null

💡 Hint

Track each operation carefully and update the deque after each step.

Operations:
1. addRear(5): deque = 5
2. addRear(10): deque = 5 -> 10
3. addFront(3): deque = 3 -> 5 -> 10
4. removeFront(): removes 3, deque = 5 -> 10
5. removeRear(): removes 10, deque = 5

🔧 Debug

advanced

Identify the Error in Deque Implementation

Given this snippet of C code for removing from the rear of a deque, what error will occur?

```c void removeRear(Deque* dq) { if (dq->rear == NULL) return; Node* temp = dq->rear; dq->rear = dq->rear->prev; if (dq->rear != NULL) dq->rear->next = NULL; free(temp); } ```

DSA C

void removeRear(Deque* dq) {
  if (dq->rear == NULL) return;
  Node* temp = dq->rear;
  dq->rear = dq->rear->prev;
  if (dq->rear != NULL) dq->rear->next = NULL;
  free(temp);
}

A Memory leak due to not freeing temp

B Dereferencing NULL pointer if deque has only one element

C No error; code works correctly

D Double free error on temp

💡 Hint

Check what happens when deque has one element and how pointers update.

If deque has one element, dq->rear->prev is NULL, so dq->rear becomes NULL. The if condition prevents dereferencing NULL. Memory is freed properly. No error occurs.

❓ Predict Output

advanced

Deque State After Complex Operations

What is the deque state after these operations?

Start empty.
addRear(1), addRear(2), addFront(3), removeFront(), addRear(4), removeRear(), addFront(5)

DSA C

Deque dq = createDeque();
addRear(&dq, 1);
addRear(&dq, 2);
addFront(&dq, 3);
removeFront(&dq);
addRear(&dq, 4);
removeRear(&dq);
addFront(&dq, 5);
printDeque(&dq);

A 5 -> 1 -> null

B 5 -> 1 -> 2 -> null

C 1 -> 2 -> 4 -> null

D 3 -> 1 -> 4 -> null

💡 Hint

Track each operation carefully and update the deque after each step.

Stepwise:
addRear(1): 1
addRear(2): 1 -> 2
addFront(3): 3 -> 1 -> 2
removeFront(): removes 3, deque = 1 -> 2
addRear(4): 1 -> 2 -> 4
removeRear(): removes 4, deque = 1 -> 2
addFront(5): 5 -> 1 -> 2

🧠 Conceptual

expert

Maximum Number of Elements in Circular Deque

A circular deque is implemented using an array of size 6. If the deque is full, how many elements can it hold at most?

A 5

B 6

C 4

D 7

💡 Hint

In circular deque implementations, one slot is usually kept empty to distinguish full and empty states.

For an array of size n, maximum elements stored is n-1 to differentiate full from empty. Here, 6 - 1 = 5.

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