Dequeue Operation in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a dequeue in data structures?

A dequeue (double-ended queue) is a data structure where elements can be added or removed from both the front and the rear ends.

beginner

Name the two main operations for removing elements in a dequeue.

The two main removal operations are dequeueFront (removes from the front) and dequeueRear (removes from the rear).

beginner

What happens if you try to dequeue from an empty dequeue?

If you try to dequeue from an empty dequeue, it results in an underflow condition, meaning there are no elements to remove.

intermediate

In a dequeue implemented with a circular array, why do we use modulo (%) operation?

Modulo operation helps wrap around the indices when they reach the end of the array, allowing the dequeue to use the array space efficiently in a circular manner.

intermediate

Explain the difference between dequeueFront and dequeueRear operations.

dequeueFront removes the element at the front end and moves the front pointer forward, while dequeueRear removes the element at the rear end and moves the rear pointer backward.

Which operation removes an element from the rear end of a dequeue?

A enqueueRear

B dequeueFront

C dequeueRear

D enqueueFront

dequeueRear removes an element from the rear end of the dequeue.

What condition occurs when trying to dequeue from an empty dequeue?

A Underflow

B Overflow

C Segmentation fault

D No operation

Underflow happens when removing from an empty dequeue.

In a circular array dequeue, what does the modulo operator (%) help with?

A Wrapping indices around the array

B Sorting elements

C Increasing array size

D Checking if dequeue is empty

Modulo helps wrap indices to the start when they reach the array end.

Which pointer moves forward when performing dequeueFront?

A Rear pointer

B Front pointer

C Both pointers

D No pointer moves

The front pointer moves forward after removing the front element.

Which operation adds an element to the front of a dequeue?

A dequeueRear

B dequeueFront

C enqueueRear

D enqueueFront

enqueueFront adds an element at the front end.

Describe the steps involved in the dequeueFront operation on a dequeue implemented with a circular array.

Think about how the front pointer moves and how to handle empty dequeue.

Explain how dequeueRear operation differs from dequeueFront in a dequeue.

Focus on which end is affected and pointer movement.

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