Implement Stack Using Queue in DSA Rust - Build from Scratch

Implement Stack Using Queue

📖 Scenario: Imagine you are building a simple system that needs a stack to manage tasks, but you only have a queue available. You want to create a stack behavior (Last In First Out) using the queue operations (First In First Out).

🎯 Goal: Build a stack using a single queue in Rust. You will implement the push and pop operations of the stack using queue operations.

📋 What You'll Learn

Create a queue using VecDeque from Rust standard library

Implement push method to add an element to the stack

Implement pop method to remove the top element from the stack

Print the state of the queue after operations to show stack behavior

💡 Why This Matters

🌍 Real World

Sometimes, only certain data structures are available or efficient. Knowing how to build one data structure using another helps in constrained environments.

💼 Career

Understanding how to implement stacks and queues and their relationship is fundamental for software engineering roles, especially in system design and algorithm optimization.

1

Create the queue data structure

Create a mutable queue called queue using VecDeque<i32> and initialize it empty.

DSA Rust

use std::collections::VecDeque;

// Create a mutable queue called queue
// Your code here

Hint

Use VecDeque::new() to create an empty queue.

2

Add a helper variable for stack size

Add a mutable variable called size of type usize and initialize it to 0 to keep track of the stack size.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::new();
    // Add a mutable variable size initialized to 0
    // Your code here
}

Hint

This variable will help track how many elements are in the stack.

3

Implement push operation using the queue

Write code to push the integer 10 onto the stack by adding it to the queue and then rotating the queue elements to simulate stack behavior. Also, increase size by 1.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::new();
    let mut size: usize = 0;

    // Push 10 onto the stack using queue operations
    // Your code here
}

Hint

After adding the new element, move all previous elements behind it by popping from front and pushing to back.

4

Pop the top element and print the queue

Pop the top element from the stack by removing the front element from queue, decrease size by 1, and then print the remaining elements in queue separated by -> and ending with null.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::new();
    let mut size: usize = 0;

    queue.push_back(10);
    size += 1;

    for _ in 0..size-1 {
        if let Some(front) = queue.pop_front() {
            queue.push_back(front);
        }
    }

    // Pop the top element and print the queue
    // Your code here
}

Hint

After popping, print all elements in the queue separated by ' -> ' and end with 'null'. If empty, print 'null'.

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