Double Ended Queue Deque in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Deque Operations in Rust

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

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(10);
    deque.push_front(20);
    deque.push_back(30);
    deque.pop_front();
    deque.push_front(40);
    println!("{:?}", deque);
}

A [20, 10, 30]

B [40, 10, 30]

C [10, 30]

D [40, 20, 10, 30]

💡 Hint

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

The deque starts empty. We add 10 at the back: [10]. Then add 20 at the front: [20, 10]. Add 30 at the back: [20, 10, 30]. Pop front removes 20: [10, 30]. Push front 40: [40, 10, 30].

🧠 Conceptual

intermediate

Deque Behavior on Mixed Operations

If you perform these operations on an empty deque: push_back(1), push_back(2), push_front(3), pop_back(), pop_front(), what is the final state of the deque?

A [1]

B [2]

C [3]

D []

💡 Hint

Track each operation step-by-step from an empty deque.

Start empty []. push_back(1) → [1]. push_back(2) → [1, 2]. push_front(3) → [3, 1, 2]. pop_back() removes 2 → [3, 1]. pop_front() removes 3 → [1].

🔧 Debug

advanced

Identify the Runtime Error in Deque Usage

What error will this Rust code produce when run?

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(5);
    deque.pop_front();
    deque.pop_front();
}

A None (runs without error)

B panic! at 'called `Option::unwrap()` on a `None` value'

C IndexOutOfBounds error

D Compile-time error due to pop_front usage

💡 Hint

Check what pop_front returns when deque is empty and if it causes panic automatically.

pop_front returns an Option. Calling pop_front on empty deque returns None but does not panic. The code runs without error.

❓ Predict Output

advanced

Deque State After Multiple Push and Pop

What is the final printed deque after this Rust code runs?

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    for i in 1..=4 {
        deque.push_back(i);
    }
    deque.pop_front();
    deque.push_front(10);
    deque.pop_back();
    deque.push_back(20);
    println!("{:?}", deque);
}

A [1, 2, 3, 20]

B [2, 3, 4, 20]

C [10, 1, 2, 3]

D [10, 2, 3, 20]

💡 Hint

Follow each operation carefully, especially the order of push and pop.

Start empty []. push_back 1..4 → [1, 2, 3, 4]. pop_front removes 1 → [2, 3, 4]. push_front 10 → [10, 2, 3, 4]. pop_back removes 4 → [10, 2, 3]. push_back 20 → [10, 2, 3, 20].

🚀 Application

expert

Deque Usage for Sliding Window Maximum

Given a deque used to store indices for a sliding window maximum algorithm, what is the state of the deque after processing the array [2, 1, 3] with window size 2, after processing the third element?

DSA Rust

use std::collections::VecDeque;

fn main() {
    let arr = [2, 1, 3];
    let k = 2;
    let mut deque: VecDeque<usize> = VecDeque::new();

    // Process first element
    deque.push_back(0);

    // Process second element
    while let Some(&back) = deque.back() {
        if arr[back] <= arr[1] {
            deque.pop_back();
        } else {
            break;
        }
    }
    deque.push_back(1);

    // Process third element
    while let Some(&back) = deque.back() {
        if arr[back] <= arr[2] {
            deque.pop_back();
        } else {
            break;
        }
    }
    deque.push_back(2);

    // Remove indices out of window
    while let Some(&front) = deque.front() {
        if front <= 2 - k {
            deque.pop_front();
        } else {
            break;
        }
    }

    println!("{:?}", deque);
}

A [0, 2]

B [1, 2]

C [2]

D [2, 1]

💡 Hint

Remember the deque stores indices of elements in decreasing order of their values within the current window.

After processing first element: deque = [0] (value 2).
Second element 1 is less than 2, so deque = [0,1].
Third element 3 is greater than 1 and 2, so pop back twice, deque = []. Push 2 → [2].
Remove indices out of window (indices ≤ 0), none to remove.
Final deque = [2].

Practice

1. What is a deque in data structures?

easy

A. A double-ended queue allowing insertion and removal from both ends

B. A queue that only allows insertion at the front

C. A stack that only allows removal from the top

D. A list that only supports random access

Solution

