本文實例講述了Python棧算法的實現與簡單應用。分享給大家供大家參考，具體如下：
原理：
棧作為一種數據結構，是一種只能在一端進行插入和刪除操作。它按照先進后出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最后一個數據被第一個讀出來）
桟的應用場景非常多：1、內存管理中使用的堆棧；2、基于桟實現的二叉樹的遍歷；3、在語言處理中，符號的平衡問題，在語言中，往往很多符號是成對出現的，比如<>,{},[],()等，如何判斷符號是否漏了，一種實現方式就是：假設在讀入一串字符串以后，如果遇到對稱符號的左邊部分，則將其壓入棧中，當遇到對稱符號的右邊部分，則彈出棧中的一個對象，如果所有的符號都是平衡的，棧中此時應該就是為空，通過判斷棧中是否為空，說明字符串是否是符號平衡的。
在桟的設計中，我們需要定義一個實例屬性top。三個實例方法：獲取棧頂元素peek()；出桟pop()；入棧push()
實例屬性：self.top，要先找到一個標點，或者是能夠定位的一個點，作為一個基準
實例方法：
1、入棧
把node.next=top 把入棧的節點，給一個top
top=node #節點進來后，就是這個節點返回給
返回top的value
2、出棧
1）是否是空棧，是的話，返回None
2）否則，返回top.value，并且top指向下一個節點
發現隊列或棧其實都需要找到一個節點，需要找到你現在的位置，
#給一個點，我們能夠根據這個點知道一些內容class Node(object): def __init__(self): #定位的點的值和一個指向 self.val=val #指向元素的值,原隊列第二元素 self.next=None #指向的指針class stack(object): def __init__(self): self.top=None #初始化最開始的位置 def peek(self): #獲取棧頂的元素 if self.top!=None: #如果棧頂不為空 return self.top.val #返回棧頂元素的值 else: return None def push(self,n):#添加到棧中 n=Node(n) #實例化節點 n.next=self.top #頂端元素傳值給一個指針 self.top=n # return n.val def pop(self): #退出棧 if self.top == None: return None else: tmp=self.top.val self.top=self.top.next #下移一位，進行 return tmpif __name__=="__main__": s=stack() s.push(1) s.push(2) s.push(3) print s.pop() print s.pop() print s.pop()
打印的效果
321
應用：
數制轉換：
1. 硬編碼實現
#--coding: utf - 8--"""N = input("Please input a number::")while (N): print "** @ **" N -= 1 """N = input("輸入十進制數字（換算為八進制）：：")stack = []string8 = ""while (N): #求余 stack.append(N % 8)# 求商 N = N //8while (len(stack) > 0): string8 += str(stack.pop())print "轉換為八進制：" + string82. 構建stack類，來實現
Stack1.py
#--coding: utf - 8--class Stack(object): def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def GetTop(self): returnself.items[len(self.items) - 1]
moshi.py
#--coding: utf - 8--import stack1shiyan = stack1.Stack()stringu = ""temp = input("請輸入一個十進制數字::")while (temp): shiyan.push(temp % 8) temp = temp / 8while (not shiyan.isEmpty()): stringu += str(shiyan.pop())print "八進制為：：" + stringu括號匹配
硬編碼實現
#--coding:utf-8--print " ****括號匹配**** "print """輸入原則： 每當你輸入一個括號， 你需要再輸入一個‘，'進行區分， 例如：(, [, ], (, ), )輸入的可識別括號有(), [], {}"""strpp = raw_input("請輸入一段括號表達式：")basestr = strpp.split(',')pstack = []suoyin = {'(': ')','[': ']','{': '}'}for e in basestr: if (e == '(' or e == '[' or e == '}'): pstack.append(e) else : if len(pstack) == 0: print "右括號多余" break else : if e == suoyin[pstack[len(pstack) - 1]]: pstack.pop() else : print "不匹配" print "右括號多余" breakif len(pstack) == 0: print "匹配正確"else : print "左括號多余"希望本文所述對大家Python程序設計有所幫助。
新聞熱點
疑難解答
