class MyStack:

    def __init__(self):
        self.dq = deque()


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

    def pop(self) -> int:
        return self.dq.pop()

    def top(self) -> int:
        return self.dq[-1]

    def empty(self) -> bool:
        return False if len(self.dq) > 0 else True


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


###################################################################
 class MyQueue:
    '''
    Ý tưởng: Sử dụng 2 stack: main_stack lưu 1 phần tử duy nhất
    sub_stack lưu số phần tử còn lại
    Như vậy thì việc pop push, peek, empty trên main_stack sẽ là O(1)
    sub_stack thì lưu phần tử còn lại mỗi khi main_stack pop or main_stack thì lấy phần tử trong sub_stack và tăng biến đếm chỉ số của
    sub_stack
    '''
    def __init__(self):
        self.main_stack = []
        self.sub_stack = []
        self.idx_tail = 0

    def push(self, x: int) -> None:
        if len(self.main_stack) == 0 and len(self.sub_stack) == 0:
            self.main_stack.append(x)
        else:
            self.sub_stack.append(x)

    def pop(self) -> int:
        if len(self.main_stack) == 0 and len(self.sub_stack) == 0:
            return -1
        if len(self.main_stack) == 0 and len(self.sub_stack) > 0:
            if  self.idx_tail >= len(self.sub_stack):
                return -1

            self.main_stack.append(self.sub_stack[self.idx_tail])
            self.idx_tail += 1

        return self.main_stack.pop()

    def peek(self) -> int:
        if len(self.main_stack) > 0 :
            return self.main_stack[-1]
        else:
            return self.sub_stack[self.idx_tail]

    def empty(self) -> bool:
        return len(self.main_stack) == 0 and self.idx_tail > len(self.sub_stack) - 1


# 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()
########################################################################