# [資演] 8- Stack 和 Queue

###### tags: `資演`

## 什麼是 stack？
Stack (堆疊) 是一種後進先出 (last in first out, **LIFO**) 的資料結構。


想像你正在洗一堆盤子。首先，你必須先將盤子從餐桌上疊到洗碗槽裡。此時，先收進來的盤子會疊在這堆盤子的底部，接著一個一個往上疊，最後一個盤子疊在最上面。

現在有了這樣一堆盤子，你要怎麼洗它們呢？一定是從最上面那個盤子開始洗吧！所以，比較晚進來的盤子先處理，這就是後進先出的概念。所以我們可以把一疊盤子當作是一個 stack；或著是說，把一個stack當成是一堆盤子。

類似的概念還有像是一疊便條紙、一疊書等，這些都可以看做是stack在真實生活中的例子。

那麼，我們為什麼需要stack呢？

Stack的應用非常廣泛。舉個例子，想想我們瀏覽器的**上一頁**功能（其實書本的上一頁也是類似的）。我們比較早瀏覽的頁面會被放在堆疊的下面，比較晚（也就是說，比較接近**現在**）瀏覽的頁面會被放在堆疊的上面。當我們點擊上一頁按鈕時，我們希望比較接近現在瀏覽的網頁會先呈現給我們，因此這可以用一個stack的資料結構來實現。


## Stack 上的操作
使用Python的list，我們可以很簡單地實作一些stack的功能。
* 創建一個stack
在這裡我們可以直接建立一個空的list，例如：

    stack = []

* 在stack中加入元素: push
這個功能可以使用list的`append`方法來做，例如：

    stack.append(3)
    stack.append(5)
    stack.append(8)
    
    print(stack)

其結果會是`[3, 5, 8]`。
* 把最頂端的元素彈出來: pop
Python的list有內建的`pop`方法可以達成這個任務，當我們使用`pop`方法時，會把最後一個元素彈出去，並回傳這個元素。例如：

    a = stack.pop()

這時`a`會等於`8`，`stack`會變成 `[3, 5]`。

## 使用 stack 來解決問題
* 檢查括弧是否成對出現
給定一個字串，裡面只包含了三種括弧的字元：`()[]{}`，檢查這些括弧是否有效地成對出現。
:::spoiler 提示
從字串的最左邊開始，遇到一個左括號（不論大小），就先append到stack裡面；如果遇到相應的右括號，就把該括號pop出來；或者，當出現了一個右括號，卻沒有相應的左括號能配對，則直接回傳`False`。當整個字串都檢查完後，如果該stack還有東西，代表還有左括號沒有遇到對應的右括號，則回傳`False`；如果stack是空的，則回傳`True`。
:::
:::spoiler 解答

    class Solution(object):
        def isValid(self, s):
            stack = []

            for i in range(len(s)):
                if (s[i] == "(" or s[i] == "[" or s[i] == "{"):
                    stack.append(s[i])
                elif(len(stack) > 0):
                    if(s[i] == ")" and stack[len(stack) - 1] == "("):
                        stack.pop()
                    elif(s[i] == "]" and stack[len(stack) - 1] == "["):
                        stack.pop()
                    elif(s[i] == "}" and stack[len(stack) - 1] == "{"):
                        stack.pop()
                    else:
                        return False
                else:
                    return False
            if(len(stack) > 0):
                return False
            else:
                return True

:::
## 什麼是 queue？
Queue (佇列) 是一種先進先出 (first in first out, **FIFO**) 的資料結構。


想像你正在排隊搶最新的iPhone。很自然地，先到的人可以先買到iPhone。這樣的一個隊伍我們可以稱為是一個queue，因為它滿足了先到先處理的模式。

## Queue 上的操作
在這邊，我們使用`collections`裡面的`deque`模組來實作queue。這個模組被設計成能快速的從頭尾兩端加入和取出。首先，我們先import這個模組：

from collections import deque

* 創建一個queue
在這裡我們可以直接建立一個空的list，例如：

    queue = deque([])

* queue中加入元素: enqueue
這個功能可以使用list的`append`方法來做，例如：

    queue.append(1)
    queue.append(3)
    queue.append(5)
    
    print(queue)

其結果會是`deque([1, 3, 5])`。
* 把最前面的元素處理掉: dequeue
在這個模組裡面要取出最前面的元素，也就是dequeue的實作是使用`popleft`方法：

    a = queue.popleft()

如此一來，我們會得到a是`1`，而`queue`會是`deque([3, 5])`。

## Circular queue
現在我們來設計一個size固定的circular queue的資料結構。當我們從一個circular queue的最前端取出一個元素之後，這個元素會被append到circular queue的最尾端。

:::spoiler 思路
我們可以使用Python list來實作，並用一個數值`headIndex`來儲存最前面的元素的位置。因為現在的size是固定的，所以我們可以很容易地知道尾端的位置。
:::

:::spoiler 解答
class MyCircularQueue:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the queue to be k.
"""
self.queue = [0]*k
self.headIndex = 0
self.count = 0
self.capacity = k

def enQueue(self, value: int) -> bool:
"""
Insert an element into the circular queue. Return true if the operation is successful.
"""
if self.count == self.capacity:
return False
self.queue[(self.headIndex + self.count) % self.capacity] = value
self.count += 1
return True

def deQueue(self) -> bool:
"""
Delete an element from the circular queue. Return true if the operation is successful.
"""
if self.count == 0:
return False
self.headIndex = (self.headIndex + 1) % self.capacity
self.count -= 1
return True

def Front(self) -> int:
"""
Get the front item from the queue.
"""
if self.count == 0:
return -1
return self.queue[self.headIndex]

def Rear(self) -> int:
"""
Get the last item from the queue.
"""
# empty queue
if self.count == 0:
return -1
return self.queue[(self.headIndex + self.count - 1) % self.capacity]

def isEmpty(self) -> bool:
"""
Checks whether the circular queue is empty or not.
"""
return self.count == 0

def isFull(self) -> bool:
"""
Checks whether the circular queue is full or not.
"""
return self.count == self.capacity
:::