Day 7：225. Implement Stack using Queues

今日题目

题目连结：225. Implement Stack using Queues
题目主题：Stack, Design, Queue

了解完Stack跟Queue的概念後，最後再复习一题，上一题是用Stack实作Queue，这次题目是用Queue来实作Stack，这样应该足够对这两种资料结构有更深的了解。

简单说说 Follow-up

这次不讲演算法资料结构，Stack跟Queue在前两篇都提过了，在这边多提一下关於LeetCode上面，平常如果有力气时可以多做的事情Follow-up。

有些题目会有这一个项目，是给解题者额外更难的挑战。以这题为例的话，原本题目解释的目标是说，请用两个Queue来实作Stack，但最後给你一个Follow-up问说，你可以用一个Queue来实作出Stack吗？

本文最後会分享的是两个Queue来实作的Stack，如果各位夥伴有空的话，可以再挑战看看这一题的Follow-up，这题的挑战其实并不难，建议可以玩玩看。

题目解说

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

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

1. push：新增一笔资料。
2. pop：取得一笔资料，并且将此资料移除。
3. top：取得一笔资料。
4. empty：确认是否为空。

约束：

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

范例1：

输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

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

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

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

解题的想像

文字描述

1. 初始化时，宣告两个Queue，分别为queue跟tmp_queue。
2. queue 可直接针对以下使用：
   • empty 检查是否为空
   • push 直接放一笔资料进去
   • top 直接看拿最後一笔资料回传
3. tmp_queue是暂存用的，在pop时才会使用到，每次pop时：
   • 将queue所有值一个一个放到tmp_queue中，直到剩一个值
   • 剩下的一个值，直接当pop回传值，不用在放进暂存区
   • tmp_queue现有所有值再放回queue并清空
   • tmp_queue使用完後永远保持空的状态

图解过程

1. __init__(self) 初始化时，宣告两个Queue
   

2. push(self, x: int) -> None
   假设 push 了三次资料，分别是1, 2, 3。
   

3. top(self) -> int
   继续上面的状态，queue = [1, 2, 3]
   top，只需要显示不需要取出，因此直接拿最後一笔当回传值即可。
   

4. pop(self) -> int
   继续上面的状态，queue = [1, 2, 3]
   pop这边分为三步骤来完成，如下图。
   

   1. 会先把资料一笔一笔放进tmp_queue，直到剩一笔
   2. 最後这一笔是pop要回传的资料
   3. 再从tmp_queue放回queue中，tmp_queue保持空的
   4. 最後回传的值就是pop_value

5. empty(self) -> bool
   继续上面的状态，因拿出一笔资料，现在queue = [1, 2]
   因为tmp_queue永远保持空的，检查queue是否为空即可，此范例的结果会回False。
   

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

程序码撰写

from collections import deque

class MyStack:
    # 初始化 需要两个Queue
    def __init__(self):
        self.queue = deque()
        self.tmp_queue = deque()
        
    # 直接用 queue 来新增资料
    def push(self, x: int) -> None:
        self.queue.append(x)

    # tmp_queue 是暂存用的
    # Queue是只能从最先进去的资料取得，因此把资料一个一个取出存到tmp_queue
    # 直到剩一个资料才是stack的pop要取出来的资料，stack要取得是最後一个进去的资料
    # 最後把tmp_queue的资料放回queue中，让tmp_queue永远保持空的
    def pop(self) -> int:
        while len(self.queue) >= 2:
            self.tmp_queue.append(self.queue.popleft())
        pop_value = self.queue.popleft()
        self.queue = deque(self.tmp_queue)
        self.tmp_queue.clear()
        return pop_value

    # 直接取得 queue 的最後一笔资料即可
    def top(self) -> int:
        return self.queue[-1]

     # 直接检查 queue 是否为空即可，因为tmp_queue会确保保持空的
    def empty(self) -> bool:
        return not self.queue

希望您今天能了解到...

1. Follow-up的挑战
2. 更熟悉Queue及Stack用法
3. 225. Implement Stack using Queues 解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：506. Relative Ranks