資料結構與算法：python語言描述之堆棧

1、形象表述

堆棧常用來存儲資料，它遵循後入先出（last-in rst-out (LIFO)）的規則。

下面這張圖形象的描述了進棧、出棧的過程：

（a）:把數值19壓進棧,（b）:把數值5壓進棧

（c）:把值19和5壓進棧後産生的堆棧

（d）：出棧，從棧頂彈出

2、python實作

對棧我們定義了一些操作函數：

1. Stack（）：建立一個新的空棧
2. isEmpty（）：判斷是否空棧，傳回布爾數值
3. length（）：傳回棧的長度
4. push（item）：元素進棧
5. pop(）：在堆棧非空的情況下，棧頂元素出棧
6. peek（）：傳回棧頂元素，如果堆棧為空，傳回錯誤。

在定義peek()函數時，我們用了斷言assert,它的用法：

assert 表達式1，表達式2

如果表達式為真，程式繼續執行，不發生中斷；

如果表達式1為假，中斷程式，并報錯，輸出表達式2。

堆棧的程式很簡單，你不用害怕，你一看就明白了。

具體程式：

應用python清單來實作堆棧
class Stack:
    #建立一個空棧
    def __init__(self):
        self._theItems = list()
    #判斷棧是空的；如果棧是空的傳回True，其他的傳回False
    def isEmpty(self):
        return len(self) == 0
    #棧的長度
    def __len__(self):
        return len(self._theItems)
    #進棧
    def push(self,item):
        self._theItems.append(item)
    #出棧
    def pop(self):
        #如果棧是空的，用斷言assert使程式中斷
        assert not self.isEmpty(),'Cannot pop from an empty stack'
        return self._theItems.pop()
    #在不删除棧頂元素的情況下，傳回棧頂元素
    def peek(self):
        assert not self.isEmpty(),'Cannot pop from an empty stack'
        return self._theItems[-1]
           

3、堆棧的應用

這是一個用字尾表達式計算數值的例子，可以先忽略。

operators = {  # 運算符操作表
    '+': lambda op1, op2: op1 + op2,
    '-': lambda op1, op2: op1 - op2,
    '*': lambda op1, op2: op1 * op2,
    '/': lambda op1, op2: op1 / op2,
}
def evalPostfix(list1):
    tokens = list1.split()  
    stack = []
    for token in tokens: 
        if token.isdigit():  
            stack.append(int(token))  
        elif token in operators.keys():  
            f = operators[token]  
            op2 = stack.pop()  
            op1 = stack.pop()  
            stack.append(f(op1, op2))  
    return stack.pop()