unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 232: Implement Queue using Stacks

link

Queue preserves the write order. Stack reverses the write order. If we reverse write order twice, we get back the original order. So, we can pass the push()‘s through the two stacks (left and right) in sequence: \text{Write}_{\text{left}} \left[, \text{Read}_{\text{left}}, \text{Write}_{\text{right}} \right], \text{Read}_{\text{right}}. Here \text{Write}_{\text{left}} would be the push()and \text{Read}_{\text{right}} would be peek() or pop().

Amortized, each push(), peek(), pop() and empty() operation takes \mathcal{O}(1) time.

Time: \mathcal{O}(n), space: same.

class MyQueue:

    def __init__(self):
        # Write into left_stack
        self.left_stack = []
        # Read or remove from right_stack
        self.right_stack = []

    def push(self, x: int) -> None:
        self.left_stack.append(x)

    def replenish_reads(self) -> None:
        if self.right_stack:
            return
            
        while self.left_stack:
            self.right_stack.append( self.left_stack.pop() )

    def pop(self) -> int:
        self.replenish_reads()
        return self.right_stack.pop()

    def peek(self) -> int:
        self.replenish_reads()
        return self.right_stack[-1]

    def empty(self) -> bool:
        return not self.left_stack and not self.right_stack


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

tanvirdotzaman

,

Leave a comment