Implement Stack Using Queue in DSA Rust

Mental Model

A stack works like a pile where you add and remove from the top. A queue works like a line where you add at the end and remove from the front. We use a queue to act like a stack by rearranging elements after each add.

Analogy: Imagine a line of people where the last person to join wants to be served first. After each new person joins, they move to the front of the line so they get served before others, mimicking a stack's top.

Queue: front -> [1, 2, 3] ← back
Stack: top -> 3 -> 2 -> 1 -> null

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop

Goal: Use a single queue to behave like a stack and show the top element after each operation

Step 1: Push 1: enqueue 1, then rotate queue to put 1 at front

Queue: [1] front -> 1 -> null

Why: First element is both front and top

Step 2: Push 2: enqueue 2, then rotate queue to put 2 at front

Queue: [2, 1] front -> 2 -> 1 -> null

Why: New element 2 moves to front to act as top

Step 3: Push 3: enqueue 3, then rotate queue to put 3 at front

Queue: [3, 2, 1] front -> 3 -> 2 -> 1 -> null

Why: New element 3 moves to front to act as top

Step 4: Pop: dequeue front element (3)

Queue: [2, 1] front -> 2 -> 1 -> null

Why: Removing top element 3 from stack

Result:

Queue after pop: front -> 2 -> 1 -> null
Popped element: 3

Annotated Code

DSA Rust

use std::collections::VecDeque;

struct MyStack {
    queue: VecDeque<i32>,
}

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

    fn push(&mut self, x: i32) {
        self.queue.push_back(x); // add new element at back
        let size = self.queue.len();
        // rotate queue to move new element to front
        for _ in 0..size - 1 {
            if let Some(front) = self.queue.pop_front() {
                self.queue.push_back(front); // move front to back
            }
        }
    }

    fn pop(&mut self) -> Option<i32> {
        self.queue.pop_front() // remove front element which is top
    }

    fn top(&self) -> Option<i32> {
        self.queue.front().copied() // peek front element
    }

    fn empty(&self) -> bool {
        self.queue.is_empty()
    }
}

fn main() {
    let mut stack = MyStack::new();
    stack.push(1);
    println!("Top after push 1: {}", stack.top().unwrap());
    stack.push(2);
    println!("Top after push 2: {}", stack.top().unwrap());
    stack.push(3);
    println!("Top after push 3: {}", stack.top().unwrap());
    let popped = stack.pop().unwrap();
    println!("Popped element: {}", popped);
    println!("Top after pop: {}", stack.top().unwrap());
}

self.queue.push_back(x); // add new element at back

enqueue new element at queue's back

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

rotate queue to move new element to front, simulating stack top

self.queue.pop_front() // remove front element which is top

pop top element by dequeuing front

self.queue.front().copied() // peek front element

peek top element at front of queue

Output

Top after push 1: 1

Top after push 2: 2

Top after push 3: 3

Popped element: 3

Top after pop: 2

Complexity Analysis

Time: O(n) for push because we rotate all elements to move new element to front; O(1) for pop and top as they access front directly

Space: O(n) because we store all elements in the queue

vs Alternative: Using two queues can also implement stack but requires more space and operations; single queue with rotation is simpler but push is costlier

Edge Cases

Pop or top on empty stack

Returns None safely without crashing

DSA Rust

self.queue.pop_front() // pop returns Option, handles empty queue

Push single element

Element becomes front and top immediately

DSA Rust

for _ in 0..size - 1 { ... } // loop skips if size is 1

When to Use This Pattern

When you see a problem asking to implement a stack but only queues are allowed, reach for the queue rotation pattern to simulate stack behavior.

Common Mistakes

Mistake: Not rotating the queue after push, so the newest element is not at front
Fix: Rotate the queue by dequeuing and enqueuing elements size-1 times after each push

Mistake: Using pop_back instead of pop_front for pop operation
Fix: Always pop from front because rotation puts top element at front

Summary

Implements a stack using a single queue by rotating elements after each push.

Use when only queue operations are allowed but stack behavior is needed.

The key is to rotate the queue so the newest element is always at the front, acting as the stack top.

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