AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

数据结构[Python--Stack] 的应用

2017-11-22 1322
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

难得有些许空闲，看一下Python的数据结构--Stack，现将几个典型示例进行总结！

一、什么是栈

     栈是一个有序集合，根据其特性可以称为"先进后出"或"后进先出", 其中添加或删除都发生在同一端，这一端被称为"栈顶"，与其对应的叫"栈底"。

    栈的底部很重要，因为其底部存储的数据是时间最长的，最近的添加项总是最先会弹出，这种排序原则有时被称为"LIFO"

二、栈

1. 栈的可用操作

  • Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。

  • push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。

  • pop() 从栈中删除顶部项。它不需要参数并返回item 。栈被修改。

  • top() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。

  • isEmpty()测试栈是否为空。不需要参数，并返回布尔值。

  • size() 返回栈中的item 数量。不需要参数，并返回一个整数。

  • clear 清空栈，没有返回值

2. 利用Python 的内置的数据结构List实现栈全部操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 进制转换

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
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 自己写栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 )

说明

  1. 上面所定义的栈，是由top指针指向一个完整的Node实例

  2. 定义一个栈，使用指针控制其读取的位置。

3.3 栈应用--前缀表达式(波兰式)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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)

说明：

  1. 前缀表达式就是说操作符位于操作数之前

  2. 表达式从右向左依次解析。将数值压栈，遇到符号将栈顶的操作数与次位置弹出进行计算，结果再次入栈，直到表达式解析完成。

3.4 栈应用--后缀表达式（逆波兰式）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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)

说明:

  1.  后缀表达式就是说操作符位于操作数之后。

  2.  表达式从左向右依次解析。将数值压栈，遇到符号将栈顶的操作数与次位置弹出进行计算[次位操作数 栈顶操作数 操作符 ]，结果再次入栈，直到表达式解析完成

  3.  计算表达式结果时同样是[次位操作数 操作符 栈顶操作数 ]


四、总结

  1. 以上示例都可以通过http://pythontutor.com/visualize.html#mode=edit 查看程序运行的每一步

  2. 本文参考于https://www.gitbook.com/book/facert/python-data-structure-cn/details

  3. 以上后两个示例代码基于自己理解所写，可能存在bug

  4. 后两个示例的缺点是没有写表达式合法性的检查，表达式的优先级（如表达式无括号可能会导致程序异常）

  5. 此处仅是对栈的一此粗浅理解及应用。










