9.棧（stack）

棧

棧和隊列是兩個很基礎的資料結構

一般棧有兩個概念：

    （1）棧區（記憶體中）

    （2）LIFO（Last In First Out）

棧最好的了解方式，可以了解為一個桶，往桶裡放盤子，拿出來的時候隻能從頂上開始拿。

           data 

ADT {

          method { push

                          pop

上一節實作了先進先出的循環雙端隊列（Deque），支援雙向的push/pop操作，隻要實作了Deque就很容易實作棧。

其實用 python 的内置類型 collections.deque 來實作它也很簡單。

用Deque實作stack

先繼承之前寫的 CircualDoubleLinkedList() 類，通過繼承的方式實作Deuqe，如下：

class Deque(CircualDoubleLinkedList):
    def pop(self):
        if len(self) == 0:                      #如果隊列為空
            raise Exception('empty')
        tailnode = self.tailnode()              #定義尾節點
        value = tailnode.value                  #尾節點的值
        self.remove(tailnode)                   #删除尾節點，O(1)
        return value                            #傳回删除節點的value
    
    def popleft(self):                          #另外一種從左側删除的方法
        if len(self) == 0:
            raise Exception("empty")
        headnode = self.headnode()
        value = headnode.value
        self.remove(headnode)
        return value
    
    
class Stack():
    def __init__(self):
        self.deque = Deque()                    #使用内置庫的collections.deque方法更容易實作
        
    def push(self, value):
        return self.deque.append(value)
    
    def pop(self, value):
        return self.deque.pop(value)

    def __len__(self):
        return len(self.deque)
    
    def is_empty(self):
        return len(self) == 0
    
    

#單元測試
def test_stack():
    s = stack()
    for i in range(3):
        s.push(i)
    assert len(s) == 3
    assert s.pop() == 2
    assert s.pop() == 1
    assert s.pop() == 0
    assert s.is_empty()
    
    import pytest
    with pytest.raise(Exception) as excinfo:
        s.pop()
    assert "empty" in str(excinfo.value)      

棧溢出（Stack over flow）

棧有兩個主要的使用含義：

    1.資料結構上所說的後進先出的結構

    2.記憶體結構的棧區

當寫遞歸函數的時候，每一層的遞歸函數都會用棧區來存儲每一層函數它的變量值，如果寫了一個沒有出口的遞歸函數，就會導緻棧溢出。

示範棧溢出：

#棧溢出
def infinite_fib(n):
    return infinite_fib(n-1) + infinite_fib(n-2)

#執行這個函數後，會傳回異常
if __name__ == "__main__":
    infinite_fib(10)      

出現棧溢出是因為記憶體配置設定給棧區的大小是固定的，當寫了一個無窮遞歸的函數，棧空間很快就會被用完，就會抛出builtins.RecursionError: maximum recursion depth exceeded的棧異常。