您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章将为大家详细讲解有关Python怎么实现栈,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
使用Python 实现栈。
两种实现方式:
基于数组 - 数组同时基于链表实现
基于单链表 - 单链表的节点时一个实例化的node 对象
完整代码可见GitHub:
https://github.com/GYT0313/Python-DataStructure/tree/master/5-stack
目录结构:
注:一个完整的代码并不是使用一个py文件,而使用了多个文件通过继承方式实现。
arraycollection.py
""" File: abstractcollection.py Author: Ken Lambert """ class AbstractCollection(object): """An abstract collection implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 if sourceCollection: for item in sourceCollection: self.add(item) # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size def __str__(self): """Returns the string representation of self.""" return "[" + ", ".join(map(str, self)) + "]" def __add__(self, other): """Returns a new bag containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result def __eq__(self, other): """Returns True if self equals other, or False otherwise.""" if self is other: return True if type(self) != type(other) or \ len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
abstractstack.py
""" File: abstractstack.py Author: Ken Lambert """ from abstractcollection import AbstractCollection class AbstractStack(AbstractCollection): """An abstract stack implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" AbstractCollection.__init__(self, sourceCollection) # Mutator methods def add(self, item): """Adds item to self.""" self.push(item)
运行示例:
代码:
栈实现:arraystack.py
""" File: abstractstack.py Author: Ken Lambert """ from abstractcollection import AbstractCollection class AbstractStack(AbstractCollection): """An abstract stack implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" AbstractCollection.__init__(self, sourceCollection) # Mutator methods def add(self, item): """Adds item to self.""" self.push(item)
数组实现:arrays.py
""" File: arrays.py An Array is a restricted list whose clients can use only [], len, iter, and str. To instantiate, use <variable> = array(<capacity>, <optional fill value>) The fill value is None by default. """ class Array(object): """Represents an array.""" def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue) def __len__(self): """-> The capacity of the array.""" return len(self._items) def __str__(self): """-> The string representation of the array.""" return str(self._items) def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items) def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index] def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem
运行示例:
代码:
linkedstack.py
""" linkedstack.py """ from node import Node from abstractstack import AbstractStack class LinkedStack(AbstractStack): """基于单链表实现栈-链表头部为栈顶""" def __init__(self, source_collection=None): self._items = None AbstractStack.__init__(self, source_collection) def __iter__(self): """迭代-使用一个列表实现, 列表第一项为单链表的最后一项""" def visit_nodes(node): if node != None: visit_nodes(node.next) temp_list.append(node.data) temp_list = [] visit_nodes(self._items) return iter(temp_list) def peek(self): """返回栈顶元素""" self._prior_condition() return self._items.data def clear(self): """清空列表""" self._size = 0 self._items = None def push(self, item): """入栈""" self._items = Node(item, self._items) self._size += 1 def pop(self): """出栈""" self._prior_condition() old_item = self._items.data self._items = self._items.next self._size -= 1 return old_item def _prior_condition(self): if self._size == 0: raise KeyError("The stack is empty.")
node.py
""" 链表结构的节点类 """ class Node(object): def __init__(self, data, next=None): self.data = data self.next = next
关于“Python怎么实现栈”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。