Queue Using Two Stacks in DSA Rust

Mental Model

Use two stacks to make a queue by reversing order twice so first-in is first-out.

Analogy: Imagine two trays of plates: you put plates on the first tray, then flip them onto the second tray to serve in the order they arrived.

stack_in: top -> [ ]
stack_out: top -> [ ]

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, dequeue, enqueue 3, dequeue

Goal: Simulate queue operations using two stacks to get correct FIFO order

Step 1: enqueue 1: push 1 onto stack_in

stack_in: top -> [1]
stack_out: top -> [ ]

Why: New elements go to stack_in to keep insertion order

Step 2: enqueue 2: push 2 onto stack_in

stack_in: top -> [2, 1]
stack_out: top -> [ ]

Why: Keep adding new elements on top of stack_in

Step 3: dequeue: stack_out empty, move all from stack_in to stack_out reversing order

stack_in: top -> [ ]
stack_out: top -> [1, 2]

Why: Reversing stack_in to stack_out makes oldest element on top for dequeue

Step 4: dequeue: pop from stack_out (1)

stack_in: top -> [ ]
stack_out: top -> [2]

Why: Pop oldest element from stack_out to simulate queue dequeue

Step 5: enqueue 3: push 3 onto stack_in

stack_in: top -> [3]
stack_out: top -> [2]

Why: New elements always go to stack_in

Step 6: dequeue: pop from stack_out (2)

stack_in: top -> [3]
stack_out: top -> [ ]

Why: stack_out not empty, pop directly to dequeue

Result:

stack_in: top -> [3]
stack_out: top -> [ ]
Dequeued elements in order: 1, 2

Annotated Code

DSA Rust

use std::vec::Vec;

struct QueueUsingTwoStacks<T> {
    stack_in: Vec<T>,
    stack_out: Vec<T>,
}

impl<T> QueueUsingTwoStacks<T> {
    fn new() -> Self {
        Self {
            stack_in: Vec::new(),
            stack_out: Vec::new(),
        }
    }

    fn enqueue(&mut self, value: T) {
        // push new element onto stack_in
        self.stack_in.push(value);
    }

    fn dequeue(&mut self) -> Option<T> {
        // if stack_out empty, move all from stack_in to stack_out reversing order
        if self.stack_out.is_empty() {
            while let Some(val) = self.stack_in.pop() {
                self.stack_out.push(val);
            }
        }
        // pop from stack_out to dequeue
        self.stack_out.pop()
    }

    fn print_state(&self) {
        // print stack_in top to bottom
        print!("stack_in: top -> [");
        for (i, val) in self.stack_in.iter().rev().enumerate() {
            if i > 0 { print!(", "); }
            print!("{}", val);
        }
        println!("]");

        // print stack_out top to bottom
        print!("stack_out: top -> [");
        for (i, val) in self.stack_out.iter().rev().enumerate() {
            if i > 0 { print!(", "); }
            print!("{}", val);
        }
        println!("]");
    }
}

fn main() {
    let mut queue = QueueUsingTwoStacks::new();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.print_state();

    if let Some(val) = queue.dequeue() {
        println!("Dequeued: {}", val);
    }
    queue.print_state();

    queue.enqueue(3);
    queue.print_state();

    if let Some(val) = queue.dequeue() {
        println!("Dequeued: {}", val);
    }
    queue.print_state();
}

self.stack_in.push(value);

push new element onto stack_in to keep insertion order

if self.stack_out.is_empty() { while let Some(val) = self.stack_in.pop() { self.stack_out.push(val); } }

if stack_out empty, move all from stack_in to stack_out reversing order to get oldest element on top

self.stack_out.pop()

pop from stack_out to dequeue the oldest element

Output

stack_in: top -> [2, 1]

stack_out: top -> []

Dequeued: 1

stack_in: top -> []

stack_out: top -> [2]

stack_in: top -> [3]

stack_out: top -> [2]

Dequeued: 2

stack_in: top -> [3]

stack_out: top -> []

Complexity Analysis

Time: O(1) amortized per operation because each element moves between stacks at most twice

Space: O(n) because all elements are stored in the two stacks combined

