数据结构之栈(使用Python描述)
栈(Stack)的特性是先进后出.即是First In Last Out.栈也是在一端进行操作的.
先进入栈的元素是最后出来的.比如说,我们使用的浏览器进行标签后退操作时,首先返回的是上一个就近的标签.
栈的特性是反转次序,也就是First In Last Out.
有关于Stack的可视化数据操作:www.cs.usfca.edu/~galles/visualization/StackArray.html.这可以帮助到你理解Stack的特性.
''' - 栈 Stack - 一种有次序的数据项集合. - 在栈中,数据项的加入和移除都仅发生在同一端 - 这一端叫栈“顶top”,另一端叫栈“底base” - 例如日常生活中的成叠的盘子 - 距离栈底越近的数据项,留在栈中的时间就越长,而最新加入栈的数据项会被最先移除 - 这种次序通常称为"后进先出LIFO" Last in frist out - 这是一种基于数据项保存时间的次序,时间的离栈顶越近而时间越长的离栈底越近 - 栈的特性 - 反转次序 '''
''' - 栈的抽象数据类型定义 - Stack():创建一个空栈,不包含任何数据项 - push(item):将item加入栈顶,无返回值 - pop():将栈顶数据项移除,并返回,栈被修改 - peek():“窥视”栈顶数据项,返回栈顶的数据项但不移除,栈不被修改 - isEmpty():返回栈是否为空栈 - size():返回栈中有多少个数据项 ''' class Stack(): # 将末端设置为栈顶/ 这里要加一个括号 def __init__(self): # self在对象的方法中表示对象本身,如果通过对象调用一个方法,那么对象就会自动成为地一个参数 self.items = [] # items表示的是一个属性 def isEmpty(self):#判断栈是否为空 return self.items == [] def push(self,item):#在栈尾添加元素 return self.items.append(item) def pop(self):# 在栈尾移除元素 return self.items.pop() def peek(self):# 返回在栈尾的元素 return self.items[len(self.items)-1] def size(self):# 返回栈的元素个数 return len(self.items) a = Stack() a.push(1) a.push('das') a.push('dasd') a.push('rew') print(a.size())
# 以下代码是栈的实际使用: 进行括号的匹配 def parCheckers(symbolString): s = Stack() index = 0 balance = True while index<len(symbolString) and balance: symbol = symbolString[index] if symbol in'([{': s.push(symbol) else: if s.isEmpty(): balance = False else: top = s.pop() if not matches(top,symbol): balance = False index = index+1; if s.isEmpty() and balance: return True else: return False def matches(open,close): opens = '([{' closes = ')]}' return opens.index(open) == closes.index(close) print(parCheckers('[[[[[((({{{((()){{}})}}})))]]]]]'))
相关推荐
whyname 2020-03-07
alicelmx 2020-01-06
yunfeiyang0 2019-06-12
huzai 2019-09-05
ipqtjmqj 2012-05-04
snowfoxmonitor 2012-11-08
dapeng00 2015-05-24
yongyoumengxiang 2019-06-28
zhoushuntian 2018-01-24
pythonpycharm 2019-04-23
懒人在思考 2018-05-31
BitTigerio 2018-04-24