【第五天 - Queue 题目分析】

先简单回顾一下，今天预计分析的题目：

如何利用两个 stack 完成 Queue 的概念?
逻辑很简单，如下：
1. 先准备两个 stack 的盒子 ( 下方封死，只能由上方放入和取出 )
2. 假设有三个马克杯，分别为小明、小美、小雅，依序放入 stack 1，当你要根据 Queue 也就是先进先出的顺序，拿出最早放入的杯子(小明的杯子)，此时，把stack 1 内的杯子逐一放到 stack 2，他就会从上到下依照小明→小美→小雅的顺序排放，接着再拿 stack 2 的杯子，就会得到小明的杯子了
在 python 的程序中，就会这样实作几个 function

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
#       分别宣告两个 stack，命名为 stack1 与 stack2
#       stack1 放存进来的值
#       stack2 是把 stack1 的值逐一放入stack2，变成 Queue 的形式(最早放的会在最上面)
        self.stack1 = []
        self.stack2 = []


    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
#       呼叫 push function 时，会把变数 x 放进 stack1 中
        self.stack1.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
#       呼叫 pop function 时，要拿出最早放入的值，所以先看看 stack2 有没有值 ( stack2 是已经变成 Queue 排列的顺序)
#       stack2 若是空的，就把 stack1 的值逐一放入 stack2
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
#       回传 stack2 最上面的值
        return self.stack2.pop()
        

    def peek(self) -> int:
        """
        Get the front element.
        """
#       跟上面 pop function 一样，判断stack2 是不是空的，若是空的，就把 stack1 的值逐一放入 stack2
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
#       由於是 peek，只会看最前面是什麽，不会把值拿出来，所以拿出来後还要储存回去        
        top = self.stack2.pop()
        self.stack2.append(top)
        return top

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
#       检查 stack1 跟 stack2 是不是空的
        if self.stack1 or self.stack2:
            return False
        else:
            return True

其中几个 function 有更为简洁/不同的写法

    def peek(self) -> int:
#       判断 stack2 是否为空，若不为空，则回传 stack中 最後一个值 (也就是最上面的)
#       若 stack2 为空，则回传 stack1 最底下的值 (最先放的值)

        if self.stack2:
            return self.stack2[-1]
        else:
            return self.stack1[0]


    def empty(self) -> bool:
#       看 stack 的长度，若为 0 则代表 stack 为空
        if len(self.stack1)==0 and len(self.stack2)==0:
            return True
        return False

此题若不按照题目要求，使用两个 stack，也可以只使用一个 python list 的结构完成 (我们之前都是使用 list 结构，来模拟 stack 的概念)
由於 python 有些内建的 function pop，并且可以指定要拿出哪一个位置的资料，所以我们可以利用一个 list 结构模拟 stack 与 Queue，但是其他语言不一定有如此方便的功能，所以建议大家还是要学好 stack 与 queue 的概念，以便能够在不同语言也能够自己实作

class MyQueue:

    def __init__(self):
        self.stack3 = []

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

    def pop(self) -> int:
        return self.stack3.pop(0)
        
    def peek(self) -> int:
        return self.stack3[0]

    def empty(self) -> bool:
        if self.stack3:
            return False
        return True