Python实现栈的方法详解【基于数组和单链表两种方法】
本文实例讲述了Python实现栈的方法。分享给大家供大家参考，具体如下：
前言
使用Python实现栈。
两种实现方式：
- 基于数组-数组同时基于链表实现
- 基于单链表-单链表的节点时一个实例化的node对象
完整代码可见GitHub：
https://github.com/GYT0313/Python-DataStructure/tree/master/5-stack
目录结构：
注：一个完整的代码并不是使用一个py文件，而使用了多个文件通过继承方式实现。
1.超类接口代码
arraycollection.py
""" File:abstractcollection.py Author:KenLambert """ classAbstractCollection(object): """Anabstractcollectionimplementation.""" #Constructor def__init__(self,sourceCollection=None): """Setstheinitialstateofself,whichincludesthe contentsofsourceCollection,ifit'spresent.""" self._size=0 ifsourceCollection: foriteminsourceCollection: self.add(item) #Accessormethods defisEmpty(self): """ReturnsTrueiflen(self)==0,orFalseotherwise.""" returnlen(self)==0 def__len__(self): """Returnsthenumberofitemsinself.""" returnself._size def__str__(self): """Returnsthestringrepresentationofself.""" return"["+",".join(map(str,self))+"]" def__add__(self,other): """Returnsanewbagcontainingthecontents ofselfandother.""" result=type(self)(self) foriteminother: result.add(item) returnresult def__eq__(self,other): """ReturnsTrueifselfequalsother, orFalseotherwise.""" ifselfisother:returnTrue iftype(self)!=type(other)or\ len(self)!=len(other): returnFalse otherIter=iter(other) foriteminself: ifitem!=next(otherIter): returnFalse returnTrue
abstractstack.py
""" File:abstractstack.py Author:KenLambert """ fromabstractcollectionimportAbstractCollection classAbstractStack(AbstractCollection): """Anabstractstackimplementation.""" #Constructor def__init__(self,sourceCollection=None): """Setstheinitialstateofself,whichincludesthe contentsofsourceCollection,ifit'spresent.""" AbstractCollection.__init__(self,sourceCollection) #Mutatormethods defadd(self,item): """Addsitemtoself.""" self.push(item)
2.基于数组
运行示例：
代码：
栈实现：arraystack.py
""" File:abstractstack.py Author:KenLambert """ fromabstractcollectionimportAbstractCollection classAbstractStack(AbstractCollection): """Anabstractstackimplementation.""" #Constructor def__init__(self,sourceCollection=None): """Setstheinitialstateofself,whichincludesthe contentsofsourceCollection,ifit'spresent.""" AbstractCollection.__init__(self,sourceCollection) #Mutatormethods defadd(self,item): """Addsitemtoself.""" self.push(item)
数组实现：arrays.py
""" File:arrays.py AnArrayisarestrictedlistwhoseclientscanuse only[],len,iter,andstr. Toinstantiate,use=array( , ) ThefillvalueisNonebydefault. """ classArray(object): """Representsanarray.""" def__init__(self,capacity,fillValue=None): """Capacityisthestaticsizeofthearray. fillValueisplacedateachposition.""" self._items=list() forcountinrange(capacity): self._items.append(fillValue) def__len__(self): """->Thecapacityofthearray.""" returnlen(self._items) def__str__(self): """->Thestringrepresentationofthearray.""" returnstr(self._items) def__iter__(self): """Supportsiterationoveraviewofanarray.""" returniter(self._items) def__getitem__(self,index): """Subscriptoperatorforaccessatindex.""" returnself._items[index] def__setitem__(self,index,newItem): """Subscriptoperatorforreplacementatindex.""" self._items[index]=newItem
3.基于链表
运行示例：
代码：
linkedstack.py
"""
linkedstack.py
"""
fromnodeimportNode
fromabstractstackimportAbstractStack
classLinkedStack(AbstractStack):
"""基于单链表实现栈-链表头部为栈顶"""
def__init__(self,source_collection=None):
self._items=None
AbstractStack.__init__(self,source_collection)
def__iter__(self):
"""迭代-使用一个列表实现,列表第一项为单链表的最后一项"""
defvisit_nodes(node):
ifnode!=None:
visit_nodes(node.next)
temp_list.append(node.data)
temp_list=[]
visit_nodes(self._items)
returniter(temp_list)
defpeek(self):
"""返回栈顶元素"""
self._prior_condition()
returnself._items.data
defclear(self):
"""清空列表"""
self._size=0
self._items=None
defpush(self,item):
"""入栈"""
self._items=Node(item,self._items)
self._size+=1
defpop(self):
"""出栈"""
self._prior_condition()
old_item=self._items.data
self._items=self._items.next
self._size-=1
returnold_item
def_prior_condition(self):
ifself._size==0:
raiseKeyError("Thestackisempty.")
node.py
""" 链表结构的节点类 """ classNode(object): def__init__(self,data,next=None): self.data=data self.next=next
参考：《数据结构（Python语言描述）》
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。