企業資訊與管理系
助理教授/日導
羅德興

歷程檔案 Portfolio

Unit 4 堆疊 (Stack)

4-1 堆疊(Stack)

【堆疊常用專有名詞】

1. Push(加入)：加入新項目到堆疊的頂端。

【演算法】

Procedure Push(item, Stack)

Begin

if (Top= N-1) //如果Top指標指到堆疊頂端

Stack Is Full; //代表堆疊已滿

Else //如果不是，則

{

Top=Top+1; //指標位址加1

Stack[Top]=item; //再將資料加入到指標所在的堆疊中

}

End

End Procedure

2. Pop ：取出堆疊頂端一個項目。

【演算法】

Procedure Pop(item, Stack)

Begin

if (Top=-1) //如果Top指標為-1

Stack Is Empty; //代表Stack為空

else //否則

{

item=Stack[Top]; //將資料從堆疊頂端取出

Top=Top-1; //再將指標位址減1

}

End

End Procedure

【堆疊的應用】

1.副程式呼叫與返回

2.遞迴程式呼叫與返回

3.運算式之轉換與求值

4.中斷處理

5.二元樹追蹤

6.巨集呼叫

7.多元處理

8.圖形(Graph)的深度搜尋

9.資料反序輸出(例如：abcàcba)

10.自助餐廳取餐盤的行為

4-2 以陣列來製作堆疊
範例 4-1

'''
This is ch2-7.1.ipynb by 羅老師 on 2024/03/20
要處理 Stack
想想 IPO ......
Stack 的演算法

'''
print("===============程式描述========================")
print("= 程式名稱：ds4-1.ipynb (ch3-2.py)                          =")
print("= 程式目的：使用堆疊進行push以及pop            =")
print("==============================================")
MaxNum=5           #定義堆疊大小
Stack=[0,0,0,0,0]  #以陣列Stack當作堆疊
Top =-1
def menu():
    print("==============================================");
    print("=   1.push(加入)                             =");
    print("=   2.pop(取出)                              =");  
    print("=   3.結束                                   =");    
    print("==============================================");
#將資料加入堆疊
def Push():
    global Top            #Top紀錄目前堆疊頂端的索引值，初始值設為-1表示堆疊為空
    while True:
        item =input("請輸入你要push(加入)的資料 (按 ENTER 返回主選單) ：")
        if item=="": break
        if(Top == MaxNum-1):
          print("堆疊是滿的!")
        else:
          Top=Top+1
          Stack[Top] = item       

#取出堆疊資料
def Pop():
    global Top            #Top紀錄目前堆疊頂端的索引值，初始值設為-1表示堆疊為空
    strTmep=""
    while True:
     if(Top == -1): 
       print("堆疊是空的!")
     else:
       strTmep= Stack[Top]
       Top= Top-1
       print("%s 是從堆疊 POP(彈、取出)的資料" % strTmep)
     # input("請按任意鍵返回主選單") 
     break          
    
while True:
    menu()
    choice = int(input("請輸入您的選擇："))
    print()
    if choice==1:
        Push()          #將資料加入堆疊
    elif choice==2:
        Pop()           #取出堆疊資料
    elif choice==3:
         break     
print("程式執行完畢！")

4-3 堆疊在運算式上的應用

一、中序(Infix)表示法： A+B

二、前序(prefix)表示法： +AB

三、後序(postfix)表示法： AB-

後序表示式又稱為逆向波蘭表示式（reverse polish notation），是由波蘭的數學家盧卡謝維奇提出。

範例 4.2

'''

This is ch4-2.1.ipynb by 羅老師 on 2023/03/27

要處理 Stack 堆疊在運算式上的應用

想想 IPO ......

想想 演算法

'''

def priority(op):
    return 1 if op in "+-" else 2 if op in "*/" else 0
    
def toPostfix(infix, isPost = True):
    toStack, toOutput = ('(', ')') if isPost else (')', '(')
    
    def procOpt(c, stack, output):
        if stack == "" or priority(stack[-1]) < priority(c):
            return (stack + c, output)
        else:
            return procOpt(c, stack[0:-1], output + stack[-1])
    
    def procPhs(stack, output):
        if stack[-1] == toStack:
            return (stack[0:-1], output)
        else:
            return procPhs(stack[0:-1], output + stack[-1])
            
    def procExpr(expr, stack = "", output = ""):
        if expr == "":
            return output + stack[::-1]
        elif expr[0] == toStack:
            return procExpr(expr[1:], stack + expr[0], output)
        elif expr[0] in "+-*/":
            return procExpr(expr[1:], *procOpt(expr[0], stack, output))
        elif expr[0] == toOutput:
            return procExpr(expr[1:], *procPhs(stack, output))
        else:
            return procExpr(expr[1:], stack, output + expr[0])
    
    output = procExpr(infix if isPost else infix[::-1])
    return output if isPost else output[::-1]

def toPrefix(infix):
    return toPostfix(infix, False)
    
infix = "(a+b)*(c+d)"
print('原運算式的中序 infix 是：', infix)
print('中序 infix 轉 後序 postorder 是：')
print(toPostfix(infix))
print('中序 infix 轉 前序 preorder 是：')
print(toPrefix(infix))

4-4 堆疊在遞迴 (Recursion)上的應用

1. n 階乘 (!)
2. 費氏數列
3. 最大公因數
4. 河內塔 (Hanoi Tower)問題

範例 4.3

'''
This is ch4-3.1.ipynb by 羅老師 on 2024/03/27
計算 Fibonacci(費氏數) 
想想 IPO ......
想想 演算法
'''
print("===============程式描述========================")
print("= 程式名稱：ch4-3.1.ipynb                        =")
print("= 程式目的：計算Fibonacci(費氏數)              =")
print("==============================================")
#遞迴函式名稱
def Fib(N):  
   print("現在進遞迴函式的是:", N)
   if (N <=2):
     return 1
   else:
     return Fib(N-1) + Fib(N - 2) #函式自己又可以呼叫自己

N = int(input("請輸入費氏數值項次："))
print("呼叫遞迴函式中 ......")
Sum = Fib(N)            #呼叫遞迴函式
print("結束呼叫遞迴函式")
print("N=%2d 時的費氏數=%3d" %(N,Sum)) 

範例 4.4

'''
This is ch4-4.1.ipynb by 羅老師 on 2023/03/27
計算河內塔問題
想想 IPO ......
想想 演算法
'''
print("===============程式描述========================")
print("= 程式名稱：ch3-6.4.py                        =")
print("= 程式目的：計算河內塔問題                     =")
print("==============================================")
#遞迴函式名稱
def Towers(N,From,Through,To): 
 if (N > 0):
    Towers (N - 1, From, To, Through)
    print("將盤子%d從柱子%s移到柱子%s" %( N, From, To))
    Towers (N - 1, Through, From, To)
print("===================輸入======================")
N = int(input("請輸入盤子個數N="))
print("===================輸出======================")
Towers (N,'A','B','C')

Ex4-1.
請修改範例 4-1
(1) 讓使用者輸入陣列個數
(2) 每次 PUSH 或 POP 後印出目前 Stack 的狀態

Ex4-2.
請練習各種不同的運算式轉換

中序(Infix)、前序(prefix)、後序(postfix)

Ex4-3.
請參考修改範例 4-3 & 4-4
(1) 寫一個程式處理 n 階乘 (!) (單號同學)

(2) 寫一個程式處理 最大公因數 (雙號同學)

補充資料：

Stack (CH03)

Reference:
http://alrightchiu.github.io/SecondRound/stack-introjian-jie.html
https://www.geeksforgeeks.org/stack-in-python/

一、以 array 實作 stack　

# This is ch3-2.py by XXXX YYYYY on 2020/05/01
# This is program 處理 堆疊 (stack)
# 程式內的前兩行務必註明:學號、姓名、題號，及用途

print("===============程式描述========================")
print("= 程式名稱：ch3-2.py                          =")
print("= 程式目的：使用堆疊進行push以及pop            =")
print("==============================================")
MaxNum=5           #定義堆疊大小
Stack=['','','','','']  #以陣列Stack當作堆疊
Top =-1
def menu():
    print("==============================================");
    print("=   1.push(加入)                             =");
    print("=   2.pop(取出)                              =");  
    print("=   3.結束                                   =");    
    print("==============================================");

#將堆疊資料印出
def Prt_stack():
    strTemp2=""
    global Top            #Top紀錄目前堆疊頂端的索引值，初始值設為-1表示堆疊為空
    if(Top == -1):
          print("堆疊目前是空的!")
    else:
      for i in range(Top,-1,-1):
        strTemp2=strTemp2 + Stack[i] + ','
      print("堆疊目前的資料： ")
      print(strTemp2)

def Push():
    global Top            #Top紀錄目前堆疊頂端的索引值，初始值設為-1表示堆疊為空
    while True:
        print("(若不 push 則 直接按 ENTER 即可)")
        item =input("請輸入你要push(加入)的資料：")
        if item=="": break
        if(Top == MaxNum-1):
          print("堆疊是滿的!")
          break
        else:
         Top=Top+1
         Stack[Top] = item      

#取出堆疊資料
def Pop():
    global Top            #Top紀錄目前堆疊頂端的索引值，初始值設為-1表示堆疊為空
    strTmep=""
    while True:
     if(Top == -1): 
       print("堆疊是空的!")
     else:
       strTmep=Stack[Top]
       print("%s 是從堆疊彈pop(取出)的資料" % strTmep)
       Top=Top-1
     # input("請按任意鍵返回主選單") 
     break          
    
while True:
    menu()
    Prt_stack()
    choice = int(input("請輸入您的選擇："))
    print()
    if choice==1:
        Prt_stack()
        Push()          #將資料加入堆疊
    elif choice==2:
        Prt_stack()
        Pop()           #取出堆疊資料
    elif choice==3:
         Prt_stack()
         break     
    else:
      break
      print("程式執行完畢！")

# ##########################################################################################

二、Stack Class 實作
1. Stack Class 實作 A
# Stack Class 實作 A

class Stack:
    def __init__(self):
        self.items = []
 # self 為物件本身的例子 (instance)
 # The __init__ method is roughly what represents a constructor in Python. 
 # When you call A()   'A 為一個類別 (class )
 # Python creates an object for you, and passes it as the first parameter to the __init__ method. 
 # Any additional parameters (e.g., A(24, 'Hello')) will also get passed as arguments
 # --in this case causing an exception to be raised, since the constructor isn't expecting them.

    def is_empty(self):
        return self.items == []
 
    def push(self, data):
        self.items.append(data)
 
    def pop(self):
        return self.items.pop()
 
s = Stack()
while True:
    print('push <value>(數值)')
    print('pop')
    print('quit')
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'push':
       s.push(int(do[1]))
    elif operation == 'pop':
        if s.is_empty():
            print('Stack is empty.')
        else:
            print('Popped value: ', s.pop())
    elif operation == 'quit':
        break

# ##########################################################################################

2. Stack Class 實作 B

# This is ch03-stack-class.py by 0000000XXX (學號)  YYYYYY(姓名) on 2020/05/15
# This is   stack class 的實作
# 程式的前兩行務必註明：學號、姓名、題號、及用途
# Stack(堆疊)是一種概念性的抽象資料結構，可以分別使用Array(陣列)與Linked list(連結串列)來實作。

# In the fololowing code, we have defined one list called items inside the Constructor.
# 以下程式碼在其建構子 (Constructor) 中定義一個 list 名稱叫做 items

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)    # 將 item 加入 list 中

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)

dataStack = Stack()  # 宣告一個 Stack 類別的物件 (例)
dataStack.push('AAA') # 呼叫 push 方法，在參數中傳一個 item
dataStack.push('BBB')
dataStack.push('CCC')
print('\n 目前　stack 的元素有', dataStack.size(), '個:') 
print(dataStack.items) # 印出 list

i= dataStack.size()
while (i>0):    # 一直 pop 元素至 Stack 為空
  print('\n stack pop 出的元素:', dataStack.pop())
  print('\n 目前　stack 的元素有', dataStack.size(), '個:')
  print(dataStack.items) # 印出 list
  i= dataStack.size()

# ##########################################################################################

