Day 6：232. Implement Queue using Stacks

今日题目

题目连结：232. Implement Queue using Stacks
题目主题：Stack, Design, Queue

此题目主要是来了解Queue，在了解了Stack的运作方式以後，接下来要分享的是Queue的运作方式。

简单说说 Queue

Queue（队列）是一种先进先出 ( FIFO ) 的资料结构，最新的资料永远都是最後才被取出，也就是先进去的资料会被优先拿出来，使用的方式及过程如下图。

可以想像 Queue 是一个圆角方形空间，从上图中范例有新的资料进去时，会从前面进去一笔新的资料，每次取出资料都会从後面取得最新的资料，因此 3 虽然是最新进去的，但是一直到最後才会轮到他被取出。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目的目标是用两个Stack来实现Queue的功能，需实现的功能分别为：

push：新增一笔资料。
pop：取得一笔资料，并且将此资料移除。
peek：取得一笔资料。
empty：确认是否为空。

约束：

1 <= x <= 9
最多执行100次方法（push、pop、peek、empty）
使用 pop 和 peek 会是有效的状态下执行

范例1：

输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

输出:
[null, null, null, 1, 1, false]

解释:
输入的第一个阵列会是几个指令，第二个阵列是输入的参数。
输出就是使用指令後得到回应。
范例输入的指令过程会像是下方这一段。
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2]
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

在初始化时宣告 stack1 跟 stack2 两个Stack
stack1 是用来push资料
- 每次使用时，会先把 stack2 倒过来放进 stack1 中
- 确定 stack2 空了以後，再放入新资料
stack2 是用来pop资料
- 每次使用时，会先把 stack1 倒过来放进 stack2 中
- 确定 stack1 空了以後，在从stack2取出资料
peek最新资料时
- 若资料在stack1，取得最前面的资料
- 若资料在stack2，取得最後面的资料
empty 需检查 stack1 跟 stack2 是否为空

图解过程

__init__(self) 初始化时，宣告两个Stack
push(self, x: int) -> None
假设资料在 stack2 = [3, 5, 4, 2]
现在要放入 x = 1，使用stack1来新增资料。

如上图，因为 Queue 是 FIFO，所以不能直接放在 stack2 中 2 的後面，要放在 3 的前面，所以才会把它倒过来放到 stack1 後再放进 x 资料，绿色方块资料是从 stack2 倒过来後放进 stack1 的资料，之後在把新的 x 红色方块资料放进 stack1 中。
pop(self) -> int
从上步骤继续 stack1 = [2, 4, 5, 3, 1]
使用stack2来取得资料，并移除取出来的资料。
1 是最後进去的，Queue 是 FIFO 所以现在要取得的是最先进去的 2。

如上图，绿色方块资料是从 stack1 倒过来後放进 stack2 的资料，之後在把最先放进来的 2 取出来。
peek(self) -> int
从上步骤继续 stack2 = [1, 3, 5, 4]
这边只是要知道接下来pop要取得的资料是什麽，因此现在应该会是显示 4 。
（下图我们把 stack1 跟 stack2 的状况都标出来，实际上绝对不会有两个stack都有资料的状况存在）
empty(self) -> bool
需要检查两个stack都是空的，才是真的空。
以下图范例来说，这样的状态会回传True。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class MyQueue:
    # 初始化 需要两个Stack
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    # stack1 是用来新增资料用的
    # 使用前会先把 stack2 倒过来到 stack1 在新增
    def push(self, x: int) -> None:
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.stack1.append(x)
        
    # stack2 是用来取得资料用
    # 使用前会先把 stack1 倒过来到 stack2 在取得资料
    def pop(self) -> int:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    # 看目前资料在 stack1 还是 stack2 中
    # 若在 stack1 中，会从最前面取得资料
    # 若在 stack2 中，会从最後面取得资料
    def peek(self) -> int:
        return self.stack1[0] if self.stack1 else self.stack2[-1]
    
    # stack1 跟 stack2 都是空的才是真的空
    def empty(self) -> bool:
        return not self.stack1 and not self.stack2