首页 > 代码库 > 数据结构[Python--Stack] 的应用
数据结构[Python--Stack] 的应用
难得有些许空闲，看一下Python的数据结构--Stack，现将几个典型示例进行总结！
一、什么是栈
栈是一个有序集合，根据其特性可以称为"先进后出"或"后进先出", 其中添加或删除都发生在同一端，这一端被称为"栈顶"，与其对应的叫"栈底"。
栈的底部很重要，因为其底部存储的数据是时间最长的，最近的添加项总是最先会弹出，这种排序原则有时被称为"LIFO"
二、栈
1. 栈的可用操作
Stack()创建一个空的新栈。 它不需要参数，并返回一个空栈。push(item)将一个新项添加到栈的顶部。它需要item做参数并不返回任何内容。pop()从栈中删除顶部项。它不需要参数并返回item。栈被修改。top()从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。isEmpty()测试栈是否为空。不需要参数，并返回布尔值。size()返回栈中的item数量。不需要参数，并返回一个整数。clear清空栈，没有返回值
2. 利用Python 的内置的数据结构List实现栈全部操作
class Stack(): def __init__(self): self.itmes = [] def isEmpty(self): return self.itmes == [] def clear(self): del self.itmes[:] def push(self, item): self.items.append(item) def pop(self): return self.itmes.pop() def top(self): return self.items[-1] def size(self): return len(self.itmes)
3. 栈的使用示例
3.1 进制转换
class Stack(): def __init__(self): self.itmes = [] def isEmpty(self): return self.itmes == [] def clear(self): del self.itmes[:] def push(self, item): self.items.append(item) def pop(self): return self.itmes.pop() def top(self): return self.items[-1] def size(self): return len(self.itmes) def divideBy2(decNumber, base): remstack = Stack() while decNumber > 0: rem = decNumber % base remstack.push(rem) decNumber = decNumber // base binString = "" while not remstack.empty(): binString = binString + str(remstack.pop()) return binString if __name__ == ‘__main__‘: print(divideBy2(42, 2))
说明： 这是用List结构来实现的"栈", 同样我们可以自己写一个栈
3.2 自己写栈
class Node: def __init__(self, value): self.value = value self.next = None class Stack: def __init__(self): self.top = None def push(self, value): node = Node(value) node.next = self.top self.top = node def pop(self): node = self.top self.top = node.next return node.value s = Stack() s.push(3) s.push(‘ac‘) s.push(‘er‘) s.pop() s.push(5)
说明
上面所定义的栈，是由top指针指向一个完整的Node实例
定义一个栈，使用指针控制其读取的位置。
3.3 栈应用--前缀表达式(波兰式)
from __future__ import division
class Node():
def __init__(self, value):
self.value = value
self.next = None
class StackNode():
def __init__(self):
self.top = None
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
def pop(self):
node = self.top
self.top = node.next
return node.value
def compute_exec(op, ov1, ov2):
def add(ov1, ov2):
return ov1 + ov2
def sub(ov1, ov2):
return ov1 - ov2
def mul(ov1, ov2):
return ov1 * ov2
def div(ov1, ov2):
return ov1 / ov2
ops = {add: ‘+‘, sub: ‘-‘, mul: ‘*‘, div: "/"}
for k, v in ops.items():
if v == op:
ret = k(ov1, ov2)
stack1.push(ret)
break
def perfix_reverse(string): # reverse
tmp = ‘‘
for s in string[::-1]:
if s == "(":
tmp += ")"
elif s == ")":
tmp += "("
else:
tmp += s
return tmp
def infix_to_prefix(string):
opt = ‘‘
string_tmp = perfix_reverse(string)
for i in string_tmp: # 前缀表达式
if i.isdigit():
opt = i + opt
elif i != ‘)‘:
stack1.push(i)
elif i == ")":
opt = stack1.pop() + opt
stack1.pop()
for s in opt[::-1]:
if s.isdigit():
stack1.push(s)
else:
op1 = s
ov1 = stack1.pop()
ov2 = stack1.pop()
compute_exec(op1, int(ov1), int(ov2)) # compute result
continue
return opt, stack1.pop()
if __name__ == ‘__main__‘:
stack1 = StackNode() # 操作符
infix = [‘((3+4)*2)‘, ‘((3+(4*2))-1)‘, ‘(5*(1+2))‘]
for i, v in enumerate(infix):
print infix[i], "==>", infix_to_prefix(v)说明：
前缀表达式就是说操作符位于操作数之前
表达式从右向左依次解析。将数值压栈，遇到符号将栈顶的操作数与次位置弹出进行计算，结果再次入栈，直到表达式解析完成。
3.4 栈应用--后缀表达式（逆波兰式）
class Node():
def __init__(self, value):
self.value = value
self.next = None
class StackNode():
def __init__(self):
self.top = None
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
def pop(self):
node = self.top
self.top = node.next
return node.value
def compute_exec(op, ov1, ov2):
def add(ov1, ov2):
return ov1 + ov2
def sub(ov1, ov2):
return ov1 - ov2
def mul(ov1, ov2):
return ov1 * ov2
def div(ov1, ov2):
return ov1 / ov2
ops = {add: ‘+‘, sub: ‘-‘, mul: ‘*‘, div: "/"}
for k, v in ops.items():
if v == op:
ret = k(ov1, ov2)
stack1.push(ret)
break
def postfix(expr):
for s in expr:
if s.isdigit():
stack2.push(s)
elif s != ")":
stack1.push(s)
elif s == ")":
top = stack2.pop()
snext = stack2.pop()
stack2.push(‘‘.join([snext, top, stack1.pop()]))
stack1.pop()
post_expr = stack2.pop()
for i in post_expr:
if i.isdigit():
stack1.push(i)
else:
op = i
top = stack1.pop()
snext = stack1.pop()
compute_exec(op, int(snext), int(top))
return post_expr, stack1.pop()
if __name__ == ‘__main__‘:
stack1 = StackNode() # 操作符
stack2 = StackNode() # 操作数
exprs = [‘((3+(4*2))-1)‘, ‘((3*4)+(3/2))‘]
for e in exprs:
print e, "==>", postfix(e)说明:
后缀表达式就是说操作符位于操作数之后。
表达式从左向右依次解析。将数值压栈，遇到符号将栈顶的操作数与次位置弹出进行计算[次位操作数 栈顶操作数 操作符 ]，结果再次入栈，直到表达式解析完成
计算表达式结果时同样是[次位操作数 操作符 栈顶操作数 ]
四、总结
以上示例都可以通过http://pythontutor.com/visualize.html#mode=edit 查看程序运行的每一步
本文参考于https://www.gitbook.com/book/facert/python-data-structure-cn/details
以上后两个示例代码基于自己理解所写，可能存在bug
后两个示例的缺点是没有写表达式合法性的检查，表达式的优先级（如表达式无括号可能会导致程序异常）
此处仅是对栈的一此粗浅理解及应用。
本文出自 “和风细雨” 博客，请务必保留此出处http://essun.blog.51cto.com/721033/1941041
数据结构[Python--Stack] 的应用