Dequeue Operation in DSA Java - Execution Trace

Concept Flow - Dequeue Operation

Start

↓

Check if Deque is empty?

Yes→Return error or null

No↓

Choose operation: Remove Front or Remove Rear

↓

Remove front node

↓

Update front pointer

↓

Return removed value

↓

End

The dequeue operation first checks if the deque is empty. If not, it removes an element either from the front or rear, updates pointers accordingly, and returns the removed value.

Execution Sample

DSA Java

Deque dq = new Deque();
dq.addRear(10);
dq.addRear(20);
dq.removeFront();
dq.removeRear();

This code adds two elements to the rear of the deque, then removes one from the front and one from the rear.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create empty deque	[]	front=null, rear=null	null
2	Add 10 at rear	[10]	front=Node(10), rear=Node(10)	10 -> null
3	Add 20 at rear	[10, 20]	rear=Node(20), Node(10).next=Node(20)	10 -> 20 -> null
4	Remove front	[20]	front=Node(20)	20 -> null
5	Remove rear	[]	front=null, rear=null	null
6	Remove front on empty deque	[]	No change	null (empty)

💡 Step 6 stops because deque is empty; no nodes to remove.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
front	null	Node(10)	Node(10)	Node(20)	null	null
rear	null	Node(10)	Node(20)	Node(20)	null	null
size	0	1	2	1	0	0

Key Moments - 3 Insights

Why do we update the front pointer when removing from the front?

Because the front node is removed, the front pointer must move to the next node to keep the deque valid. See Step 4 in execution_table where front changes from Node(10) to Node(20).

What happens when we remove the last element from the deque?

Both front and rear pointers become null, indicating the deque is empty. This is shown in Step 5 where after removing rear, front and rear are null.

Why can't we remove from an empty deque?

Because there are no nodes to remove, attempting to do so should return an error or null. Step 6 shows no pointer changes and the visual state remains null.

Visual Quiz - 3 Questions

Look at the execution_table, what is the front pointer after Step 3?

A Node(20)

B null

C Node(10)

D Node(30)

💡 Hint

Check the 'Pointer Changes' column at Step 3 in execution_table.

At which step does the deque become empty?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look for when both front and rear pointers become null in execution_table.

If we remove from the rear at Step 4 instead of front, what would the visual state be?

A 10 -> null

B 20 -> null

C null

D 10 -> 20 -> null

💡 Hint

Removing rear removes the last node; check nodes in list before Step 4.

Concept Snapshot

Deque Operation:
- Remove element from front or rear
- Check if deque is empty first
- Update front or rear pointer after removal
- If last element removed, front and rear become null
- Returns removed element or error if empty

Full Transcript

The dequeue operation involves removing an element from either the front or rear of the deque. First, it checks if the deque is empty. If empty, removal is not possible and returns null or error. If not empty, it removes the node at the chosen end, updates the front or rear pointer to the next or previous node accordingly, and returns the removed value. When the last element is removed, both front and rear pointers become null, indicating the deque is empty. This process ensures the deque remains valid after each removal.

Practice

1. What is the main difference between a deque and a regular queue?

easy

A. Deque is slower than queue in all operations

B. Deque only allows insertion, queue only allows deletion

C. Deque allows insertion and deletion from both ends, queue only from one end

D. Deque stores elements in sorted order, queue does not

Solution

1. Step 1: Understand queue operations

   A regular queue allows insertion at the rear and deletion from the front only.

2. Step 2: Understand deque operations

   A deque (double-ended queue) allows insertion and deletion at both front and rear ends.

3. Final Answer:

   Deque allows insertion and deletion from both ends, queue only from one end -> Option C

4. Quick Check:

   Deque = Both ends operations [OK]

Hint: Deque = double-ended operations, queue = single-ended [OK]

Common Mistakes:

• Thinking deque only allows insertion
• Confusing deque with stack
• Assuming deque stores sorted data

2. Which of the following is the correct way to add an element to the front of a Java Deque named dq?

easy

A. dq.addLast(element);

B. dq.addFirst(element);

C. dq.pushBack(element);

D. dq.enqueueFront(element);

Solution

1. Step 1: Recall Java Deque methods

   Java Deque interface provides addFirst() to add element at the front.

2. Step 2: Check options for correct method

   Only dq.addFirst(element); correctly adds at front.

3. Final Answer:

   dq.addFirst(element); -> Option B

4. Quick Check:

   addFirst() adds front [OK]

Hint: Use addFirst() to add at front in Java Deque [OK]

Common Mistakes:

• Using addLast() to add at front
• Using non-existent methods like pushBack()
• Confusing enqueue with Deque methods

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

Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(10);
dq.addFirst(20);
dq.addLast(30);
System.out.println(dq);

medium

A. [20, 30, 10]

B. [10, 20, 30]

C. [30, 10, 20]

D. [20, 10, 30]

Solution

1. Step 1: Trace additions to deque

   First addLast(10) adds 10 at rear: [10]. Then addFirst(20) adds 20 at front: [20, 10]. Then addLast(30) adds 30 at rear: [20, 10, 30].

2. Step 2: Print deque state

   Printing dq shows elements in order: [20, 10, 30].

3. Final Answer:

   [20, 10, 30] -> Option D

4. Quick Check:

   addFirst adds front, addLast adds rear [OK]

Hint: Track addFirst at front, addLast at rear [OK]

Common Mistakes:

• Mixing order of addFirst and addLast
• Assuming addLast adds at front
• Confusing printed order with insertion order

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

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

medium

A. removeFront() method does not exist in Deque

B. addFirst() cannot be used with LinkedList

C. Deque cannot store String elements

D. dq should be initialized with ArrayDeque, not LinkedList

Solution

1. Step 1: Check Deque methods

   Deque interface does not have a method named removeFront(). The correct method to remove from front is removeFirst().

2. Step 2: Verify other statements

   addFirst() works with LinkedList, Deque can store Strings, and LinkedList is a valid Deque implementation.

3. Final Answer:

   removeFront() method does not exist in Deque -> Option A

4. Quick Check:

   Use removeFirst() to remove front [OK]

Hint: Use removeFirst(), not removeFront() [OK]

Common Mistakes:

• Using removeFront() instead of removeFirst()
• Thinking LinkedList can't implement Deque
• Confusing method names for removal

5. Given a Deque dq initially empty, which sequence of operations will result in the deque containing [5, 10, 15] from front to rear?

hard

A. dq.addFirst(5); dq.addLast(10); dq.addLast(15);

B. dq.addLast(15); dq.addLast(10); dq.addLast(5);

C. dq.addFirst(5); dq.addFirst(10); dq.addFirst(15);

D. dq.addLast(5); dq.addLast(15); dq.addLast(10);

Solution

1. Step 1: Analyze dq.addFirst(5); dq.addLast(10); dq.addLast(15); operations

   Start empty: []. addFirst(5) -> [5]. addLast(10) -> [5, 10]. addLast(15) -> [5, 10, 15].

2. Step 2: Verify final deque order

   Deque after operations is [5, 10, 15], matching the required order.

3. Final Answer:

   dq.addFirst(5); dq.addLast(10); dq.addLast(15); -> Option A

4. Quick Check:

   addFirst front, addLast rear = correct order [OK]

Hint: Add 5 front, then 10 and 15 at rear for correct order [OK]

Common Mistakes:

• Adding all elements at front reverses order
• Adding all elements at rear but starting with wrong element
• Mixing addFirst and addLast order