1. Step 1: Understand the deque concept

   A deque is a data structure where elements can be added or removed from both the front and the back.

2. Step 2: Compare options with deque definition

   Only double-ended queue allowing insertion and removal from both ends correctly describes this behavior; others describe different structures.

3. Final Answer:

   A double-ended queue allowing insertion and removal from both ends -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

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

Common Mistakes:

• Confusing deque with stack or regular queue
• Thinking deque only allows insertion at one end
• Assuming deque is a fixed-size array

2. Which of the following is the correct way to create an empty VecDeque in Rust?

easy

A. let dq = VecDeque::empty();

B. let dq = VecDeque();

C. let dq = new VecDeque();

D. let dq = VecDeque::new();

Solution

1. Step 1: Recall Rust VecDeque creation syntax

   In Rust, the standard way to create an empty VecDeque is by calling VecDeque::new().

2. Step 2: Check each option for Rust syntax correctness

   let dq = VecDeque::new(); uses correct Rust syntax. The other options are invalid Rust syntax for VecDeque creation.

3. Final Answer:

   let dq = VecDeque::new(); -> Option D

4. Quick Check:

   VecDeque::new() creates empty deque [OK]

Hint: Use VecDeque::new() to create empty deque in Rust [OK]

Common Mistakes:

• Using constructor syntax like VecDeque() which is invalid in Rust
• Trying to call new as a method without ::
• Using non-existent empty() method

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

use std::collections::VecDeque;

fn main() {
    let mut dq = VecDeque::new();
    dq.push_back(10);
    dq.push_front(20);
    dq.push_back(30);
    dq.pop_front();
    println!("{:?}", dq);
}

medium

A. [10, 30]

B. [20, 10, 30]

C. [30, 10]

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, resulting in [10, 30]

2. Step 2: Confirm final deque state

   After all operations, the deque contains [10, 30].

3. Final Answer:

   [10, 30] -> Option A

4. Quick Check:

   After pop_front, deque = [10, 30] [OK]

Hint: Track push/pop order carefully front and back [OK]

Common Mistakes:

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

4. Identify the error in the following Rust code using VecDeque:

use std::collections::VecDeque;

fn main() {
    let mut dq = VecDeque::new();
    dq.push_front(5);
    dq.push_back(10);
    let x = dq.pop_back();
    println!("{}", x);
}

medium

A. pop_back() does not return a value

B. Cannot print Option<i32> directly with {}

C. VecDeque does not have push_front method

D. dq must be immutable to pop elements

Solution

1. Step 1: Understand pop_back return type

   pop_back() returns an Option containing the popped value or None if empty.

2. Step 2: Check println! usage

   Using {} tries to print the Option<i32> directly, which causes a type mismatch error. {:?} or unwrap() is needed.

3. Final Answer:

   Cannot print Option<i32> directly with {} -> Option B

4. Quick Check:

   Option<i32> needs {:?} or unwrap() to print [OK]

Hint: Use {:?} or unwrap() to print Option values [OK]

Common Mistakes:

• Trying to print Option with {} instead of {:?}
• Assuming pop_back returns value directly, not Option
• Thinking VecDeque lacks push_front method

5. You want to implement a sliding window maximum using a VecDeque in Rust. Which approach correctly maintains the deque to always have the maximum at the front while sliding the window?

hard

A. Remove elements from front smaller than new element before pushing it to front

B. Always push new element to front without removing any elements

C. Remove elements from back smaller than new element before pushing it to back

D. Remove elements from back larger than new element before pushing it to back

Solution

1. Step 1: Understand sliding window max logic with deque

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

2. Step 2: Analyze options for correct deque maintenance

   Remove elements from back smaller than new element before pushing it to back correctly describes removing smaller elements from back before pushing new element to back. Others do not maintain max at front properly.

3. Final Answer:

   Remove elements from back smaller than new element before pushing it to back -> Option C

4. Quick Check:

   Sliding window max uses back removals of smaller elements [OK]

Hint: Pop smaller from back before push_back new max candidate [OK]

Common Mistakes:

• Removing from front instead of back
• Pushing new elements to front incorrectly
• Removing larger elements instead of smaller