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

歷程檔案 Portfolio

堆疊 Stack

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?

全部共 0則留言

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

文章分類 Labels

最新文章 Top10