vs Alternative: Compared to a linked list queue with O(1) enqueue and dequeue, this uses two stacks but still achieves amortized O(1) dequeue by reversing order only when needed

Edge Cases

dequeue from empty queue

returns None safely without error

DSA Rust

self.stack_out.pop()

enqueue then dequeue single element

element is returned correctly

DSA Rust

if self.stack_out.is_empty() { while let Some(val) = self.stack_in.pop() { self.stack_out.push(val); } }

multiple enqueues before any dequeue

all elements are stored in stack_in until first dequeue triggers transfer

DSA Rust

if self.stack_out.is_empty() { while let Some(val) = self.stack_in.pop() { self.stack_out.push(val); } }

When to Use This Pattern

When you need a queue but only have stack operations, use two stacks to reverse order twice and simulate FIFO behavior.

Common Mistakes

Mistake: Trying to dequeue directly from stack_in without transferring to stack_out
Fix: Always transfer all elements from stack_in to stack_out if stack_out is empty before dequeue

Mistake: Transferring elements from stack_in to stack_out on every dequeue
Fix: Only transfer when stack_out is empty to keep amortized O(1) complexity

Summary

Implements a queue using two stacks by reversing element order twice.

Use when you want queue behavior but only have stack operations available.

The key insight is that reversing twice restores the original order for FIFO.

Practice

1. What is the main idea behind implementing a Queue Using Two Stacks?

easy

A. Use one stack for enqueue and another for dequeue operations

B. Use two stacks to perform only enqueue operations

C. Use two stacks to store elements in sorted order

D. Use two stacks to reverse the order twice to maintain queue order

Solution

1. Step 1: Understand queue order

   A queue follows First-In-First-Out (FIFO) order, meaning the first element added is the first removed.

2. Step 2: Use two stacks to reverse order twice

   One stack reverses the order when pushing elements, and the second stack reverses it back when popping, preserving FIFO.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain queue order -> Option D

4. Quick Check:

   Two stacks reverse order twice = queue order [OK]

Hint: Two stacks reverse order twice to simulate queue [OK]

Common Mistakes:

• Thinking both stacks store elements in sorted order
• Using stacks only for enqueue or dequeue
• Confusing stack order with queue order

2. Which of the following Rust code snippets correctly declares two stacks for implementing a queue?

easy

A. let mut stack1: Vec<i32> = Vec::new(); let mut stack2: Vec<i32> = Vec::new();

B. let stack1 = Vec<i32>; let stack2 = Vec<i32>;

C. let mut stack1 = Vec::new<i32>(); let mut stack2 = Vec::new<i32>();

D. let stack1: Vec = Vec::new(); let stack2: Vec = Vec::new();

Solution

1. Step 1: Check correct Vec declaration syntax in Rust

   In Rust, to declare a mutable vector of i32, use: let mut stack: Vec<i32> = Vec::new();

2. Step 2: Compare options with correct syntax

   let mut stack1: Vec<i32> = Vec::new(); let mut stack2: Vec<i32> = Vec::new(); matches the correct syntax exactly; others have syntax errors or missing mutability.

3. Final Answer:

   let mut stack1: Vec<i32> = Vec::new(); let mut stack2: Vec<i32> = Vec::new(); -> Option A

4. Quick Check:

   Correct Rust Vec declaration = let mut stack1: Vec<i32> = Vec::new(); let mut stack2: Vec<i32> = Vec::new(); [OK]

Hint: Use let mut stack: Vec<i32> = Vec::new() for mutable stacks [OK]

Common Mistakes:

• Omitting mut keyword for mutable vectors
• Incorrect generic syntax like Vec<i32> without parentheses
• Using Vec::new<i32>() which is invalid

3. What will be the output of the following Rust code implementing a queue using two stacks?

struct Queue {
    stack1: Vec<i32>,
    stack2: Vec<i32>,
}

impl Queue {
    fn new() -> Self {
        Queue { stack1: Vec::new(), stack2: Vec::new() }
    }

    fn enqueue(&mut self, val: i32) {
        self.stack1.push(val);
    }

