2024-08-27|閱讀時間 ‧ 約 11 分鐘

🧱用Python list 來實現 Stack(堆疊)

micheile henderson on Unsplash

在之前的教學中，已經學會了用雙向鏈結串列來實作Stack 堆疊。

今天，要用另一種底層資列結構，python list，來實作Stack 堆疊。

讀者可以從中發現，因為python list的功能和function實作已經很豐富，
所以使用起來，相當直覺，也簡單許多。

定義

是一個線性長條狀的資料結構。

規定推入資料，取出資料都必須在頂端TOP操作。

(就像餐廳疊盤子，或者，書桌上疊書本的那種感覺。)

也由於這項規定，Stack先天具有先進後出First-in Last-out的這種特質。

支援的操作與介面

stack.push(data)

推入一筆新資料data進入stack的頂端。

stack.top()

取得stack頂端目前的資料。

stack.pop()

取得stack頂端目前的資料，並且將此資料從stack頂端移除。

len( stack )

取得stack的大小，也就是現在有幾筆資料存在stack裡。

stack.is_empty()

判斷stack是否為空。

優點

1.在頂端新增、取得、移除資料是O(1) 常數時間。

2.可以根據需求動態延伸或縮短，有效利用記憶體空間。

缺點

1.不支援random acess，不支援Stack[ index ] 這種操作。

2.如果要取得下層的資料，必須先將頂端的資料移除。

Stack的class定義與建構子(初始化函式)

class Stack:

  def __init__(self):
    self.stack = list()

Stack常見的function實現

1.在stack頂端插入新元素

直接在stack頂端放入新元素，對應的底層實作就是在python list尾巴串上新資料。

時間複雜度: O(1) 常數時間

  def push(self, data):
  
    self.stack.append(data)
    return

2.讀取stack頂端元素

直接返回stack頂端的元素，對應的底層實作就是返回python list尾巴的資料。

實作上有個細節需要留意，假如stack是空的，直接返回None即可。

Pyhon 的索引與法相當靈活，除了支援順著數的0, 1, 2, ..., n-1之外；

還支援逆著數的-1, -2, -3, ..., -n。

self.stack[-1]就相當於 self.stack[ len(self.stack)-1 ]

會回傳陣列尾巴的最後一個元素。

時間複雜度: O(1) 常數時間

  def top(self):
      if self.is_empty():
            return None
            
      return self.stack[-1]

3.從stack頂端取出舊元素

直接返回並且移除stack頂端的元素，

對應的底層實作就是在返回並且移除python list尾巴的資料。

時間複雜度: O(1) 常數時間

  def pop(self):
  
      if self.is_empty():
            return None
            
      return self.stack.pop()

4.取得stack的長度

返回stack的長度，也代表stack內部資料的總數量。

對應的底層實作就是在返回串列的長度。

時間複雜度: O(1) 常數時間

  def __len__(self):

    return len(self.stack)

5.檢查stack是否為空

如果stack 的長度為0，代表stack是空的，內部沒有任何資料。

時間複雜度: O(1) 常數時間

  def is_empty(self):
  
      return 0 == len( self.stack )

完整的Stack實作和程式碼，底層是Python list。

class Stack:

  def __init__(self):
    self.stack = list()

  def push(self, data):
    self.stack.append(data)
    return


  def pop(self):

    if self.is_empty():
      return None

    return self.stack.pop()


  def top(self):
    if self.is_empty():
      return None

    return self.stack[-1]


  def is_empty(self):
    return 0 == len( self.stack )


  def __len__(self):
    return len(self.stack)

  def __contains__(self, item):
    return item in self.stack

  def traverse(self):
    for element in self.stack:
      print(element, end = "->")

    print()
    return

def test():

  print(f"Empty stack\n")
  stack = Stack()

  for i in range(1, 5):
    print(f"Push {i}...")
    stack.push(i)

  print()
  print(f"Is stack empty? {stack.is_empty()}")
  print(f"Size of stack: { len(stack) } ")
  print()

  for i in range(1,6):
    print(f"Is {i} in stack? = { i in stack}")

  print()
  stack.traverse()

  for i in range(4):
    print(f"Top of stack = {stack.top()}")
    print(f"pop {stack.top()}")
    stack.pop()

  print(f"Is stack empty? {stack.is_empty()}")

  return

if __name__ == "__main__":
  test()

測試輸出

Empty stack

Push 1...
Push 2...
Push 3...
Push 4...

Is stack empty? False
Size of stack: 4 

Is 1 in stack? = True
Is 2 in stack? = True
Is 3 in stack? = True
Is 4 in stack? = True
Is 5 in stack? = False

1->2->3->4->
Top of stack = 4
pop 4
Top of stack = 3
pop 3
Top of stack = 2
pop 2
Top of stack = 1
pop 1
Is stack empty? True