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

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

$isFull()$ 的情況。

• [未完成] 使用Queue實現Stack的3種方法 (Leetcode 225)
  • Python的deque套件簡介
  • Method 1. 使用兩個queue，在 push() 時調整
  • Method 2. 使用兩個queue，在 pop() 時調整
  • Method 3. 使用一個queue，在 pop() 時調整

LeetCode	力扣
225. Implement Stack using Queues	225. 用队列实现栈

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