python stack資料結構實作
Data Structure python

【Python】Stack(堆疊) 資料結構實作

用 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

PushTo add data into the stack
新增資料到stack
O(1)
PopTo 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

  1. list 內建資料結構(list built-in data structure)
  2. deque(double-ended queue; 雙端佇列) library 雙端佇列
  3. 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程式碼結構,包括函式的使用
  • 使用模組與套件編寫大型Python程式
  • 深入討論物件、類別與其他物件導向功能
  • 檢視一般檔案、關聯式資料庫與NoSQL的儲存機制 
  • 使用Python建構web用戶端、伺服器、API與服務 
  • 管理系統工作,例如程式、程序與執行緒
  • 瞭解並行處理與網路程式設計的基礎

流暢的 Python:清晰、簡潔、有效的程式設計

博客來-流暢的Python:清晰、簡潔、有效的程式設計

適合已經有Python程式語言基礎的人

這本書更詳細的介紹有關python的用法

讓我們寫的程式可以更加”Pythonic”

建議可以與英文版同時閱讀

以後在查閱stackoverflow文獻的時候能不因語言而產生隔閡

  • Python 資料模型:瞭解特殊方法是讓物件具備一致行為的關鍵
  • 資料結構:充分使用內建的型態,並瞭解 Unicode 時代中,文字 vs. bytes 之間的關係
  • 函式就是物件:見識 Python 函式是一級物件,並瞭解這個事實如何影響熱門的設計模式
  • 物件導向的習慣用法:學習參考、可變性、介面、運算子多載與多重繼承,並建構類別
  • 控制流程:藉由 concurrent.futures 與 asyncio 套件,來充分活用情境管理器、產生器、協同程序與並行
  • 中繼編程:瞭解特性、屬性描述器、類別修飾器與中繼類別的工作原理

如果對文章內容有任何問題,歡迎在底下留言讓我知道。 
如果你喜歡我的文章,可以分享我的文章,讓更多的人看見我的文章。 
追蹤我的Instagram,看我分享 #咖啡雞湯 #咖啡廳推薦 
如果這篇文章對你有幫助,
可以幫我在下方按 5 個Like 讓我得到一些回饋,
支持我繼續寫出更多好文章!

在〈【Python】Stack(堆疊) 資料結構實作〉中有 8 則留言

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *