使用堆疊

Data Structures and Algorithms in Python

Miriam Antona

Software Engineer

堆疊（Stacks）

LIFO： Last-In First-Out（後進先出）
- 最後插入的項目會最先被移除

一疊書的圖片。

堆疊（Stacks）

LIFO： Last-In First-Out（後進先出）
- 最後插入的項目一定最先被移除
只能在頂端新增
- 將元素「推入」堆疊（push）

在堆疊頂端新增一本書的圖片。

堆疊（Stacks）

LIFO： Last-In First-Out（後進先出）
- 最後插入的項目一定最先被移除
只能在頂端新增
- 將元素「推入」堆疊（push）
只能從頂端取出
- 從堆疊「彈出」（pop）

從堆疊頂端取走一本書的圖片。

堆疊（Stacks）

LIFO： Last-In First-Out（後進先出）
- 最後插入的項目一定最先被移除
只能在頂端新增
- 將元素「推入」堆疊（push）
只能從頂端移除
- 從堆疊「彈出」（pop）
只能讀取最後一個元素
- 從堆疊「偷看」（peek）

一疊書，箭頭指向最上面那本書的封面。

堆疊：實際用途

復原（Undo）功能

只含一個元素的堆疊。

堆疊：實際用途

復原（Undo）功能
- 每次按鍵皆「push」

在堆疊頂端新增一個元素。

堆疊：實際用途

復原（Undo）功能
- 每次按鍵皆「push」

在堆疊頂端新增一個元素。

堆疊：實際用途

復原（Undo）功能
- 每次按鍵皆「push」

在堆疊頂端新增一個元素。

堆疊：實際用途

復原（Undo）功能
- 每次按鍵皆「push」

在堆疊頂端新增一個元素。

堆疊：實際用途

復原（Undo）功能
- 每次按鍵皆「push」
- 將最後一次按鍵「pop」

自堆疊頂端移除一個元素。

堆疊：實際用途

符號檢查器： ( [ { } ] )
- 將開啟符號「push」

含有一個開啟符號的堆疊。

堆疊：實際用途

符號檢查器： ( [ { } ] )
- 將開啟符號「push」

在堆疊頂端新增一個開啟符號。

堆疊：實際用途

符號檢查器： ( [ { } ] )
- 將開啟符號「push」

在堆疊頂端新增一個開啟符號。

堆疊：實際用途

符號檢查器： ( [ { } ] )
- 將開啟符號「push」
- 檢查關閉符號

含有開啟符號且標示「check "}"」的堆疊。

堆疊：實際用途

符號檢查器： ( [ { } ] )
- 將開啟符號「push」
- 檢查關閉符號
- 將相符的開啟符號「pop」

自堆疊頂端移除一個開啟符號。

堆疊：實際用途

函式呼叫
- 將記憶體區塊「push」
- 執行結束後「pop」

堆疊：以單向連結串列實作

以連結串列表示的堆疊。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

堆疊：以單向連結串列實作

標示節點各部分名稱的連結串列堆疊。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

堆疊：以單向連結串列實作

以「TOP」指向堆疊頂端的連結串列堆疊。

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

堆疊：push

空堆疊與含元素堆疊的示意圖。

def push(self, data):

堆疊：push

空堆疊與含元素堆疊，準備插入新節點。

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

  if self.top:

堆疊：push

空堆疊與含元素堆疊，新節點連到頂端元素。

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

堆疊：push

空堆疊與含元素堆疊，已插入新節點。

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

堆疊：pop

def pop(self):

  if self.top is None:

    return None

  else:

堆疊示意圖，文字「TOP」指向頂端節點。

堆疊：pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

堆疊示意圖，「popped_node」指向頂端節點。

堆疊：pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

堆疊示意圖，「popped_node」指向頂端節點，「TOP」指向第二個節點。

堆疊：pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

堆疊示意圖，「popped_node」指向已與堆疊斷開的節點，「TOP」指向頂端節點。

堆疊：pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

堆疊示意圖，「TOP」指向頂端節點。

堆疊：peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

Python 的 LifoQueue

LifoQueue：
- Python 的 queue 模組
- 行為如同堆疊

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

一起來練習吧！

Data Structures and Algorithms in Python