Double Ended Queue Deque in DSA Python - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Add Front

↓

Update Front

↓

Check Remove?

↓

Remove Front

↓

Update Pointers

↓

Done

The deque allows adding or removing elements from both front and rear ends by updating pointers accordingly.

Execution Sample

DSA Python

from collections import deque
d = deque()
d.append(10)  # add rear
d.appendleft(5) # add front
d.pop()        # remove rear
d.popleft()    # remove front

This code shows adding and removing elements from both ends of a deque.

Execution Table

Step	Operation	Nodes in Deque	Pointer Changes	Visual State
1	Initialize empty deque	[]	head=None, tail=None	null
2	Add 10 at rear	[10]	head=10, tail=10	10 -> null
3	Add 5 at front	[5, 10]	head=5, tail=10	5 -> 10 -> null
4	Remove rear	[5]	head=5, tail=5	5 -> null
5	Remove front	[]	head=None, tail=None	null
6	Attempt remove front on empty	[]	Raises IndexError	null

💡 Deque is empty, no more elements to remove.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
deque	[]	[10]	[5, 10]	[5]	[]	[]
head	None	10	5	5	None	None
tail	None	10	10	5	None	None

Key Moments - 3 Insights

Why does the head pointer change when adding at the front but tail stays the same?

Because adding at the front inserts a new node before the current head, so head moves to new node, but tail remains at the last node (see Step 3 in execution_table).

What happens to pointers when the last element is removed?

Both head and tail become None, indicating the deque is empty (see Step 5 in execution_table).

Why can't we remove from front when deque is empty?

Because there are no nodes to remove, the operation raises an IndexError (see Step 6 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the visual state of the deque?

A 10 -> 5 -> null

B 5 -> 10 -> null

C null

D 5 -> null

💡 Hint

Check the Visual State column at Step 3 in execution_table.

At which step does the deque become empty after removals?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at Nodes in Deque column to find when it becomes [].

If we add 20 at rear after Step 5, what will be the new tail?

A 5

B None

C 20

D 10

💡 Hint

Adding at rear updates tail to new node (see Step 2 for similar operation).

Concept Snapshot

Double Ended Queue (Deque):
- Supports adding/removing from front and rear.
- Head points to front, tail points to rear.
- Adding front updates head; adding rear updates tail.
- Removing last element sets head and tail to None.
- Empty deque has no nodes and pointers are None.

Full Transcript

A double ended queue or deque lets you add or remove items from both ends. We start with an empty deque where head and tail pointers are None. When we add an element at the rear, it becomes both head and tail. Adding at the front inserts before head and updates head pointer. Removing from rear or front updates pointers accordingly. When the last element is removed, both pointers become None, showing the deque is empty. Trying to remove from an empty deque raises an IndexError. This step-by-step trace shows how the deque changes visually and how pointers move with each operation.