Python棧算法的實現(xiàn)與簡單應用示例

更新時間：2017年11月01日 11:49:46 作者：做夢的人-

這篇文章主要介紹了Python棧算法的實現(xiàn)與簡單應用,簡單講述了棧的原理并結合實例形式給出了基于棧實現(xiàn)的進制轉換與括號匹配等相關使用技巧,需要的朋友可以參考下

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

原理：

棧作為一種數(shù)據(jù)結構，是一種只能在一端進行插入和刪除操作。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）

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

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

實例屬性：self.top，要先找到一個標點，或者是能夠定位的一個點，作為一個基準

實例方法：

1、入棧

把node.next=top 把入棧的節(jié)點，給一個top
top=node #節(jié)點進來后，就是這個節(jié)點返回給
返回top的value

2、出棧

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

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

應用：

數(shù)制轉換：

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

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

2. 構建stack類，來實現(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("請輸入一個十進制數(shù)字::")
while (temp):
  shiyan.push(temp % 8)
  temp = temp / 8
while (not shiyan.isEmpty()):
  stringu += str(shiyan.pop())
print "八進制為：：" + stringu

括號匹配

硬編碼實現(xiàn)

#--coding:utf-8--
print "  ****括號匹配****  "
print """
輸入原則： 每當你輸入一個括號， 你需要再輸入一個‘，'
進行區(qū)分， 例如：(, [, ], (, ), )
輸入的可識別括號有(), [], {}
"""
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 "右括號多余"
        break
if len(pstack) == 0:
  print "匹配正確"
else :
  print "左括號多余"

更多關于Python相關內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》

希望本文所述對大家Python程序設計有所幫助。

您可能感興趣的文章: