Implement Stack using Queues

Problem: Implement Stack using Queues

While implementing stack using queues, the difficulties lies in access or pop the last added element. We can use an extra queue to store all elements before it by dequeue and enqueue.

In my solution, I add an extra last element property so that function top can run faster than pop function.

Code in Python:

from collections import deque

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.queue = deque([])
        self.last = None


    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.queue.append(x)
        self.last = x


    def pop(self):
        """
        :rtype: nothing
        """
        buf = deque([])
        tmp = self.queue.popleft()
        while self.queue:
            buf.append(tmp)
            self.last = tmp
            tmp = self.queue.popleft()
        self.queue = buf


    def top(self):
        """
        :rtype: int
        """
        return self.last


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