    fn dequeue(&mut self) -> Option<i32> {
        if self.stack2.is_empty() {
            while let Some(x) = self.stack1.pop() {
                self.stack2.push(x);
            }
        }
        self.stack2.pop()
    }
}

fn main() {
    let mut q = Queue::new();
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    println!("{:?}", q.dequeue());
    println!("{:?}", q.dequeue());
    q.enqueue(40);
    println!("{:?}", q.dequeue());
    println!("{:?}", q.dequeue());
}

medium

A. Some(10) Some(20) Some(30) Some(40)

B. Some(30) Some(20) Some(10) Some(40)

C. Some(10) Some(20) Some(40) None

D. None None None None

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10, 20, 30 pushes these onto stack1 in order: [10, 20, 30]

2. Step 2: Trace dequeue operations

   First dequeue: stack2 empty, pop all from stack1 to stack2: stack2 = [30, 20, 10]. Pop from stack2 returns 10.
   Second dequeue: pop from stack2 returns 20.
   Enqueue 40: push 40 to stack1.
   Third dequeue: pop from stack2 returns 30.
   Fourth dequeue: stack2 empty, move 40 from stack1 to stack2, pop returns 40.

3. Final Answer:

   Some(10) Some(20) Some(30) Some(40) -> Option A

4. Quick Check:

   Queue order preserved by two stacks = Some(10) Some(20) Some(30) Some(40) [OK]

Hint: Dequeue empties stack2 by reversing stack1 first [OK]

Common Mistakes:

• Assuming stack2 pops in same order as stack1
• Not moving elements from stack1 to stack2 when stack2 is empty
• Confusing order of elements after transfer

4. Identify the bug in this Rust code snippet for dequeue operation in a queue using two stacks:

fn dequeue(&mut self) -> Option<i32> {
    while let Some(x) = self.stack1.pop() {
        self.stack2.push(x);
    }
    self.stack2.pop()
}

medium

A. It uses pop() on stack1 instead of peek()

B. It moves elements from stack1 to stack2 every time, even if stack2 is not empty

C. It does not pop from stack2 after moving elements

D. It returns None always because stack2 is never filled

Solution

1. Step 1: Analyze the dequeue logic

   The code moves all elements from stack1 to stack2 every dequeue call, regardless of stack2's state.

2. Step 2: Identify correct behavior

   To maintain queue order efficiently, elements should be moved only if stack2 is empty. Otherwise, stack2's elements should be popped directly.

3. Final Answer:

   It moves elements from stack1 to stack2 every time, even if stack2 is not empty -> Option B

4. Quick Check:

   Move only if stack2 empty = It moves elements from stack1 to stack2 every time, even if stack2 is not empty [OK]

Hint: Move elements only if stack2 is empty during dequeue [OK]

Common Mistakes:

• Moving elements every dequeue wastes time
• Ignoring stack2's current elements
• Not popping from stack2 after transfer

5. You want to implement a peek function for the queue using two stacks in Rust that returns the front element without removing it. Which approach correctly achieves this?

hard

A. Return the first element of stack1 without any stack transfers

B. Return the last element of stack1 directly without moving elements

C. If stack2 is empty, move all elements from stack1 to stack2, then return the last element of stack2 without popping

D. Pop an element from stack2 and push it back immediately to peek

Solution

1. Step 1: Understand peek operation in queue using two stacks

   Peek should return the front element without removing it. The front is at the bottom of stack1 or top of stack2 after transfer.

2. Step 2: Correct approach for peek

   If stack2 is empty, move all elements from stack1 to stack2 to reverse order. Then peek the last element of stack2 (top) without popping.

3. Final Answer:

   If stack2 is empty, move all elements from stack1 to stack2, then return the last element of stack2 without popping -> Option C

4. Quick Check:

   Peek uses stack2 top after transfer if empty = If stack2 is empty, move all elements from stack1 to stack2, then return the last element of stack2 without popping [OK]

Hint: Peek top of stack2 after transfer if empty [OK]

Common Mistakes:

• Peeking stack1 directly ignores queue order
• Popping to peek then pushing back wastes time
• Ignoring stack2 state before peeking