Implement Stack Using Queue in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack Implemented Using One Queue

What is the printed output of the following Rust code that implements a stack using a single queue after performing push and pop operations?

DSA Rust

use std::collections::VecDeque;

struct Stack {
    queue: VecDeque<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack { queue: VecDeque::new() }
    }

    fn push(&mut self, x: i32) {
        self.queue.push_back(x);
        let size = self.queue.len();
        for _ in 0..size - 1 {
            if let Some(val) = self.queue.pop_front() {
                self.queue.push_back(val);
            }
        }
    }

    fn pop(&mut self) -> Option<i32> {
        self.queue.pop_front()
    }

    fn print_stack(&self) {
        for val in &self.queue {
            print!("{} -> ", val);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.print_stack();
    stack.pop();
    stack.print_stack();
}

A

10 -> 20 -> 30 -> null
30 -> 20 -> null

B

10 -> 20 -> 30 -> null
20 -> 10 -> null

C

30 -> 20 -> 10 -> null
10 -> 20 -> null

D

30 -> 20 -> 10 -> null
20 -> 10 -> null

💡 Hint

Remember that push rotates the queue to keep the last pushed element at the front.

The stack is implemented using one queue by pushing the new element and then rotating the queue so that the new element is at the front. This makes pop() remove the most recently pushed element.

After pushing 10, 20, 30, the queue order is 30, 20, 10. Popping removes 30, leaving 20, 10.

❓ Predict Output

intermediate

Result of Multiple Push and Pop on Stack Using Two Queues

Given the Rust implementation of a stack using two queues, what is the output after the following operations?

DSA Rust

use std::collections::VecDeque;

struct Stack {
    q1: VecDeque<i32>,
    q2: VecDeque<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack {
            q1: VecDeque::new(),
            q2: VecDeque::new(),
        }
    }

    fn push(&mut self, x: i32) {
        self.q2.push_back(x);
        while let Some(val) = self.q1.pop_front() {
            self.q2.push_back(val);
        }
        std::mem::swap(&mut self.q1, &mut self.q2);
    }

    fn pop(&mut self) -> Option<i32> {
        self.q1.pop_front()
    }

    fn print_stack(&self) {
        for val in &self.q1 {
            print!("{} -> ", val);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(5);
    stack.push(15);
    stack.push(25);
    stack.print_stack();
    stack.pop();
    stack.print_stack();
    stack.push(35);
    stack.print_stack();
}

A

25 -> 15 -> 5 -> null
15 -> 5 -> null
35 -> 15 -> 5 -> null

B

5 -> 15 -> 25 -> null
15 -> 25 -> null
35 -> 15 -> 25 -> null

C

25 -> 15 -> 5 -> null
5 -> 15 -> null
35 -> 5 -> 15 -> null

D

5 -> 15 -> 25 -> null
25 -> 15 -> null
35 -> 25 -> 15 -> null

💡 Hint

The push operation moves all elements to the second queue and swaps queues to keep the newest element at front.

Push adds the new element to q2, then moves all elements from q1 to q2, then swaps q1 and q2. This keeps the newest element at the front of q1.

After pushing 5, 15, 25, q1 is [25, 15, 5]. Popping removes 25, leaving [15, 5]. Pushing 35 results in [35, 15, 5].

🔧 Debug

advanced

Identify the Error in Stack Push Method Using One Queue

The following Rust code tries to implement a stack using one queue. What error will occur when compiling or running this code?

DSA Rust

use std::collections::VecDeque;

struct Stack {
    queue: VecDeque<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack { queue: VecDeque::new() }
    }

    fn push(&mut self, x: i32) {
        self.queue.push_back(x);
        for i in 0..self.queue.len() {
            if let Some(val) = self.queue.pop_front() {
                self.queue.push_back(val);
            }
        }
    }

    fn pop(&mut self) -> Option<i32> {
        self.queue.pop_front()
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.pop();
}

A Infinite loop because queue length changes during iteration

B Compilation error: cannot borrow `self.queue` as mutable more than once

C No error, code runs correctly

D Runtime panic due to popping from empty queue

💡 Hint

Consider how the queue length changes inside the loop.

The loop uses the queue length as the upper bound, but the queue length changes inside the loop because elements are popped and pushed back. This causes the loop to never end, resulting in an infinite loop.

❓ Predict Output

advanced

Final Queue State After Sequence of Stack Operations Using Two Queues

What is the final printed state of the internal queue after executing the following Rust code implementing a stack with two queues?

DSA Rust

use std::collections::VecDeque;

struct Stack {
    q1: VecDeque<i32>,
    q2: VecDeque<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack {
            q1: VecDeque::new(),
            q2: VecDeque::new(),
        }
    }

    fn push(&mut self, x: i32) {
        self.q2.push_back(x);
        while let Some(val) = self.q1.pop_front() {
            self.q2.push_back(val);
        }
        std::mem::swap(&mut self.q1, &mut self.q2);
    }

    fn pop(&mut self) -> Option<i32> {
        self.q1.pop_front()
    }

    fn print_internal_queue(&self) {
        for val in &self.q1 {
            print!("{} -> ", val);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(100);
    stack.push(200);
    stack.pop();
    stack.push(300);
    stack.print_internal_queue();
}

A 100 -> 300 -> null

B 300 -> 100 -> null

C 200 -> 100 -> 300 -> null

D 300 -> 200 -> null

💡 Hint

Remember pop removes the front element, and push rearranges the queue.

After pushing 100 and 200, q1 is [200, 100]. Popping removes 200, leaving [100]. Pushing 300 moves 300 to front, then 100 behind, so q1 is [300, 100].

🧠 Conceptual

expert

Time Complexity of Stack Operations Using Queues

What is the time complexity of the push and pop operations in a stack implemented using two queues where push operation moves all elements from one queue to another?

A Push: O(1), Pop: O(1)

B Push: O(n), Pop: O(n)

C Push: O(n), Pop: O(1)

D Push: O(1), Pop: O(n)

💡 Hint

Consider which operation involves moving all elements between queues.

In this implementation, push inserts the new element into the empty queue and then moves all elements from the other queue to it, making push O(n). Pop simply removes from the front of the queue, which is O(1).

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one or two queues to simulate stack operations like push and pop

B. Use a queue to sort elements in ascending order

C. Use a stack to implement queue operations

D. Use two stacks to implement a queue

Solution

1. Step 1: Understand stack and queue operations

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue(s)

   By using one or two queues and carefully managing element order, we can mimic stack push and pop operations.

3. Final Answer:

   Use one or two queues to simulate stack operations like push and pop -> Option A

4. Quick Check:

   Stack via queue = simulate push/pop with queues [OK]

Hint: Remember stack is LIFO, queue is FIFO; simulate LIFO with queue(s) [OK]

Common Mistakes:

• Confusing stack and queue order
• Trying to sort elements instead of simulating stack
• Using stack to implement queue instead

2. Which Rust code snippet correctly declares a queue using VecDeque for implementing a stack?

easy

A. let mut queue = Vec::with_capacity(10);

B. let queue = Vec<i32>::new();

C. let mut queue: VecDeque<i32> = VecDeque::new();

D. let queue: VecDeque = Vec::new();

Solution

1. Step 1: Identify correct queue type in Rust

   VecDeque is the standard double-ended queue in Rust, suitable for queue operations.

2. Step 2: Check correct syntax for mutable queue declaration

   "let mut queue: VecDeque<i32> = VecDeque::new();" correctly declares a mutable queue of i32.

3. Final Answer:

   let mut queue: VecDeque<i32> = VecDeque::new(); -> Option C

4. Quick Check:

   VecDeque mutable queue declaration = let mut queue: VecDeque<i32> = VecDeque::new(); [OK]

Hint: Use VecDeque with mut keyword for queue in Rust [OK]

Common Mistakes:

• Using Vec instead of VecDeque for queue
• Missing mut keyword for mutable queue
• Wrong type annotations

3. Given this Rust code implementing push for stack using one queue, what is the queue state after pushing 1, then 2?

use std::collections::VecDeque;

struct Stack {
    queue: VecDeque<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack { queue: VecDeque::new() }
    }

    fn push(&mut self, x: i32) {
        self.queue.push_back(x);
        let size = self.queue.len();
        for _ in 0..size - 1 {
            if let Some(val) = self.queue.pop_front() {
                self.queue.push_back(val);
            }
        }
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    println!("{:?}", stack.queue);
}

medium

A. [2, 1]

B. [1, 2]

C. [1]

D. [2]

Solution

1. Step 1: Trace push(1) operation

   Push 1: queue = [1]. No rotation since size=1.

2. Step 2: Trace push(2) operation

   Push 2: queue = [1, 2]. Rotate size-1=1 times: pop_front 1, push_back 1 -> queue = [2, 1].

3. Final Answer:

   [2, 1] -> Option A

4. Quick Check:

   After push 1,2 queue = [2,1] [OK]

Hint: After push, rotate queue to front to simulate stack top [OK]

Common Mistakes:

• Not rotating queue after push
• Confusing push_back and pop_front order
• Assuming queue keeps insertion order

4. Identify the bug in this pop method for stack implemented using one queue:

fn pop(&mut self) -> Option<i32> {
    self.queue.pop_back()
}

medium

A. pop_back() is invalid for VecDeque

B. pop_back() removes from the wrong end; should use pop_front()

C. pop_back() is correct; no bug

D. pop_back() requires mutable borrow error

Solution

1. Step 1: Understand queue ends in VecDeque

   VecDeque supports pop_front() and pop_back(), but our stack top is at front after push rotation.

2. Step 2: Check which end holds stack top

   After push rotation, stack top is at front, so pop_front() removes top, not pop_back().

3. Final Answer:

   pop_back() removes from the wrong end; should use pop_front() -> Option B

4. Quick Check:

   Stack top at front, pop_front() needed [OK]

Hint: Pop from front after rotation to get stack top [OK]

Common Mistakes:

• Using pop_back() instead of pop_front()
• Not rotating queue after push
• Confusing queue ends

5. How would you implement the top method for a stack using a single queue in Rust, assuming push rotates the queue so the top is at the front?

hard

A. Return the last element using queue.back().cloned()

B. Remove and return the last element using queue.pop_back()

C. Remove and return the first element using queue.pop_front()

D. Return the element at the front of the queue without removing it using queue.front().cloned()

Solution

1. Step 1: Recall queue rotation after push

   After push, queue is rotated so top element is at front.

2. Step 2: Access top without removing

   Use queue.front().cloned() to get top element without popping.

3. Final Answer:

   Return the element at the front of the queue without removing it using queue.front().cloned() -> Option D

4. Quick Check:

   Top element at front, use front().cloned() [OK]

Hint: Top is front element after rotation; use front().cloned() [OK]

Common Mistakes:

• Using pop_front() which removes element
• Using back() which is bottom of stack
• Removing element instead of just viewing