Dequeue Operation in DSA C++ - Execution Trace

Concept Flow - Dequeue Operation

Start Dequeue Operation

↓

Check if Deque is Empty?

Yes→Return Error or Null

No↓

Remove Node from Front or Rear

↓

Update Front or Rear Pointer

↓

Return Removed Value

↓

Done

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

Execution Sample

DSA C++

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {10, 20, 30};
    int val = dq.front(); dq.pop_front();
    // val = 10, dq = 20 -> 30
    val = dq.back(); dq.pop_back();
    // val = 30, dq = 20
    return 0;
}

This code removes elements first from the front, then from the rear of a deque, showing how the deque shrinks.

Execution Table

Step	Operation	Nodes in Deque	Pointer Changes	Visual State
1	Start with deque {10, 20, 30}	10 -> 20 -> 30	front points to 10, rear points to 30	10 -> 20 -> 30
2	pop_front()	20 -> 30	front moves from 10 to 20	20 -> 30
3	Return removed value 10	20 -> 30	no pointer change	20 -> 30
4	pop_back()	20	rear moves from 30 to 20	20
5	Return removed value 30	20	no pointer change	20
6	pop_front()	empty	front and rear become null (deque empty)	empty
7	Return removed value 20	empty	no pointer change	empty
8	pop_front() on empty deque	empty	no pointer change	empty

💡 Deque becomes empty after removing all elements; further pop operations return error or null.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
front	points to 10	points to 20	points to 20	null	null
rear	points to 30	points to 30	points to 20	null	null
deque size	3	2	1	0	0
removed value	N/A	10	30	20	N/A

Key Moments - 3 Insights

Why does the front pointer move forward after pop_front but the rear pointer stays the same?

Because pop_front removes the front node, so front must move to the next node (see Step 2). The rear pointer stays until pop_back removes the rear node (see Step 4).

What happens when the last element is removed from the deque?

Both front and rear pointers become null, indicating the deque is empty (see Step 6). This prevents dangling pointers.

Why does pop_front on an empty deque not change pointers?

Because the deque is already empty, no pointers can move or nodes removed (see Step 8). The operation returns an error or null.

Visual Quiz - 3 Questions

Look at the execution table, what is the deque state after Step 4?

A 20 -> 30

B 20

C empty

D 10 -> 20 -> 30

💡 Hint

Check the 'Visual State' column in Step 4 of the execution_table.

At which step does the deque become empty?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

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

If we call pop_back() instead of pop_front() at Step 2, what would be the new front pointer?

A Points to 10

B Points to 20

C Points to 30

D Null

💡 Hint

Consider that pop_back removes from rear, so front pointer does not move (see variable_tracker).

Concept Snapshot

Dequeue Operation:
- Removes element from front or rear
- Update front or rear pointer accordingly
- If empty, pointers set to null
- Returns removed element
- Handles empty deque safely

Full Transcript

The dequeue operation removes an element from either the front or rear of the deque. First, it checks if the deque is empty. If empty, it returns an error or null. If not, it removes the node from the chosen end, updates the front or rear pointer to the next node or null if empty, and returns the removed value. The pointers track the current front and rear nodes. When the last element is removed, both pointers become null to indicate the deque is empty. Further removal attempts on an empty deque do not change pointers and return an error or null.

Practice

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

easy

A. Deque allows insertion and deletion from both ends, queue only from front and rear respectively

B. Deque only allows insertion at the rear, queue allows insertion at both ends

C. Deque is always sorted, queue is not

D. Deque uses arrays, queue uses linked lists

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 front and rear respectively -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended, so both ends allowed [OK]

Common Mistakes:

• Thinking deque only inserts at rear
• Confusing deque with sorted data structure
• Assuming deque uses only arrays

2. Which of the following is the correct syntax to insert an element 10 at the front of a std::deque<int> named d in C++?

easy

A. d.push(10);

B. d.push_front(10);

C. d.insert_front(10);

D. d.add_front(10);

Solution

