Stacks

Stacks

Implement Queue from Stacks

class MyQueue(object):

    def __init__(self):
        self.stack_1 = []
        self.stack_2 = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack_1.append(x)

    def pop(self):
        """
        :rtype: int
        """
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        popped_value = self.stack_2.pop()
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())
        return popped_value

    def peek(self):
        """
        :rtype: int
        """
        return self.stack_1[0]

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.stack_1) == 0

• Key insight: Pop elements from stack 1 over to stack 1, pop the top of stack 2 to get our queue pop behavior, then bring everything from stack 2 back to stack 1.