本文實(shí)例講述了Python棧算法的實(shí)現(xiàn)與簡(jiǎn)單應(yīng)用。分享給大家供大家參考，具體如下：

原理：

棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作。它按照先進(jìn)后出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái)）

桟的應(yīng)用場(chǎng)景非常多：1、內(nèi)存管理中使用的堆棧；2、基于桟實(shí)現(xiàn)的二叉樹(shù)的遍歷；3、在語(yǔ)言處理中，符號(hào)的平衡問(wèn)題，在語(yǔ)言中，往往很多符號(hào)是成對(duì)出現(xiàn)的，比如<>,{},[],()等，如何判斷符號(hào)是否漏了，一種實(shí)現(xiàn)方式就是：假設(shè)在讀入一串字符串以后，如果遇到對(duì)稱符號(hào)的左邊部分，則將其壓入棧中，當(dāng)遇到對(duì)稱符號(hào)的右邊部分，則彈出棧中的一個(gè)對(duì)象，如果所有的符號(hào)都是平衡的，棧中此時(shí)應(yīng)該就是為空，通過(guò)判斷棧中是否為空，說(shuō)明字符串是否是符號(hào)平衡的。

在桟的設(shè)計(jì)中，我們需要定義一個(gè)實(shí)例屬性top。三個(gè)實(shí)例方法：獲取棧頂元素peek()；出桟pop()；入棧push()

實(shí)例屬性：self.top，要先找到一個(gè)標(biāo)點(diǎn)，或者是能夠定位的一個(gè)點(diǎn)，作為一個(gè)基準(zhǔn)

實(shí)例方法：

1、入棧

把node.next=top 把入棧的節(jié)點(diǎn)，給一個(gè)top
top=node  #節(jié)點(diǎn)進(jìn)來(lái)后，就是這個(gè)節(jié)點(diǎn)返回給
返回top的value

2、出棧

1）是否是空棧，是的話，返回None
2）否則，返回top.value，并且top指向下一個(gè)節(jié)點(diǎn)
發(fā)現(xiàn)隊(duì)列或棧其實(shí)都需要找到一個(gè)節(jié)點(diǎn)，需要找到你現(xiàn)在的位置，

#給一個(gè)點(diǎn)，我們能夠根據(jù)這個(gè)點(diǎn)知道一些內(nèi)容class Node(object):  def __init__(self): #定位的點(diǎn)的值和一個(gè)指向    self.val=val  #指向元素的值,原隊(duì)列第二元素    self.next=None  #指向的指針class stack(object):  def __init__(self):    self.top=None #初始化最開(kāi)始的位置  def peek(self): #獲取棧頂?shù)脑?   if self.top!=None: #如果棧頂不為空      return self.top.val #返回棧頂元素的值    else:      return None  def push(self,n):#添加到棧中    n=Node(n) #實(shí)例化節(jié)點(diǎn)    n.next=self.top #頂端元素傳值給一個(gè)指針    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 #下移一位，進(jìn)行      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

應(yīng)用：

數(shù)制轉(zhuǎn)換：

1. 硬編碼實(shí)現(xiàn)

#--coding: utf - 8--"""N = input("Please input a number::")while (N):  print "** @ **"  N -= 1 """N = input("輸入十進(jìn)制數(shù)字（換算為八進(jìn)制）：：")stack = []string8 = ""while (N):  #求余  stack.append(N % 8)# 求商  N = N //8while (len(stack) > 0):  string8 += str(stack.pop())print "轉(zhuǎn)換為八進(jìn)制：" + string8