LeetCode Entry

232. Implement Queue using Stacks

29.01.2024 easy 2024 kotlin rust

Queue by 2 stacks.

232. Implement Queue using Stacks easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/487

Problem TLDR

Queue by 2 stacks.

Intuition

Let’s write down how the numbers are added:

stack a: [1 2]
stack b: []

peek:

a: [1]
b: [2]

a: []
b: [2 1], b.peek == 1

Approach

Let’s do some code golf.

Complexity

• Time complexity: \(O(1)\) for total operations. In general, stack drain is a rare operation

• Space complexity: \(O(n)\) for total operations.

Code

class MyQueue() {
  val a = Stack<Int>()
  val b = Stack<Int>()
  fun push(x: Int) = a.push(x)
  fun pop() = peek().also { b.pop() }
  fun peek(): Int {
    if (b.size < 1) while (a.size > 0) b += a.pop()
    return b.peek()
  }
  fun empty() = a.size + b.size == 0
}

struct MyQueue(Vec<i32>, Vec<i32>);
impl MyQueue {
    fn new() -> Self { Self(vec![], vec![]) }
    fn push(&mut self, x: i32) { self.0.push(x); }
    fn pop(&mut self) -> i32 { self.peek(); self.1.pop().unwrap() }
    fn peek(&mut self) -> i32 {
      if self.1.is_empty() { self.1.extend(self.0.drain(..).rev()); }
      *self.1.last().unwrap()
    }
    fn empty(&self) -> bool { self.0.len() + self.1.len() == 0 }
}