Double Ended Queue Deque in DSA Java - Execution Trace

Concept Flow - Double Ended Queue Deque

Start

↓

Check Operation Type

↓

Insert Front

↓

Update Front Pointer

↓

Add Node at Front

↓

Update Size

↓

End

↓

Start

↓

Check Operation Type

↓

Remove Front

↓

Update Front Pointer

↓

Remove Node at Front

↓

Update Size

↓

End

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

Execution Sample

DSA Java

Deque deque = new Deque();
deque.insertRear(10);
deque.insertFront(20);
deque.removeRear();
deque.insertRear(30);
System.out.println(deque);

This code creates a deque, inserts 10 at rear, 20 at front, removes rear, inserts 30 at rear, then prints the deque.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create empty deque	[]	head=null, tail=null, size=0	null
2	insertRear(10)	[10]	tail -> new node(10), head -> new node(10), size=1	10 -> null
3	insertFront(20)	[20, 10]	head -> new node(20), new node(20).next = old head(10), size=2	20 -> 10 -> null
4	removeRear()	[20]	tail -> node(20), tail.next=null, size=1	20 -> null
5	insertRear(30)	[20, 30]	tail.next -> new node(30), tail -> new node(30), size=2	20 -> 30 -> null
6	Print deque	[20, 30]	No pointer change	20 -> 30 -> null

💡 All operations completed, deque final state has 2 nodes.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	null	node(10)	node(20)	node(20)	node(20)	node(20)
tail	null	node(10)	node(10)	node(20)	node(30)	node(30)
size	0	1	2	1	2	2

Key Moments - 3 Insights

Why does insertFront update the head pointer but not the tail?

Because insertFront adds a node at the front, the head pointer must point to the new node, but the tail remains the same unless the list was empty (see Step 3 in execution_table).

Why does removeRear update the tail pointer and set tail.next to null?

Removing from rear means the tail moves to the previous node and its next pointer must be null to mark the end (see Step 4 in execution_table).

What happens if we removeRear when only one node exists?

Both head and tail become null, and size becomes 0, indicating an empty deque. This is not shown here but is important to handle.

Visual Quiz - 3 Questions

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

A 10 -> 20 -> null

B 20 -> 10 -> null

C 10 -> null

D 20 -> null

💡 Hint

Check the Visual State column at Step 3 in execution_table.

At which step does the size of the deque become 1 after being 2?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the size changes in variable_tracker and execution_table.

If we insertFront(40) after Step 5, what will be the new head node value?

A 30

B 20

C 40

D 10

💡 Hint

Inserting at front updates the head pointer to the new node (see concept_flow).

Concept Snapshot

Double Ended Queue (Deque) allows insertion and removal at both ends.
Use insertFront and insertRear to add nodes.
Use removeFront and removeRear to remove nodes.
Update head and tail pointers accordingly.
Keep track of size to know deque length.
Visualize as nodes linked from head to tail.

Full Transcript

A Double Ended Queue or Deque lets you add or remove items from both the front and rear ends. When you insert at the front, you create a new node and make it the new head, linking it to the old head. When you insert at the rear, you add a new node after the tail and update the tail pointer. Removing from front or rear updates the head or tail pointers and decreases the size. The example code shows inserting 10 at rear, then 20 at front, removing rear, inserting 30 at rear, and printing the deque. The final deque has nodes 20 and 30 linked. Tracking pointers and size helps manage the deque correctly.

Practice

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

easy

A. A queue where elements can only be added at the rear

B. A data structure where elements can be added or removed from both ends

C. A stack where elements can only be added or removed from the top

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion from both front and rear ends.

2. Step 2: Compare with other data structures

   Unlike queues or stacks, Deque supports operations at both ends.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option B

4. Quick Check:

   Deque = double-ended queue [OK]

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

Common Mistakes:

• Confusing Deque with stack or simple queue
• Thinking Deque allows random access like arrays
• Assuming Deque only works from one end

2. Which of the following is the correct way to create a Deque in Java using the standard library?

easy

