# class MyStack:

#     def __init__(self):

#         #deque是双端队列，左侧是先进的，popleft就是先入先出，pop就是后入先出

#         self.que = deque()

#     def push(self, x):

#         self.que.append(x)

#     def pop(self):

#         if self.empty():

#             return None

#         #把前len(self.que)-1的数据都加到后面去，露出最后一个数据再弹出

#         for i in range(len(self.que)-1):

#             self.que.append(self.que.popleft())

#         return self.que.popleft()

#     #top就是获取最前面的数据但是不能弹除

#     def top(self):

#         # 写法一：

#         # if self.empty():

#         #     return None

#         # return self.que[-1]

#         # 写法二：

#         if self.empty():

#             return None

#         for i in range(len(self.que)-1):

#             self.que.append(self.que.popleft())

#         temp = self.que.popleft()

#         self.que.append(temp)

#         return temp

#     def empty(self):

#         return not self.que      

#方法一：使用单个队列

# class MyStack:

#     def __init__(self):

#         self.deq=deque()

#     def push(self,x):

#         self.deq.append(x)

#     def pop(self):

#         if self.empty():

#             return False

#         else:

#             for i in range(len(self.deq)-1):

#                 self.deq.append(self.deq.popleft())

#             return self.deq.popleft()

#     def top(self):

#         if self.empty():

#             return False

#         else:

#             for i in range(len(self.deq)-1):

#                 self.deq.append(self.deq.popleft())

#             temp=self.deq.popleft()

#             self.deq.append(temp)

#             return temp

#     def empty(self):

#         return not self.deq

       

#方法二：使用双队列  这种方法与第一种方法大同小异，都是把前len(deq)-1给存下来，一个是用自己存，另一个是用第二个队列存

from collections import deque

class MyStack:

    def __init__(self):

        # Python普通的Queue或SimpleQueue没有类似于peek的功能

        # 也无法用索引访问，在实现top的时候较为困难。

        # 用list可以，但是在使用pop(0)的时候时间复杂度为O(n)

        # 因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能

        # in - 存所有数据

        # out - 仅在pop的时候会用到

        self.queue_in = deque()

        self.queue_out = deque()

    def push(self, x):

        # 直接append即可

        self.queue_in.append(x)

    def pop(self):

        # 1. 首先确认不空

        # 2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out

        # 3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out

        # 4. 交换in和out，此时out里只有一个元素

        # 5. 把out中的pop出来，即是原队列的最后一个

       

        # tip：这不能像栈实现队列一样，因为另一个queue也是FIFO，如果执行pop()它不能像

        # stack一样从另一个pop()，所以干脆in只用来存数据，pop()的时候两个进行交换

        if self.empty():

            return None

        for i in range(len(self.queue_in) - 1):

            self.queue_out.append(self.queue_in.popleft())      

        self.queue_in, self.queue_out = self.queue_out, self.queue_in    # 交换in和out，这也是为啥in只用来存

        return self.queue_out.popleft()

    def top(self):

        # 写法一：

        # 1. 首先确认不空

        # 2. 我们仅有in会存放数据，所以返回第一个即可（这里实际上用到了栈）

        # 写法二：

        # 1. 首先确认不空

        # 2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out

        # 3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out

        # 4. 交换in和out，此时out里只有一个元素

        # 5. 把out中的pop出来，即是原队列的最后一个，并使用temp变量暂存

        # 6. 把temp追加到queue_in的末尾

        # 写法一：

        # if self.empty():

        #     return None    

        # return self.queue_in[-1]    # 这里实际上用到了栈，因为直接获取了queue_in的末尾元素

        # 写法二：

        if self.empty():

            return None

        for i in range(len(self.queue_in) - 1):

            self.queue_out.append(self.queue_in.popleft())

        self.queue_in, self.queue_out = self.queue_out, self.queue_in

        temp = self.queue_out.popleft()  

        self.queue_in.append(temp)

        return temp

    def empty(self):

        #因为只有in存了数据，只要判断in是不是有数即可

        return len(self.queue_in) == 0