用 Python 實作 Stack
大學三年到現在大二學的資料結構也忘的差不多乾淨了
之前用java實作資料結構，現在轉換跑道入坑python
以下針對幾個要點來介紹Stack資料結構
- 什麼是Stack？
- Stack 應用
- 如何用python實作stack
目錄
什麼是Stack？
Stack 是一個線性（linear）資料的集合
是採 LIFO(Last In First Out) 後進先出的方式儲存與取得資料
Stack 直譯下就是「堆疊」
「堆疊」顧名思義就是一堆疊起來的東西（？
最經典的例子就是堆起來的盤子
在抽盤子的時候並不會從最下面（也就是第一個放的盤子）的開始拿，而是從最上面（最後放的）開始拿。
時間複雜度 （time complexity）: O(n)
不同於list或array，stack的結構並不允許隨機存取
Stack的operations
| Push | To add data into the stack 新增資料到stack | O(1) |
| Pop | To remove data from the stack 從stack移除資料 | O(1) |
Stack 可以用Array 或Linked List 實作
為什麼要用Stack?
Stack可以讓我們以序列（sequentially）的方式儲存資料
Stack 應用
- call stack + stack memory
- 深度優先搜尋演算法（DFS, Depth-First-Search）
- 尤拉迴路（Eulerian Circuit）
- 瀏覽器回上一頁
- 回上一步(undo)
如何用python實作stack
- 用 list 內建資料結構（list built-in data structure）
- 用deque(double-ended queue; 雙端佇列) library 雙端佇列
- 用queue（佇列）
PUSH Operation
Push - adds an element at the top of the stack
POP Operation
Pop - removes an element from the top of the stack
from collections.abc import Iterable
class Stack:
def __init__(self, initial_data):
self.stack = []
self.initial_data = initial_data
＃判斷是否是initial_data是否是可迭代的資料
if isinstance(initial_data, Iterable):
self.stack = list(initial_data)
else:
raise NotImplementedError('Initial＿data was not iterable data')
#給python Interpreter看的
def __repr__(self):
return "Stack(initial_data={!r})".format(self.initial_data)
#給使用者看的print()
def __str__(self):
return "stack({})".format(self.stack)
#return: int
def __len__(self):
return len(self.stack)
def __getitem__(self, i):
return self.stack[i]
@property
def is_empty(self):
return len(self.stack) == 0
def push(self, data):
self.stack.append(data)
#return: data that pop out
def pop(self):
if not self.is_empty:
return self.stack.pop()
# return: top element in stack
def peek(self):
return self.stack[-1]
def main():
list1 = []
stack = Stack(list1)
print(stack) # stack([])
stack.push(1)
print(stack) # stack([1])
stack.pop()
print(stack) # stack([])
stack.push(3)
print(stack) # stack([3])
stack.push(4)
print(stack) # stack([3, 4])
print(stack.peek()) # 4
if __name__ == '__main__':
main()推薦入門書籍
精通 Python：運用簡單的套件進行現代運算（第二版）
之前開始入坑python時就是用這本打底的（有換封面過）
這本書除了前幾張介紹基本的語法之外
後續幾張開始介紹與python相關的延伸性的功能
非常適合程式設計初學者以及剛要開始學習這個語言的讀者
羅列以下幾點關於本書大綱供大家參考
- 學習簡單的資料類型、基本數學運算與文字操作
- 以Python的內建資料結構處理資料
- 探索Python程式碼結構，包括函式的使用
- 使用模組與套件編寫大型Python程式
- 深入討論物件、類別與其他物件導向功能
- 檢視一般檔案、關聯式資料庫與NoSQL的儲存機制
- 使用Python建構web用戶端、伺服器、API與服務
- 管理系統工作，例如程式、程序與執行緒
- 瞭解並行處理與網路程式設計的基礎
流暢的 Python：清晰、簡潔、有效的程式設計
適合已經有Python程式語言基礎的人
這本書更詳細的介紹有關python的用法
讓我們寫的程式可以更加"Pythonic"
建議可以與英文版同時閱讀
以後在查閱stackoverflow文獻的時候能不因語言而產生隔閡
- Python 資料模型：瞭解特殊方法是讓物件具備一致行為的關鍵
- 資料結構：充分使用內建的型態，並瞭解 Unicode 時代中，文字 vs. bytes 之間的關係
- 函式就是物件：見識 Python 函式是一級物件，並瞭解這個事實如何影響熱門的設計模式
- 物件導向的習慣用法：學習參考、可變性、介面、運算子多載與多重繼承，並建構類別
- 控制流程：藉由 concurrent.futures 與 asyncio 套件，來充分活用情境管理器、產生器、協同程序與並行
- 中繼編程：瞭解特性、屬性描述器、類別修飾器與中繼類別的工作原理
如果對文章內容有任何問題，歡迎在底下留言讓我知道。 如果你喜歡我的文章，可以分享我的文章，讓更多的人看見我的文章。 追蹤我的Instagram，看我分享 #咖啡雞湯 #咖啡廳推薦 如果這篇文章對你有幫助， 可以幫我在下方按 5 個Like 讓我得到一些回饋， 支持我繼續寫出更多好文章！
- 【SSH】製作SSH key教學
製作SSH key 1. 打開終端機(Bash/Terminal) 2. 輸入指令 3. 將指定的 SSH 私 … 閱讀全文 - 【快速架站】什麼是Hexo? 5分鐘快速架站教學What is Hexo? Hexo 是一個快速、簡單且強大的網誌框架。Hexo 使用 Markdown（或其 … 閱讀全文
- 【Python】Quick Sort 快速排序｜演算法介紹、新手快速入門目錄 基本概念實際應用線上學習平台推薦udemy推薦入門書籍精通 Python：運用簡單的套件進行現代運算（第 … 閱讀全文
在〈【Python】Stack(堆疊) 資料結構實作〉中有 10 則留言