Python实现栈的方法详解【基于数组和单链表两种方法】

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

前言

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

• 基于数组 - 数组同时基于链表实现

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

完整代码可见GitHub：
https://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程序设计有所帮助。

来源：https://blog.csdn.net/qq_38038143/article/details/89361096