from functools import wraps
from multiprocessing import Lock

def synchronized(tlockname):
    """A decorator to place an instance based lock around a method """

    def _synched(func):
        @wraps(func)
        def _synchronizer(self, *args, **kwargs):
            tlock = self.__getattribute__(tlockname)
            tlock.acquire()
            try:
                return func(self, *args, **kwargs)
            finally:
                tlock.release()

        return _synchronizer

    return _synched

class MyStack:
    def __init__(self):
        self.queue1 = []
        self.queue2 = []
        self.queue = self.queue1

        self._lock = Lock()

    @synchronized('_lock')
    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.queue.append(x)

    @synchronized('_lock')
    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        current_queue, tobe_queue = (self.queue1, self.queue2) if self.queue == self.queue1 else (self.queue2, self.queue1)

        while len(current_queue) > 1:
            x = current_queue.pop(0)
            tobe_queue.append(x)

        ret = current_queue.pop(0)
        self.queue = tobe_queue
        return ret

    @synchronized('_lock')
    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        current_queue, tobe_queue = (self.queue1, self.queue2) if self.queue == self.queue1 else (self.queue2, self.queue1)

        while len(current_queue) > 1:
            x = current_queue.pop(0)
            tobe_queue.append(x)

        ret = current_queue.pop(0)
        tobe_queue.append(ret)
        self.queue = tobe_queue
        return ret

    @synchronized('_lock')
    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return len(self.queue) == 0