1. Step 1: Recall deque insertion methods

   In C++, std::deque uses push_front() to insert at the front.

2. Step 2: Check method names

   Only push_front(10); is valid syntax for front insertion.

3. Final Answer:

   d.push_front(10); -> Option B

4. Quick Check:

   push_front() inserts at front [OK]

Hint: Use push_front() to add at front in deque [OK]

Common Mistakes:

• Using push() which is not a deque method
• Using insert_front() which doesn't exist
• Confusing with vector methods

3. What will be the output of the following C++ code snippet?

std::deque<int> d = {1, 2, 3};
d.push_front(0);
d.push_back(4);
d.pop_front();
for (int x : d) std::cout << x << " ";

medium

A. 1 2 3 4

B. 0 1 2 3 4

C. 1 2 3

D. 0 1 2 3

Solution

1. Step 1: Trace deque operations

   Initial deque: [1, 2, 3]
   After push_front(0): [0, 1, 2, 3]
   After push_back(4): [0, 1, 2, 3, 4]
   After pop_front(): removes 0, deque becomes [1, 2, 3, 4]

2. Step 2: Print elements

   Elements printed are 1 2 3 4 with spaces.

3. Final Answer:

   1 2 3 4 -> Option A

4. Quick Check:

   pop_front removes first element [OK]

Hint: pop_front removes first inserted element [OK]

Common Mistakes:

• Forgetting pop_front removes 0
• Confusing push_front and push_back order
• Printing without spaces

4. Identify the error in the following C++ code using std::deque:

std::deque<int> d;
d.push_back(5);
d.pop_front();
std::cout << d.front();

medium

A. deque must be initialized with size

B. push_back() syntax is incorrect

C. pop_front() called on empty deque causes undefined behavior

D. front() cannot be used after pop_front()

Solution

1. Step 1: Analyze deque state after operations

   Initially, deque is empty.
   push_back(5) adds 5: deque = [5]
   pop_front() removes 5: deque becomes empty again.

2. Step 2: Check front() usage

   Calling front() on empty deque is undefined behavior and may cause runtime error.

3. Final Answer:

   pop_front() called on empty deque causes undefined behavior -> Option C

4. Quick Check:

   front() on empty deque is invalid [OK]

Hint: Don't pop from empty deque before accessing front [OK]

Common Mistakes:

• Assuming front() returns 5 after pop_front
• Thinking push_back syntax is wrong
• Believing deque needs size at initialization

5. Given a std::deque<int> d = {10, 20, 30, 40, 50}, which sequence of operations will result in the deque containing 10 20 30 after all operations?

hard

A. d.pop_back(); d.pop_front();

B. d.pop_front(); d.pop_back();

C. d.pop_front(); d.pop_front();

D. d.pop_back(); d.pop_back();

Solution

1. Step 1: Start with initial deque

   Deque = [10, 20, 30, 40, 50]

2. Step 2: Apply operations for each option

   d.pop_back(); d.pop_back();: pop_back() removes 50 -> [10, 20, 30, 40], pop_back() removes 40 -> [10, 20, 30]
   d.pop_front(); d.pop_back();: pop_front() removes 10 -> [20, 30, 40, 50], pop_back() removes 50 -> [20, 30, 40]
   d.pop_front(); d.pop_front();: pop_front() twice removes 10 and 20 -> [30, 40, 50]
   d.pop_back(); d.pop_front();: pop_back() removes 50 -> [10, 20, 30, 40], pop_front() removes 10 -> [20, 30, 40]

3. Step 3: Compare results

   Only d.pop_back(); d.pop_back(); results in [10, 20, 30]. The other sequences result in different contents.

4. Final Answer:

   d.pop_back(); d.pop_back(); -> Option D

5. Quick Check:

   Two pop_back() removes the last two elements [OK]

Hint: pop_back twice removes last two elements [OK]

Common Mistakes:

• Removing wrong ends in wrong order
• Assuming pop_back twice keeps 20
• Confusing pop_front and pop_back effects