Python如何通过数组与单链表实现栈功能详解？

本文共计1050个文字，预计阅读时间需要5分钟。

原文：本文实例讲述了Python实现栈的方法。分享给广大读者供大家参考，具体如下：

前言使用Python实现栈。

两种实现方式：基于数组基于链表+节点时一个

改写后：本文通过实例展示如何用Python实现栈。以下内容供大家参考：

简介利用Python实现栈功能。

实现方法：数组实现链表实现（节点时一个）

本文实例讲述了Python实现栈的方法。分享给大家供大家参考，具体如下：

前言

使用Python 实现栈。
两种实现方式：

• 基于数组 - 数组同时基于链表实现
• 基于单链表 - 单链表的节点时一个实例化的node 对象

完整代码可见GitHub：
github.com/GYT0313/Python-DataStructure/tree/master/5-stack

目录结构：

注：一个完整的代码并不是使用一个py文件，而使用了多个文件通过继承方式实现。

1. 超类接口代码

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)

2. 基于数组

运行示例：

代码：
栈实现：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

3. 基于链表

运行示例：

代码：
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语言描述）》

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。