数据结构---堆栈（Data Structure Stack Python）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构---堆栈（Data Structure Stack Python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2409字，纯文字阅读大概需要4分钟。
内容图文
堆栈（Stack）：是一种线性数据结构，其数据遵循后进先出（last in first out）的原则。典型的应用比如说网页的“后退”按钮，其储存了依次浏览过的网页url（进栈），在按后退按钮时则实施出栈操作。
python实现：
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
return self.stack.pop()
def isEmpty():
return self.stack == []
时间复杂度（Time Complexity）：
push（进栈操作）： O(1)
pop（出栈操作）： O(1)
Stack的应用：在需要倒序的地方可以考虑使用stack。（以下代码均摘自《Problem Solving with Algorithms and Data Structures Using Python》一书）
1，对str进行逆序
比如输入一个字符串"abcd"，要求输出它的逆序"dcba"。首先遍历字符串，将每个字符储存进stack，然后创建一个空字符串，将stack中储存的字符一个个取出，加入空字符串，直至stack为空。
def reversestring(mystr):
s = Stack()
revstring = ""
for i in mystr:
s.push(i)
while not s.isEmpty():
revstring = revstring + s.pop()
return revstring
2，检查符号的平衡性
当我们在题板上写code时，所使用的一些符号必须配对，否则会造成语法错误。比如说：列表[ ]，字典{ }，等等。那么如何来检查这些符号的平衡性呢？首先遍历符号字符串，如果是开括号之类的，那么储存进stack，如果是闭括号之类的，那么在stack中去除最上面的符号。这里因为有许多种不同的符号，所以有一个helper function，帮助检查遍历到的这个符号是否和去除的符号配对，如果不配对，那么就表示符号不平衡。遍历至符号字符串的最后一个符号或者直到发现不平衡的情况为止。
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open,close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
3，将数值转换成各种进制
将数值除以base，取余储存进stack，将商数继续除以base，直至商数的数值为0，然后将stack中的数值倒序，即为转换的进制数。
def baseConverter(decNumber,base):
digits = "0123456789ABCDEF"
remstack = Stack()
while decNumber > 0:
rem = decNumber % base
remstack.push(rem)
decNumber = decNumber // base
newString = ""
while not remstack.isEmpty():
newString = newString + digits[remstack.pop()]
return newString
4，让计算机读懂数值计算表达式（例如：3+2*5）
内容总结
以上是互联网集市为您收集整理的数据结构---堆栈（Data Structure Stack Python）全部内容，希望文章能够帮你解决数据结构---堆栈（Data Structure Stack Python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。