##棧部分-（疊貓貓）

##抽象數據類型棧的定義：是一種遵循先入后出的邏輯的線性數據結構。

換種方式去理解這種數據結構如果我們在一摞盤子中取到下面的盤子，我們首先要把最上面的盤子依次拿走，才可以繼續拿下面的盤子，我們把盤子替代成各種類型的元素（如整形，字符，對象等），對于棧就是類似這種衍生出來的線性數據結構。

##棧的定義（c++）：是限定僅在表尾進行插入或刪除操作的線性表

##圖例介紹

##LIFO結構：

##動態過程

##棧的表示和實現

##棧常用操作：pop(),push(),peek()

然而，某些語言可能沒有專門提供棧類，這時我們可以將該語言的“數組”或“鏈表”當作棧來使用，并在程序邏輯上忽略與棧無關的操作。

棧遵循先入后出的原則，我們只能在棧頂添加或刪除元素。

但是，數組和鏈表都可以在任意位置添加和刪除元素，所以棧可以看作是一種受限制的數組或鏈表。

##棧的順序表示-基于數組的實現

采用具有一塊連續存儲的地址進行相關操作，具有代表性的便是數組，基于數組的實現棧。

我們可以將數組的尾部視作棧頂，入棧和出棧操作分別對應在數組的尾部添加或者刪除元素，時間復雜度都為O(1)。

##圖解

##python代碼實現

考慮到入棧的元素可能會遠遠不斷的地增加，因此我們可以使用動態數組，這樣就可以不用自行處理數組的擴容問題。

class ArrayStack:"""基于數組實現額棧"""def __init__(self):"""構造方法"""self._stack:list[int] = []def size(self):"""獲取棧的長度"""return len(self._stack)def is_empty(self):"""判斷棧是否為空"""return self._stack == []def push(self,item):"""入棧"""self._stack.append(item)def pop(self):"""出棧"""if self.is_empty():raise IndexError("棧為空")return self._stack.pop()def peek(self):"""訪問棧頂元素"""if self.is_empty():raise IndexError("棧為空")return self._stack[-1]def to_list(self):"""返回列表用于打印"""return self._stack

時間效率：在基于數組的實現中，入棧和出棧操作都在預先分配好的連續內存中進行，具有很好的緩存本地性，因此效率較高。然而，如果入棧時超出數組容量，會觸發擴容機制，導致該次入棧操作的時間復雜度變為O(n)?。

空間效率：在初始化列表時，系統會為列表分配“初始容量”，該容量可能超出實際需求；并且，擴容機制通常是按照特定倍率（例如 2 倍）進行擴容的，擴容后的容量也可能超出實際需求。因此，基于數組實現的棧可能造成一定的空間浪費。