Python棧算法的實(shí)現(xiàn)與簡(jiǎn)單應(yīng)用示例

本文實(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ù)脑?br />     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 tmp
if __name__=="__main__":
  s=stack()
  s.push(1)
  s.push(2)
  s.push(3)
  print s.pop()
  print s.pop()
  print s.pop()

打印的效果    
3
2
1

應(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 //8
while (len(stack) > 0):
  string8 += str(stack.pop())
print "轉(zhuǎn)換為八進(jìn)制：" + string8

2. 構(gòu)建stack類，來(lái)實(shí)現(xiàn)

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):
    return
self.items[len(self.items) - 1]

moshi.py
    
#--coding: utf - 8--
import stack1
shiyan = stack1.Stack()
stringu = ""
temp = input("請(qǐng)輸入一個(gè)十進(jìn)制數(shù)字::")
while (temp):
  shiyan.push(temp % 8)
  temp = temp / 8
while (not shiyan.isEmpty()):
  stringu += str(shiyan.pop())
print "八進(jìn)制為：：" + stringu

括號(hào)匹配

硬編碼實(shí)現(xiàn)    
#--coding:utf-8--
print "  ****括號(hào)匹配****  "
print """
輸入原則： 每當(dāng)你輸入一個(gè)括號(hào)， 你需要再輸入一個(gè)‘，'
進(jìn)行區(qū)分， 例如：(, [, ], (, ), )
輸入的可識(shí)別括號(hào)有(), [], {}
"""
strpp = raw_input("請(qǐng)輸入一段括號(hào)表達(dá)式：")
basestr = strpp.split(',')
pstack = []
suoyin = {'(': ')','[': ']','{': '}'}
for e in basestr:
  if (e == '(' or e == '[' or e == '}'):
    pstack.append(e)
  else :
    if len(pstack) == 0:
      print "右括號(hào)多余"
      break
    else :
      if e == suoyin[pstack[len(pstack) - 1]]:
        pstack.pop()
      else :
        print "不匹配"
        print "右括號(hào)多余"
        break
if len(pstack) == 0:
  print "匹配正確"
else :
  print "左括號(hào)多余"