# [未完成] 使用Queue實現Stack的3種方法 (Leetcode 225)

> 寫每日一題的時候發現這題好像在哪間學校的考古題寫過，感覺蠻有機會考出來，就把所有思路都記錄下來，萬一考出來了？ `[112交大]`
> 考試時可能還要注意 $isFull()$ 的情況。

[ToC]

| LeetCode | 力扣 |
| -------- | -------- |
| [225. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) | [225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/)

## Python的deque套件簡介

依照題目的要求，能使用那些函數，且python中是如何調用的
$back()$ ? -> X
[未完成]

## Method 1. 使用兩個queue，在 push() 時調整
- 目的為**使queue1維持stack的性質** (即queue1的第1個元素為stack上最頂端的元素，以此類推)，queue2用來在調整時暫存queue1的元素
- 時間複雜度：
- $push()$: $O(n)$
- $pop()$: $O(1)$
- $top()$: $O(1)$
- $empty()$: $O(1)$
- 在上述的前提下，可以發現在stack的4個操作裡面，只有 $push()$ 會破壞這個性質，因此我們要在 $push()$ 的時候做調整。
- 在 $push()$ 時，因為queue1本身就具stack的性質，為了繼續維持stack性質，可以先先把新的元素push到queue2，這樣新的元素在queue2中就會是stack最頂層的元素。
- 之後再把原本queue1內的元素依次加入queue2中 (pop出來後push進queue2)，queue2就會維持stack的性質，最後再把queue1和queue2兩者交換，讓queue1繼續維持stack的性質就好。

from collections import deque

class MyStack1:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, x: int) -> None:
        """
        因為queue1要保持stack的性質，所以要把queue1的元素都移到queue2
        那麼queue2的元素就會維持stack的性質，最後再把兩者交換，讓queue1維持stack的性質
        """
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self) -> int:
        """
        在某些語言中的pop()可能不能處理size為0的情況，考試時要注意
        """
        return self.queue1.popleft() if self.queue1 else None

    def top(self) -> int:
        """
        Python的deque沒有top()，直接取[0]就好，另外和pop()相同，在某些語言中的top()可能不能處理size為0的情況，考試時要注意
        """
        return self.queue1[0] if self.queue1 else None

    def empty(self) -> bool:
        return not self.queue1

## Method 2. 使用兩個queue，在 pop() 時調整
- 目的為**使queue1還是維持queue的性質**，queue2同樣用來在調整時暫存queue1的元素
- 時間複雜度：
- $push()$: $O(1)$
- $pop()$: $O(n)$
- $top()$: $O(n)$
- $empty()$: $O(1)$
- 在上述的前提下，可以發現在stack的4個操作裡面，其實都不會破壞這個性質。
- 但在 $pop()$ 時因為我們不能直接取出和刪除最後一個元素，所以我們要利用暫存用的queue2，先對queue1做n-1次pop，同時把元素push到queue2後，再對queue1做1次pop把最後一個元素pop出來，這個元素就是stack頂端的元素。最後再把兩個queue交換，讓queue1維持原本的性質。
- 在做 $top()$ 時我們同樣不能直接取出最後一個元素，但我們可以利用已經寫好的 $pop()$ ，把頂端的元素pop出來，再把它push回去就好。
- 有些題解在取 $top()$ 時的的方法是用了 $back()$ ，但是這樣就不是queue了，不符合題目要求。

class MyStack2:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

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

    def pop(self) -> int:
        if not self.queue1:
            return None
        size = len(self.queue1)
        while size > 1:
            self.queue2.append(self.queue1.popleft())
            size -= 1
        self.queue1, self.queue2 = self.queue2, self.queue1
        return self.queue2.popleft()

    def top(self) -> int:
        """
        這裡可以用上述的pop()方法把top的元素pop出來，再把它push回去就好了
        """
        if not self.queue1:
            return None
        top = self.pop()
        self.push(top)
        return top

    def empty(self) -> bool:
        return not self.queue1

## Method 3. 使用一個queue，在 pop() 時調整
- 和方法2.類似，但是不用兩個queue，而是只用一個queue就能完成
- 使queue1還是維持queue的性質，但**不用使用另外一個queue2暫存queue1的元素，直接push回queue1即可**
- 時間複雜度：
- $push()$: $O(1)$
- $pop()$: $O(n)$
- $top()$: $O(n)$
- $empty()$: $O(1)$
- 概念和方法2.基本相同，因此不再贅述。

class MyStack3:
    def __init__(self):
        self.queue = deque()

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

    def pop(self) -> int:
        if not self.queue:
            return None
        size = len(self.queue)
        while size > 1:
            self.queue.append(self.queue.popleft())
            size -= 1
        return self.queue.popleft()

    def top(self) -> int:
        """
        這裡可以用上述的pop()方法把top的元素pop出來，再把它push回去就好了
        """
        if not self.queue:
            return None
        top = self.pop()
        self.push(top)
        return top

    def empty(self) -> bool:
        return not self.queue

class MyStack(MyStack3):
    pass