Dequeue Operation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Push and Pop Operations

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();
    for (int val : dq) {
        std::cout << val << " -> ";
    }
    std::cout << "null" << std::endl;
    return 0;
}

A 30 -> 10 -> null

B 20 -> 10 -> 30 -> null

C 10 -> 30 -> null

D 20 -> 30 -> null

💡 Hint

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

Initially, 10 is added at the back, then 20 at the front, making deque: 20, 10. Then 30 is added at the back: 20, 10, 30. pop_front removes 20, leaving 10, 30.

❓ Predict Output

intermediate

Result of Dequeue Pop Back and Push Front

What will be the output after running this C++ code snippet?

DSA C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {5, 15, 25};
    dq.pop_back();
    dq.push_front(35);
    for (auto x : dq) {
        std::cout << x << " -> ";
    }
    std::cout << "null" << std::endl;
    return 0;
}

A 5 -> 15 -> null

B 35 -> 5 -> 15 -> null

C 5 -> 15 -> 25 -> null

D 15 -> 25 -> 35 -> null

💡 Hint

pop_back removes the last element, push_front adds at the front.

Starting deque: 5, 15, 25. pop_back removes 25, leaving 5, 15. push_front adds 35 at front: 35, 5, 15.

🔧 Debug

advanced

Identify the Error in Deque Pop Operation

What error will this C++ code produce when executed?

DSA C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;
    dq.pop_front();
    std::cout << "Deque size: " << dq.size() << std::endl;
    return 0;
}

A Output: Deque size: 0

B Compilation error: pop_front not defined

C No output, program hangs

D Runtime error: popping from empty deque

💡 Hint

Consider what happens when you pop from an empty deque.

Calling pop_front on an empty deque causes undefined behavior and typically a runtime error or crash.

❓ Predict Output

advanced

Final Deque State After Mixed Operations

What is the final printed state of the deque after this code runs?

DSA C++

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {1, 2, 3, 4};
    dq.pop_back();
    dq.pop_front();
    dq.push_back(5);
    dq.push_front(6);
    for (int x : dq) {
        std::cout << x << " -> ";
    }
    std::cout << "null" << std::endl;
    return 0;
}

A 6 -> 2 -> 3 -> 5 -> null

B 1 -> 2 -> 3 -> 5 -> null

C 2 -> 3 -> 4 -> 5 -> null

D 6 -> 1 -> 2 -> 3 -> null

💡 Hint

Track each operation step-by-step on the deque.

Start: 1,2,3,4 pop_back removes 4: 1,2,3 pop_front removes 1: 2,3 push_back 5: 2,3,5 push_front 6: 6,2,3,5

🧠 Conceptual

expert

Deque Operation Complexity

Which statement correctly describes the time complexity of push_front and pop_back operations on a std::deque in C++?

A Both push_front and pop_back operate in constant time O(1) amortized.

B push_front is O(n), pop_back is O(1).

C push_front is O(1), pop_back is O(n).

D Both push_front and pop_back operate in linear time O(n).

💡 Hint

Consider how std::deque is implemented internally with blocks.

std::deque provides O(1) amortized time for push_front and pop_back because it uses a segmented array allowing efficient insertions/removals at both ends.

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