Python栈算法的实现与简单应用示例_Python

本文实例讲述了Python栈算法的实现与简单应用。分享给大家供大家参考，具体如下：

原理：

栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）

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 tmp

									if __name__=="__main__":

									  s=stack()

									  s.push(1)

									  s.push(2)

									  s.push(3)

									  print s.pop()

									  print s.pop()

									  print s.pop()

打印的效果

应用：

数制转换：

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 //8

									while (len(stack) > 0):

									  string8 += str(stack.pop())

									print "转换为八进制：" + string8

2. 构建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):

									    return

									self.items[len(self.items) - 1]

moshi.py

									#--coding: utf - 8--

									import stack1

									shiyan = stack1.Stack()

									stringu = ""

									temp = input("请输入一个十进制数字::")

									while (temp):

									  shiyan.push(temp % 8)

									  temp = temp / 8

									while (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 "右括号多余"

									        break

									if len(pstack) == 0:

									  print "匹配正确"

									else :

									  print "左括号多余"