数据结构(二):栈
2019-04-12 09:30:34来源:博客园 阅读 ()
栈:后进先出(LIFO)表。
特点:只允许在顶部进行存取操作的顺序表。
基本操作:
- push:入栈,即将元素压入栈顶
- pop:出栈,即将栈顶元素删除
- top:输出栈顶元素
应用场景:
- 平衡符号:编译器中用于检查符号是否成对出现,方法为做一个空栈,读取字符,如果字符是一个开放符号如“{”、“(”、“[”等,将其压入栈中。如果字符是一个封闭符号,如“}”、“)”、“]”,此时如果栈为空,说明有字符没有成对出现;否则将栈元素弹出,如果弹出的符号不是对应的开放符号,同样说明没有成对出现;如果字符读取完毕时栈不为空,也说明字符没有成对出现。
- 函数调用:函数在调用的时候,需要存储所有的重要信息,如变量名、返回地址等,这些信息就是通过栈来存储,然后控制转移到新的函数,当函数返回时从栈中取出存储的信息,继续从转移前的位置往下执行。递归函数对栈的使用开销极大,而且很容易导致栈溢出,可以通过栈操作来模拟递归过程。
栈的链表实现:
1 class Node(object): 2 def __init__(self, value=None, next=None): 3 self.value = value 4 self.next = next 5 6 7 class Stack(object): 8 def __init__(self, maxsize=8): 9 self._head = Node() # 表头,无实际意义 10 self._top = None 11 self.maxsize = maxsize 12 self.length = 0 13 14 def pop(self): 15 if self.length > 0: 16 node = self._head.next 17 self._head.next = node.next 18 self.length -= 1 19 self._top = self._head.next 20 else: 21 raise Exception('Empty stack') 22 23 def push(self, value): 24 if self.length >= self.maxsize: 25 raise Exception('Stack is full') 26 node = Node(value) 27 node.next = self._head.next 28 self._head.next = node 29 self.length += 1 30 self._top = self._head.next 31 32 def top(self): 33 if self.length > 0: 34 return self._top.value 35 else: 36 raise Exception('Stack is empty') 37 38 def __len__(self): 39 return self.length
栈的数组实现:
1 from array import array 2 3 class Stack(object): 4 def __init__(self, maxsize=8): 5 self._array = array('i', range(maxsize)) 6 self.maxsize = maxsize 7 self.length = 0 8 self.index = -1 9 self._top = None 10 11 def push(self, value): 12 if self.length >= self.maxsize: 13 raise Exception('Stack is full') 14 self.index += 1 15 self._array[self.index] = value 16 self.length += 1 17 self._top = value 18 19 def pop(self): 20 if self.length <= 0: 21 raise Exception('Stack is empty') 22 self.index -= 1 23 self.length -= 1 24 if self.index >= 0: 25 self._top = self._array[self.index] 26 else: 27 self._top = None 28 29 def top(self): 30 return self._top 31 32 def __len__(self): 33 return self.length
原文链接:https://www.cnblogs.com/sheshouxin/p/10680634.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Python 数据结构理解分享 2019-07-24
- django修改表数据结构后报错的解决办法 2019-07-24
- Python-04-数据结构 2019-07-24
- python算法与数据结构-二叉树的代码实现(46) 2019-07-24
- python算法与数据结构-数据结构中常用树的介绍(45) 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash