Implement Queue using Stacks

Problem: Implement Queue using Stacks

I use a dumb way to solve this problem, but I recommend a smart solution with 2 stacks here. The smart solution mainly use an extra stack to store leading elements so that we can return fast if consecutive pop function are called.

Code in Python:

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.head = None


    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        if not self.stack: self.head = x
        self.stack.append(x)


    def pop(self):
        """
        :rtype: nothing
        """
        cache = []
        if len(self.stack) == 1:
            self.head = None
            return self.stack.pop()
        while len(self.stack) > 1:
            self.head = self.stack.pop()
            cache.append(self.head)
        ans = self.stack.pop()
        self.stack = cache[::-1]
        return ans


    def peek(self):
        """
        :rtype: int
        """
        return self.head


    def empty(self):
        """
        :rtype: bool
        """
        if not self.stack: return True
        return False