Double Ended Queue Deque in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Deque Operations Sequence

What is the printed state of the deque after executing the following C++ code?

DSA C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;
    dq.push_back(10);
    dq.push_front(20);
    dq.push_back(30);
    dq.pop_front();
    dq.push_front(40);
    for (int x : dq) std::cout << x << " -> ";
    std::cout << "null" << std::endl;
    return 0;
}

A 40 -> 10 -> 30 -> null

B 20 -> 10 -> 30 -> null

C 10 -> 30 -> null

D 40 -> 20 -> 10 -> 30 -> null

💡 Hint

Remember that push_front adds to the front and pop_front removes from the front.

The operations modify the deque as follows:

• push_back(10): deque = 10
• push_front(20): deque = 20, 10
• push_back(30): deque = 20, 10, 30
• pop_front(): removes 20, deque = 10, 30
• push_front(40): deque = 40, 10, 30

Printing shows: 40 -> 10 -> 30 -> null

🧠 Conceptual

intermediate

Deque Size After Mixed Operations

If a deque starts empty and the following operations are performed:

push_back(5), push_front(3), push_back(7), pop_back(), pop_front(), push_front(9)

What is the size of the deque now?

A 2

B 3

C 1

D 0

💡 Hint

Count each operation carefully and track the deque size step-by-step.

Step-by-step size changes:

• push_back(5): size = 1
• push_front(3): size = 2
• push_back(7): size = 3
• pop_back(): removes 7, size = 2
• pop_front(): removes 3, size = 1
• push_front(9): size = 2

Final size is 2, but note the last operation adds one element, so the final size is 2.

Rechecking: Actually, after pop_front size was 1, then push_front(9) makes size 2.

🔧 Debug

advanced

Identify the Runtime Error in Deque Access

What error will the following code produce when run?

DSA C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3};
    std::cout << dq.at(3) << std::endl;
    return 0;
}

A Prints 3

B Segmentation fault

C std::out_of_range exception

D Compilation error

💡 Hint

Check the valid index range for the deque elements.

The deque has elements at indices 0, 1, and 2. Accessing dq.at(3) is out of range.

The at() method throws std::out_of_range exception when index is invalid.

📝 Syntax

advanced

Correct Syntax to Insert at Both Ends

Which option correctly inserts 100 at the front and 200 at the back of a std::deque named dq?

A dq.push_back(100); dq.push_front(200);

B dq.push_front(100); dq.push_back(200);

C dq.insert_front(100); dq.insert_back(200);

D dq.add_front(100); dq.add_back(200);

💡 Hint

Check the correct method names for deque insertion at front and back.

The correct methods are push_front() and push_back().

Options C and D use invalid method names.

Option B reverses the intended positions.

🚀 Application

expert

Deque Usage for Palindrome Check

You want to check if a string is a palindrome using a deque. Which approach below correctly uses deque operations to compare characters from both ends?

A Push all characters to deque, then compare characters using at() with increasing indices.

B Push all characters to deque, then compare only front characters repeatedly without popping.

C Push all characters to deque, then pop_back() repeatedly without comparing characters.

D Push all characters to deque, then while size > 1, compare front and back characters using front() and back(), pop_front() and pop_back() if equal.

💡 Hint

Think about how to compare characters from both ends moving inward.

To check palindrome, compare characters from front and back moving inward.

Option D correctly uses front() and back() to compare, then removes them if equal.

Other options do not compare both ends or do not remove characters properly.

Practice

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

easy

A. A stack where elements are added and removed only from the top

B. A queue where elements are added only at the rear and removed from the front

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

D. A list where elements can be accessed randomly by index

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion at both front and rear ends, unlike a queue or stack.

2. Step 2: Compare with other data structures

   Queue allows operations at one end for insertion and the other for deletion; stack allows operations only at one end.

3. Final Answer:

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