A. Deque<Integer> dq = new ArrayDeque<>();

B. Deque<Integer> dq = new Deque<>();

C. Deque<Integer> dq = new Stack<>();

D. Deque<Integer> dq = new Queue<>();

Solution

1. Step 1: Identify valid Deque implementations in Java

   ArrayDeque implements the Deque interface and is the preferred implementation.

2. Step 2: Check syntax correctness

   ArrayDeque is instantiated with new ArrayDeque<>(), which is correct syntax.

3. Final Answer:

   Deque<Integer> dq = new ArrayDeque<>(); -> Option A

4. Quick Check:

   ArrayDeque is standard Deque implementation [OK]

Hint: Use ArrayDeque for Deque in Java [OK]

Common Mistakes:

• Using Stack which is not a Deque
• Trying to instantiate interface Queue directly
• Trying to instantiate the Deque interface directly

3. What will be the output of the following Java code?

Deque<String> dq = new ArrayDeque<>();
dq.addFirst("A");
dq.addLast("B");
dq.addFirst("C");
System.out.println(dq);

medium

A. [A, C, B]

B. [A, B, C]

C. [C, A, B]

D. [B, A, C]

Solution

1. Step 1: Trace addFirst and addLast operations

   addFirst("A") adds A at front: [A]
   addLast("B") adds B at rear: [A, B]
   addFirst("C") adds C at front: [C, A, B]

2. Step 2: Print the Deque

   Printing dq shows elements in order: [C, A, B]

3. Final Answer:

   [C, A, B] -> Option C

4. Quick Check:

   addFirst adds front, addLast adds rear [OK]

Hint: addFirst puts element at front, addLast at rear [OK]

Common Mistakes:

• Mixing order of addFirst and addLast
• Assuming addFirst adds at rear
• Confusing print output format

4. Identify the error in the following Java code using Deque:

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(10);
dq.addLast(20);
dq.removeLast();
dq.removeFirst();
dq.removeFirst();

medium

A. No error, code runs fine

B. Compilation error due to wrong method names

C. Throws NullPointerException on removeLast()

D. Throws NoSuchElementException on last removeFirst()

Solution

1. Step 1: Trace the Deque operations

   Start: empty
   addFirst(10): [10]
   addLast(20): [10, 20]
   removeLast(): removes 20 -> [10]
   removeFirst(): removes 10 -> []
   removeFirst(): tries to remove from empty Deque

2. Step 2: Identify exception on removing from empty Deque

   removeFirst() on empty Deque throws NoSuchElementException

3. Final Answer:

   Throws NoSuchElementException on last removeFirst() -> Option D

4. Quick Check:

   Removing from empty Deque throws NoSuchElementException [OK]

Hint: Removing from empty Deque throws NoSuchElementException [OK]

Common Mistakes:

• Assuming removeFirst returns null instead of exception
• Confusing method names causing compile error
• Thinking removeLast throws NullPointerException

5. You want to implement a task scheduler that processes tasks in the order they arrive but sometimes needs to prioritize urgent tasks by adding them to the front. Which Deque operation combination is best suited for this scenario?

hard

A. Use addLast() for normal tasks and addFirst() for urgent tasks

B. Use addFirst() for normal tasks and addLast() for urgent tasks

C. Use only addLast() for all tasks

D. Use only addFirst() for all tasks

Solution

1. Step 1: Understand task order requirements

   Normal tasks should be processed in arrival order (queue behavior). Urgent tasks should be processed before normal tasks (front insertion).

2. Step 2: Match Deque operations to requirements

   addLast() adds normal tasks at rear (end), preserving arrival order.
   addFirst() adds urgent tasks at front, prioritizing them.

3. Final Answer:

   Use addLast() for normal tasks and addFirst() for urgent tasks -> Option A

4. Quick Check:

   Normal at rear, urgent at front [OK]

Hint: Normal tasks rear, urgent tasks front with addLast/addFirst [OK]

Common Mistakes:

• Reversing addFirst and addLast roles
• Using only one end for all tasks losing priority
• Confusing queue and stack behavior