本文实例讲述了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指向下一个节点
发现队列或栈其实都需要找到一个节点，需要找到你现在的位置，
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#给一个点，我们能够根据这个点知道一些内容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() |
打印的效果
|
1
2
3
|
321 |
应用：
数制转换：
1. 硬编码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#--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 "转换为八进制：" + string8 |
2. 构建stack类，来实现
Stack1.py
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#--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
|
1
2
3
4
5
6
7
8
9
10
11
|
#--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 |
括号匹配
硬编码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#--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程序设计有所帮助。
原文链接：http://www.cnblogs.com/chongyou/p/7099692.html
