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.