Using Stacks

Classic Question: Implement a FIFO Queue using only two LIFO Stacks.

Since a Stack reverses order (1, 2, 3 → 3, 2, 1), using two stacks reverses the order twice, bringing it back to normal (1, 2, 3 → 3, 2, 1 → 1, 2, 3).

1. Input Stack (s1): Handles all enqueue operations.
2. Output Stack (s2): Handles all dequeue operations.
3. Logic:
   • Push to s1.
   • When asked to pop:
     • If s2 is NOT empty, pop from s2.
     • If s2 IS empty, pour everything from s1 into s2. (This reverses the order). Then pop from s2.

Implementation

class MyQueue:
    def __init__(self):
        self.s1 = []  # Input
        self.s2 = []  # Output
 
    def push(self, x: int) -> None:
        self.s1.append(x)
 
    def pop(self) -> int:
        self.move_input_to_output()
        return self.s2.pop()
 
    def peek(self) -> int:
        self.move_input_to_output()
        return self.s2[-1]
 
    def empty(self) -> bool:
        return not self.s1 and not self.s2
 
    def move_input_to_output(self):
        # Only move if Output stack is empty!
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())

pub struct QueueUsingStacks<T> {
    s1: Vec<T>, // Input
    s2: Vec<T>, // Output
}
 
impl<T> QueueUsingStacks<T> {
    pub fn new() -> Self {
        Self {
            s1: Vec::new(),
            s2: Vec::new(),
        }
    }
 
    pub fn push(&mut self, x: T) {
        self.s1.push(x);
    }
 
    pub fn pop(&mut self) -> Option<T> {
        self.move_input_to_output();
        self.s2.pop()
    }
 
    pub fn peek(&mut self) -> Option<&T> {
        self.move_input_to_output();
        self.s2.last()
    }
 
    pub fn empty(&self) -> bool {
        self.s1.is_empty() && self.s2.is_empty()
    }
 
    // Helper to transfer elements
    fn move_input_to_output(&mut self) {
        if self.s2.is_empty() {
            while let Some(val) = self.s1.pop() {
                self.s2.push(val);
            }
        }
    }
}