三、Stack Class 及其效率考量
(Sources: https://www.coderbridge.com/@ninja-ja/889274a4faa84b639d8e239eed6acb16)

題目: Min Stack

原始題目如下:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

簡單說就是要實作一個 stack 但是可以支援找到當前 stack 中最小值的功能。
因為基本的 stack 的實作可以直接使用 Array，所以剩下的就是提供找到 Array 中最小值的功能。
有些程式語言有提供回傳 Array 中最小值的功能，可以直接使用。

解法 1 (Python 3)

class MinStack:      def __init__(self):         """         initialize your data structure here.         """         self.stack = []      def push(self, x: int) -> None:         self.stack.append(x)      def pop(self) -> None:         self.stack.pop()      def top(self) -> int:         return self.stack[-1]      def getMin(self) -> int:         return min(self.stack)  # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

上面這個解法很直觀的使用 python list 內建的 append, pop 函式來實作 stack。
至於 getMin 的實作是使用內建的 min 函式。
要注意的是 min 函式的時間複雜度是 O(n)，基本上如果沒有先經過特殊處理(如: 排序)，在 array 中尋找最小元素的時間複雜度都是 O(n)。

解法 2 (Python 3)

那我們有辦法加快速度嗎?
這時候我們可以把 stack 中各種元素的存在的情況視為一種狀態 (state)，然後把各種狀態的最小元素直接存下來。

例如當 stack 是 [3] 的時候最小元素是 3。
當再 push 2 到 stack 中，stack 是 [3, 2] 的時候最小元素是 2。
當再 push 3 到 stack 中，stack 是 [3, 2, 3] 的時候最小元素是 2。
所以我們可以把 stack 在各個不同狀態的最小元素值，以上面的例子來說，分別是 3, 2, 2，存起來，當呼叫 getMin 的時候直接回傳。

因為 stack 在不同長度時會對應到不同的狀態，所以我們會需要使用一個和 stack 一樣長度的 Array 來儲存這些不同狀態的最小值。這個 Array 的長度會和 stack 長度一起變化。

class MinStack:      def __init__(self):         """         initialize your data structure here.         """         self.stack = []         self.min_states = []      def push(self, x: int) -> None:         self.stack.append(x)         self.min_states.append(min(x, self.min_states[-1]) if self.min_states else x)      def pop(self) -> None:         self.stack.pop()         self.min_states.pop()      def top(self) -> int:         return self.stack[-1]      def getMin(self) -> int:         return self.min_states[-1]  # 直接回傳當前 stack (某個 state) 的最小元素  # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

經過這樣的修改，getMin 函式的時間複雜度變成 O(1)。不過要注意的是因為需要多儲存一個不同狀態最小值的 list，整個程式的記憶體用量多了一倍。

這個是典的用空間換取時間的例子。在實務上，在一些效能要求很高的系統中，這是一種很常見的手法來提高系統的效率。如果這個函式常常被使用到的話，這樣的設計或許就很划算。

四、使用 list 實作 stack

# This is ch03-stack-list.py by 0000000XXX (學號) YYYYYY(姓名) on 2020/05/15

# This is 使用 list 展示 stack 的實作

# 程式的前兩行務必註明：學號、姓名、題號、及用途

# Stack(堆疊)是一種概念性的抽象資料結構，可以分別使用Array(陣列)與Linked list(連結串列)來實作。

import datetime # 引入時間日期模組

today = datetime.date.today()

print ("Hello, 現在是", today)

print ("我是學號 0000000XXX YYYYYY(姓名) 在學習 data structure\n\n")

stack = []

# append() function to push element into the stack

stack.append('a')

stack.append('b')

stack.append('c')

print('目前 stack 的元素 (Initial stack):')

print(stack)

# pop() fucntion to pop element from the stack

# LIFO order

print('\n 從 stack pop 出的元素 (Elements poped from stack):')

print(stack.pop())

print('\n stack 所有的元素均已 pop 出 (Stack after elements are poped):')

print(stack)

# uncommenting print(stack.pop())

# will cause an IndexError

# as the stack is now empty
# ##########################################################################################

五、、使用 deque 實作 stack [download]

# This is ch03-stack-list.py by 0000000XXX (學號)  YYYYYY(姓名) on 2020/05/15
# This is 使用 collections deque 展示  stack 的實作
# 程式的前兩行務必註明：學號、姓名、題號、及用途
# Stack(堆疊)是一種概念性的抽象資料結構，可以分別使用Array(陣列)與Linked list(連結串列)來實作。

import datetime # 引入時間日期模組
today = datetime.date.today()
print ("Hello, 現在是", today)
print ("我是 學號 0000000XXX  YYYYYY(姓名) 在學習 data structure- deque 實作 stack \n\n")

# Python program to  
# demonstrate stack implementation 
# using collections.deque 
   
from collections import deque 
  
stack = deque() 

print('初始的 stack (Initial stack):') 
print(stack)
print('\n') 

# append() function to push 
# element in the stack 
stack.append('a') 
stack.append('b') 
stack.append('c') 
  
print('目前 stack 的元素 (Initial stack):') 
print(stack) 
  
# pop() fucntion to pop 
# element from stack in  
# LIFO order
print('\n 從 stack pop 出的元素 (Elements poped from stack):')  
print(stack.pop()) 
print(stack.pop()) 
print(stack.pop()) 
  
print('\n stack 所有的元素 均已 pop 出 (Stack after elements are poped):') 
print(stack) 
  
# uncommenting print(stack.pop())   
# will cause an IndexError  
# as the stack is now empty 
# ##########################################################################################

六、應用
A. 遞迴 (recursive)的應用程式例
1. n 階層 (n!) ch3-6.1.py
2. 費氏數列 (Fibonacci Numbers)   ch3-6.1.py ch3-6.2.py
3. 最大公因數 (GCD)   ch3-6.3.py
4. 河內塔問題 (Hanoi Tower)   ch3-6.4.py

B. 一般應用
Stack最主要的功能是「記得先前的資訊」，所以時常用來處理需要「回復到先前的狀態」的問題，也稱為Back-Tracking問題，例如：

編輯器(如word、sublime等等)中的undo。
網頁瀏覽器的「回到前一頁」功能。
編譯器(compiler)中的Parsing。
- 參考：Compiler Design - Top-Down Parser。
任何遞迴(recursion)形式的演算法，都可以用Stack改寫，例如Depth-First Search(DFS，深度優先搜尋)。
- 參考：GeeksforGeeks:Iterative Depth First Traversal of Graph。
- 因為遞迴(recursion)使用了系統的Call Stack。
於記憶體管理(memory management)中的Call Stack。
- 參考：Wikipedia：Call stack。
- 參考：Stack Overflow：What and where are the stack and heap?

全部共 9則留言

周育賢03-20 11:30:

MaxNum =int(input("請輸入Stack(輸入陣列個數)你要的個數：")) # MaxNum=5 #定義堆疊大小

張金寶04-10 10:27:

https://colab.research.google.com/drive/14qxbKCPoKKagtApwCD0JfV9vNBfo-tmv

04-23 13:28:

https://colab.research.google.com/drive/1HguK22lGM89oQLu2b73KMlJehSgOcYDr

04-23 13:32:

https://colab.research.google.com/drive/1HguK22lGM89oQLu2b73KMlJehSgOcYDr

04-23 13:41:

https://colab.research.google.com/drive/1HguK22lGM89oQLu2b73KMlJehSgOcYDr#scrollTo=N5s-vt8Qmcns

04-23 13:46:

https://colab.research.google.com/drive/1_ccwCPARUE2Sx-m4GIpqA81cFCkIe0p6

周育賢06-26 10:56:

4-1https://colab.research.google.com/drive/1AoMXU3Vrc1MEF9C291lcKBRhezJkn6pW

周育賢06-26 10:57:

4-3https://colab.research.google.com/drive/1CsUTnHgn5BR1YtGUj0zqaBYfUBmPB2CD

張金寶06-27 10:36:

https://colab.research.google.com/drive/1c628SFKBVqguKoj6r2PScRVP05w68JGx#scrollTo=JwInPgzGDplU

登入帳號密碼代表遵守學術網路規範

文章分類 Labels

最新文章 Top10