🧱用Python 與 串列 來實現 Stack(堆疊)

Debby Hudson on Unsplash

在之前的教學中，已經學會了Node和Linked List的實作，
用Python實現了單向鏈結串列Singly linked list、雙向鏈結串列Doubly linked list。

今天要承接之前打下的基礎，用雙向鏈結串列來實作Stack 堆疊。

定義

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

規定推入資料，取出資料都必須在頂端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):
		# 底層用 雙向鏈結串列來實作 Stack
    self.stack = LinkedList()

Stack常見的function實現

1.在stack頂端插入新元素

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

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

  def push(self, data):

    self.stack.insertAtTail(data)
    return

2.讀取stack頂端元素

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

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

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

  def top(self):

    if self.stack.tail is None:
      return None

    return self.stack.tail.data

3.從stack頂端取出舊元素

直接返回並且移除stack頂端的元素，
對應的底層實作就是在返回並且移除尾巴結點的資料。

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

  def pop(self):
    return self.stack.removeAtTail()

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 == self.stack.size

完整的Stack實作和程式碼，
底層是Doubly Linked List雙向鏈結串列。

class Node:
  def __init__(self, data):
    # 儲存節點的資料
    self.data = data

    # 指向下一個節點，初始化為空 None
    self.next = None

    # 指向前一個節點，初始化為空 None
    self.prev = None


class LinkedList:
  def __init__(self):

    # 頭部節點初始化為空
    self.head = None
    # 尾巴節點初始化為空
    self.tail = None

    # 串列長度初始化為0
    self.size = 0


  def insertAtHead(self,data):
    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.tail is None:
      self.head = new_node
      self.tail = new_node
    else:

      # Update linkage
      new_node.next = self.head
      self.head.prev = new_node

      self.head = new_node
    return


  def insertAtTail(self, data):
    new_node = Node(data)

    self.size += 1

    # If the list is empty
    if self.head is None:
      self.head = new_node
      self.tail = new_node
    else:

      # Update linkage
      self.tail.next = new_node
      new_node.prev = self.tail

      self.tail = new_node

    return


  def removeAtHead(self):
    if self.head is None:
      return
    else:
      self.size -= 1
      oldHead = self.head

      # Update linkage
      if self.head == self.tail:
        self.tail = None
        self.head = None
      else:
        self.head = self.head.next

      # Break linkage
      oldHead.next = None

      if self.head:
        self.head.prev = None

      return oldHead


  def removeAtTail(self):
    if self.tail is None:
      return
    else:
      self.size -= 1
      oldTail = self.tail

      # Update linkage
      if self.tail == self.head:
        self.tail = None
        self.head = None
      else:
        self.tail = self.tail.prev

      # Break linkage
      oldTail.prev = None

      if self.tail:
        self.tail.next = None

      return oldTail


  def traverse(self):

    print("Forward traversal")
    cur = self.head

    while cur:
      print(cur.data, end=' <-> ')
      cur = cur.next
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return


  def backward_traverse(self):

    print("Backward traversal")
    cur = self.tail

    while cur:
      print(cur.data, end=' <-> ')
      cur = cur.prev
    print("None")

    print(f"Size of singly linked list: {self.size} \n", )
    return


  def search(self, target):
    cur = self.head
    while cur:
      if cur.data == target:
        return cur

      cur = cur.next

    return None


  def removeAfter(self, node):

    self.size -= 1

    removed = node.next
    the_one_after_removal = node.next.next if node.next else None

    # Update linkage
    if the_one_after_removal:
      the_one_after_removal.prev = node

    node.next = the_one_after_removal
    # Break linkage
    if removed:
      removed.next = None
      removed.prev = None

    return removed


  def insertAfter(self, node, new_node):

    self.size += 1

    the_one_after_insertion = node.next

    # Update linkage
    node.next = new_node
    new_node.prev = node

    the_one_after_insertion.prev = new_node
    new_node.next = the_one_after_insertion
    return


  def __contains__(self, item):

    cur = self.head
    while cur:
      if cur.data == item:
        return True

      cur = cur.next

    return False


  def __len__(self):
    return self.size


class Stack:
  def __init__(self):
    self.stack = LinkedList()

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

  def pop(self):
    return self.stack.removeAtTail()

  def top(self):
    if self.stack.tail is None:
      return None

    return self.stack.tail.data

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

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

  def traverse(self):
    self.stack.traverse()
    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()

  print(f"Top of stack = {stack.top()}")
  stack.pop()

  print(f"Top of stack = {stack.top()}")
  stack.pop()

  print(f"Top of stack = {stack.top()}")
  stack.pop()

  print(f"Top of stack = {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

Forward traversal
1 <-> 2 <-> 3 <-> 4 <-> None
Size of singly linked list: 4 

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

結語

這篇我們透過Linked List作為底層的輔助資料結構，來實現完整的Stack class 和 interface function。

讀者可以搭配先前的教學文章，一起復習相關的資料結構。

Stack相關的演算法練習題與詳解

Stack堆疊應用題 合法括號配對字串 Leetcode #20_Valid Parentheses

一魚多吃 用stack來解 最長合法括弧字串 Leetcode #32 Longest Valid Parenthese

應用題 用Stack實作Queue_Leetcode #232 Implement Queue using Stacks

一魚多吃 用stack來解 Backspace String Compare_Leetcode #844

一魚多吃 用stack來驗證 合法括弧字串 678. Valid Parenthesis String

用stack 模擬陣列生成 Build Array w/ Stack Operations_Leetcode 1441