Dequeue Operation in DSA Rust

Mental Model

A dequeue lets you add or remove items from both ends easily. It works like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway where people can enter or exit from either the front door or the back door without waiting.

front -> [1] -> [2] -> [3] -> back
↑front pointer
                      ↑back pointer

Dry Run Walkthrough

Input: dequeue with elements 1 -> 2 -> 3, perform remove_front, then remove_back

Goal: Remove one element from the front and one from the back, showing how the dequeue shrinks from both ends

Step 1: remove_front removes element 1 from the front

front -> [2] -> [3] -> back
↑front pointer
              ↑back pointer

Why: Removing from front updates front pointer to next element

Step 2: remove_back removes element 3 from the back

front -> [2] -> back
↑front pointer
        ↑back pointer

Why: Removing from back updates back pointer to previous element

Result:

front -> [2] -> back
↑front pointer
        ↑back pointer

Annotated Code

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut dequeue: VecDeque<i32> = VecDeque::new();
    dequeue.push_back(1);
    dequeue.push_back(2);
    dequeue.push_back(3);

    // Remove from front
    let front_removed = dequeue.pop_front();
    println!("Removed from front: {:?}", front_removed);
    print_dequeue(&dequeue);

    // Remove from back
    let back_removed = dequeue.pop_back();
    println!("Removed from back: {:?}", back_removed);
    print_dequeue(&dequeue);
}

fn print_dequeue(deq: &VecDeque<i32>) {
    if deq.is_empty() {
        println!("empty");
        return;
    }
    let mut s = String::new();
    for &item in deq {
        s.push_str(&format!("{} -> ", item));
    }
    s.push_str("null");
    println!("{}", s);
}

let front_removed = dequeue.pop_front();

remove element from front and update front pointer

print_dequeue(&dequeue);

show current dequeue state after front removal

let back_removed = dequeue.pop_back();

remove element from back and update back pointer

print_dequeue(&dequeue);

show current dequeue state after back removal

Output

Removed from front: Some(1)

2 -> 3 -> null

Removed from back: Some(3)

2 -> null

Complexity Analysis

Time: O(1) because removing from front or back just moves pointers without shifting elements

Space: O(n) where n is number of elements stored, as space grows with elements

vs Alternative: Compared to a normal queue or stack, dequeue allows removal from both ends in constant time, making it more flexible

Edge Cases

empty dequeue

pop_front or pop_back returns None without error

DSA Rust

let front_removed = dequeue.pop_front();

single element dequeue

removing front or back empties the dequeue correctly

DSA Rust

let back_removed = dequeue.pop_back();

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, use a dequeue operation because it supports O(1) insertions and deletions at both front and back.

Common Mistakes

Mistake: Trying to remove from an empty dequeue without checking causes errors or panics.
Fix: Use pop_front or pop_back which safely return None if empty.

Summary

It removes elements from either the front or back of a dequeue.

Use it when you need fast removal from both ends of a list.

The key is that pointers move inward without shifting all elements.

Practice

1. What does the pop_front() operation do in a dequeue?

easy

A. Removes and returns the element at the front of the dequeue

B. Removes and returns the element at the back of the dequeue

C. Adds an element to the front of the dequeue

D. Adds an element to the back of the dequeue

Solution

1. Step 1: Understand pop_front() operation

   The pop_front() removes the first element from the front of the dequeue.

2. Step 2: Compare with other operations

   Unlike pop_back() which removes from the back, pop_front() targets the front element.

3. Final Answer:

   Removes and returns the element at the front of the dequeue -> Option A

4. Quick Check:

   pop_front() = remove front element [OK]

Hint: pop_front() always removes from the front [OK]

Common Mistakes:

• Confusing pop_front() with pop_back()
• Thinking pop_front() adds elements
• Mixing push and pop operations

2. Which of the following is the correct Rust syntax to remove an element from the back of a VecDeque named dq?

easy

A. dq.pop_front();

B. dq.pop_back();

C. dq.remove_back();

D. dq.pop();

Solution

1. Step 1: Identify VecDeque method for back removal

   The correct method to remove from the back is pop_back().

2. Step 2: Check other options

   pop_front() removes from front, remove_back() and pop() are invalid methods for VecDeque.

3. Final Answer:

   dq.pop_back(); -> Option B

4. Quick Check:

   pop_back() removes back element [OK]

Hint: Use pop_back() to remove from back in VecDeque [OK]

Common Mistakes:

• Using pop() which is for Vec, not VecDeque
• Using remove_back() which does not exist
• Confusing pop_front() with pop_back()

3. What is the output of the following Rust code?

use std::collections::VecDeque;

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

medium

A. [5, 10, 20]

B. [1, 10, 20]

C. [10, 20, 1]

D. [1, 5, 10]

Solution

1. Step 1: Trace push_back and push_front calls

   After push_back(10) and push_back(20), dq = [10, 20]. Then push_front(5) makes dq = [5, 10, 20].

2. Step 2: Apply pop_back and push_front

   pop_back() removes 20, dq = [5, 10]. Then push_front(1) makes dq = [1, 5, 10].

3. Final Answer:

   [1, 5, 10] -> Option D

4. Quick Check:

   Operations result in [1, 5, 10] [OK]

Hint: Track each operation step-by-step on the deque [OK]

Common Mistakes:

• Forgetting pop_back removes last element
• Mixing order of push_front and push_back
• Misreading the final print format

4. Identify the error in this Rust code that tries to remove an element from the front of a VecDeque named dq:

use std::collections::VecDeque;

fn main() {
    let mut dq = VecDeque::new();
    dq.push_back(1);
    dq.push_back(2);
    let front = dq.pop();
    println!("{:?}", front);
}

medium

A. VecDeque has no method named pop()

B. pop() removes from back, not front

C. dq is not mutable

D. push_back() is used incorrectly

Solution

1. Step 1: Check VecDeque methods

   VecDeque does not have a method named pop(). It uses pop_front() or pop_back().

2. Step 2: Identify the error cause

   Calling dq.pop() causes a compile-time error because the method does not exist.

3. Final Answer:

   VecDeque has no method named pop() -> Option A

4. Quick Check:

   pop() method missing in VecDeque [OK]

Hint: Use pop_front() or pop_back() for VecDeque removals [OK]

Common Mistakes:

• Using pop() from Vec on VecDeque
• Ignoring compiler error messages
• Assuming pop() removes front element

5. Given a VecDeque with elements [3, 6, 9, 12], which sequence of operations will result in the dequeue [1, 3, 6]?

hard

A. dq.pop_back(); dq.pop_front(); dq.push_front(1);

B. dq.pop_front(); dq.pop_back(); dq.push_front(1);

C. dq.pop_back(); dq.pop_back(); dq.push_front(1);

D. dq.pop_front(); dq.pop_front(); dq.push_back(1);

Solution

1. Step 1: Start with dq = [3, 6, 9, 12]

   Initial dequeue has elements 3, 6, 9, 12 in order.

2. Step 2: Apply operations in dq.pop_back(); dq.pop_back(); dq.push_front(1);

   First pop_back() removes 12, dq = [3, 6, 9]. Second pop_back() removes 9, dq = [3, 6]. Then push_front(1) adds 1 at front, dq = [1, 3, 6].

3. Final Answer:

   dq.pop_back(); dq.pop_back(); dq.push_front(1); -> Option C

4. Quick Check:

   Operations produce [1, 3, 6] [OK]

Hint: Remove from back twice, then add 1 at front [OK]

Common Mistakes:

• Removing from front instead of back
• Adding 1 at back instead of front
• Wrong operation order