4. Quick Check:

   Deque = double-ended queue allowing both ends operations [OK]

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

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque allows random access like arrays
• Assuming deque only works like a queue

2. Which of the following is the correct syntax to declare a deque of integers in C++?

easy

A. deque<int> d = new deque();

B. deque<int> d;

C. deque<int> d[];

D. deque d<int>;

Solution

1. Step 1: Recall C++ STL deque declaration syntax

   The correct syntax uses template syntax: deque<int> d; declares a deque of integers named d.

2. Step 2: Check other options for syntax errors

   'deque<int> d = new deque();' uses invalid 'new' syntax for STL containers, 'deque d<int>;' has wrong template placement, 'deque<int> d[];' declares an array of deques incorrectly.

3. Final Answer:

   deque<int> d; -> Option B

4. Quick Check:

   Correct C++ deque declaration = deque<int> d; [OK]

Hint: Use template syntax: deque<Type> name; [OK]

Common Mistakes:

• Placing template brackets incorrectly
• Using Java or other language syntax
• Declaring arrays of deques without proper syntax

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

#include <iostream>
#include <deque>
using namespace std;
int main() {
  deque<int> d;
  d.push_back(10);
  d.push_front(20);
  d.push_back(30);
  d.pop_front();
  for (auto x : d) cout << x << " ";
  return 0;
}

medium

A. 10 30

B. 30 10

C. 20 10 30

D. 10 20 30

Solution

1. Step 1: Trace deque operations step-by-step

   Initially empty deque. push_back(10) -> [10]. push_front(20) -> [20, 10]. push_back(30) -> [20, 10, 30]. pop_front() removes 20 -> [10, 30].

2. Step 2: Print elements in deque

   Loop prints elements in order: 10 30

3. Final Answer:

   10 30 -> Option A

4. Quick Check:

   After pop_front, deque = 10 30 [OK]

Hint: Track push_front/back and pop_front carefully [OK]

Common Mistakes:

• Forgetting pop_front removes front element
• Mixing order of push_front and push_back
• Assuming pop_front removes from back

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

#include <deque>
using namespace std;
int main() {
  deque<int> d;
  d.push_front(5);
  d.pop_back();
  d.pop_back();
  return 0;
}

medium

A. deque<int> d; is invalid declaration

B. push_front() is not a valid deque method

C. Missing #include <iostream> for cout

D. Calling pop_back() on empty deque causes undefined behavior

Solution

1. Step 1: Analyze deque operations

   After push_front(5), deque has one element [5]. First pop_back() removes 5, deque becomes empty []. Second pop_back() is called on empty deque.

2. Step 2: Understand behavior of pop_back on empty deque

   Calling pop_back() on empty deque causes undefined behavior or runtime error.

3. Final Answer:

   Calling pop_back() on empty deque causes undefined behavior -> Option D

4. Quick Check:

   pop_back on empty deque = error [OK]

Hint: Never pop from empty deque to avoid errors [OK]

Common Mistakes:

• Assuming pop_back on empty deque is safe
• Confusing push_front with invalid method
• Ignoring missing iostream is irrelevant here

5. You want to implement a sliding window maximum using a deque in C++. Which deque operation is essential to maintain the window elements in decreasing order?

hard

A. Remove elements from the back while they are smaller than the new element

B. Remove elements from the front while they are smaller than the new element

C. Add new elements only at the front

D. Add new elements only at the back without removal

Solution

1. Step 1: Understand sliding window maximum logic

   To keep maximum at front, remove all smaller elements from back before adding new element at back.

2. Step 2: Identify correct deque operation

   Removing smaller elements from back maintains decreasing order, ensuring front is max.

3. Final Answer:

   Remove elements from the back while they are smaller than the new element -> Option A

4. Quick Check:

   Sliding window max uses back removals for order [OK]

Hint: Remove smaller from back to keep max at front [OK]

Common Mistakes:

• Removing from front instead of back
• Adding elements without removing smaller ones
• Adding only at front breaks order