本文转自 jinlinger 51CTO博客，原文链接：http://blog.51cto.com/essun/1941041，如需转载请自行联系原作者
文章标签：
云解析DNS
Python
关键词：
Python应用
数据结构应用
数据结构Python应用
数据结构python
余二五
目录
相关文章
站大爷
|
6月前
|
监控 数据可视化 数据挖掘
Python Rich库使用指南：打造更美观的命令行应用
Rich库是Python的终端美化利器，支持彩色文本、智能表格、动态进度条和语法高亮，大幅提升命令行应用的可视化效果与用户体验。
站大爷
483 0
蓝易云
|
6月前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示；根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
蓝易云
387 86
sunyalei
|
7月前
|
数据采集 监控 Java
Python 函数式编程的执行效率：实际应用中的权衡
Python 函数式编程的执行效率：实际应用中的权衡
sunyalei
330 102
荔枝科研社
|
6月前
|
机器学习/深度学习 算法 安全
【强化学习应用(八)】基于Q-learning的无人机物流路径规划研究（Python代码实现）
【强化学习应用(八)】基于Q-learning的无人机物流路径规划研究（Python代码实现）
荔枝科研社
420 6
站大爷
|
6月前
|
设计模式 缓存 运维
Python装饰器实战场景解析：从原理到应用的10个经典案例
Python装饰器是函数式编程的精华，通过10个实战场景，从日志记录、权限验证到插件系统，全面解析其应用。掌握装饰器，让代码更优雅、灵活，提升开发效率。
站大爷
414 0
站大爷
|
7月前
|
数据采集 存储 数据可视化
Python网络爬虫在环境保护中的应用：污染源监测数据抓取与分析
在环保领域，数据是决策基础，但分散在多个平台，获取困难。Python网络爬虫技术灵活高效，可自动化抓取空气质量、水质、污染源等数据，实现多平台整合、实时更新、结构化存储与异常预警。本文详解爬虫实战应用，涵盖技术选型、代码实现、反爬策略与数据分析，助力环保数据高效利用。
站大爷
397 0
站大爷
|
7月前
|
存储 程序员 数据处理
Python列表基础操作全解析：从创建到灵活应用
本文深入浅出地讲解了Python列表的各类操作，从创建、增删改查到遍历与性能优化，内容详实且贴近实战，适合初学者快速掌握这一核心数据结构。
站大爷
627 0
站大爷
|
7月前
|
中间件 机器人 API
Python多态实战：从基础到高阶的“魔法”应用指南
Python多态机制通过“鸭子类型”实现灵活接口，使不同对象统一调用同一方法，自动执行各自行为。它简化代码逻辑、提升扩展性，适用于数据处理、策略切换、接口适配等场景。掌握多态思维，能有效减少冗余判断，使程序更优雅、易维护。
站大爷
335 0
站大爷
|
7月前
|
存储 监控 安全
Python剪贴板监控实战：clipboard-monitor库的深度解析与扩展应用
本文介绍了基于Python的剪贴板监控技术，结合clipboard-monitor库实现高效、安全的数据追踪。内容涵盖技术选型、核心功能开发、性能优化及实战应用，适用于安全审计、自动化办公等场景，助力提升数据管理效率与安全性。
站大爷
268 0
站大爷
|
8月前
|
存储 监控 安全
Python剪贴板监控实战：clipboard-monitor库的深度解析与扩展应用
本文介绍如何利用Python的clipboard-monitor库实现剪贴板监控系统，涵盖文本与图片的实时监听、防重复存储、GUI界面开发及数据加密等核心技术，适用于安全审计与自动化办公场景。
站大爷
291 0

热门文章

最新文章

  • 1
    【数据结构入门】-堆的实现以及堆排序（2）
  • 2
    数据结构 | 使用Kotlin实现栈与队列
  • 3
    【数据结构入门精讲 | 第二篇】考研408、企业面试基础概念习题
  • 4
    数据结构学习笔记——链表的相关知识（单链表带头结点和不带头结点的基本操作）（下）
  • 5
    运行时栈帧结构
  • 6
    【数据结构与算法】第六章：栈与递归
  • 7
    【数据结构入门精讲 | 第十二篇】考研408、公司面试树专项练习（一）
  • 8
    数据结构实践——败者树归并模拟
  • 9
    数据结构—线性表的定义与基本操作【插入、删除、查找】（上）
  • 10
    【Java数据结构】搜索二叉树——对节点的插入、查找、删除 操作
  • 1
    字典在Python中的应用与实例
    312
  • 2
    元组（Tuple）在Python编程中的应用与实例
    928
  • 3
    Python函数：深入理解与应用
    156
  • 4
    Python中的try-except异常处理语句
    1013
  • 5
    可移植性在Python中的优势
    524
  • 6
    Python与C的联姻：探索Python的可移植性与C的底层力量
    399
  • 7
    如何选择适合的Python并行计算库
    318
  • 8
    如何优化Python代码以提高执行效率
    127
  • 9
    Python编程的深入探索与实用案例
    149
  • 10
    聊聊python多线程与多进程
    196

    • 相关课程

    更多
  • Python Web开发基础
  • Python开发基础入门
  • Python常用数据科学库
  • Python网络爬虫实战
  • Python完全自学手册图文教程
  • Python基础快速入门实战教程

    • 相关电子书

    更多
  • From Python Scikit-Learn to Sc
  • Data Pre-Processing in Python:
  • 双剑合璧-Python和大数据计算平台的结合

    • 推荐镜像

    更多
  • python-release
    • 下一篇
    ECS账号安全防护最佳实践