Double Ended Queue Deque in DSA C - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Insert Front

↓

Update Front Pointer

↓

Check Underflow/Overflow

↓

Delete Front

↓

Update Front Pointer

↓

End

The deque allows insertion and deletion from both ends by updating front and rear pointers accordingly.

Execution Sample

DSA C

deque_init();
deque_insert_rear(10);
deque_insert_front(20);
deque_delete_rear();
deque_insert_rear(30);

This code initializes a deque, inserts 10 at rear, 20 at front, deletes rear, then inserts 30 at rear.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize deque	Empty	front = -1, rear = -1	null
2	Insert 10 at rear	10	front = 0, rear = 0	10 -> null
3	Insert 20 at front	20, 10	front = -1, rear = 0	20 -> 10 -> null
4	Delete rear	20	rear = -1	20 -> null
5	Insert 30 at rear	20, 30	rear = 0	20 -> 30 -> null
6	End	20, 30	front = -1, rear = 0	20 -> 30 -> null

💡 Operations complete; deque contains two elements with front at index -1 and rear at index 0.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
front	-1	0	-1	-1	-1	-1
rear	-1	0	0	-1	0	0
deque array	[]	[10]	[20, 10]	[20]	[20, 30]	[20, 30]

Key Moments - 3 Insights

Why does front move forward when inserting at front?

In this implementation, front moves backward (decrements) to add new elements at the front index, as shown in step 3 where front changes from 0 to -1.

Why does rear move forward when deleting from rear?

When deleting from rear, rear pointer moves backward (decrements) to remove the last element, as in step 4 where rear changes from 0 to -1, removing the element at index 0.

Why is the deque empty at start with front and rear at -1?

Front and rear set to -1 indicate no elements; this is a common way to mark an empty deque, as seen in step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after step 3?

A 10 -> null

B 20 -> 10 -> null

C 20 -> null

D 30 -> 20 -> null

💡 Hint

Check the 'Visual State' column for step 3 in the execution table.

At which step does the rear pointer move from 0 to -1?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Pointer Changes' column and track rear pointer changes.

If we insert 40 at front after step 5, what will front pointer be?

A -2

B -1

C 0

D 1

💡 Hint

Observe how front pointer decrements on insert front operations in variable_tracker.

Concept Snapshot

Double Ended Queue (Deque):
- Supports insertion and deletion at both front and rear.
- Uses two pointers: front and rear.
- Insert front: front pointer moves backward (decrements).
- Insert rear: rear pointer moves forward (increments).
- Delete front/rear updates pointers accordingly.
- Empty deque: front = rear = -1.

Full Transcript

A double ended queue, or deque, allows adding and removing items from both ends. We keep track of two pointers: front and rear. When we insert at the front, we move the front pointer backward (decrement) to add the new element. When we insert at the rear, we move the rear pointer forward (increment). Deleting from front or rear moves the pointers accordingly. Initially, both pointers are set to -1 to show the deque is empty. The visual states show how the list changes after each operation, helping us understand the pointer movements and the current elements in the deque.

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