这篇文章主要介绍了Python实现栈的方法,结合实例形式详细分析了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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与总结》、《Python编码操作总结》、《Python函数使用总结》、《Python字符串操作汇总》及《Python入门与进阶经典教程》

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

最新资讯
懂得流体力学,它们身体构造简单,却是游泳高手

懂得流体力学,它们身体

月亮水母“懂得”流体力学知识,从而成为了海洋里最懂得
今日《自然》:新冠病毒在不断突变,免疫系统也没闲着...

今日《自然》:新冠病毒

新冠病毒突变的出现不禁让人们产生了疑虑,人体的免疫系
甜味剂会随尿排出污染水源……可能再也无法直视“这水真甜”了

甜味剂会随尿排出污染

你有没有想过,这些被人为排放到水中的甜味剂会流入江河
字节跳动全资子公司入股松果医疗,后者经营范围含全科医疗服务

字节跳动全资子公司入

天眼查App显示,今日,北京松果医疗有限公司发生工商变更,
帝国陨落!停牌3年负债百亿 "果汁大王"汇源退市后何去何从|观潮

帝国陨落!停牌3年负债

24小时前,香港联交所发布通告,取消中国汇源果汁集团有限
联邦快递宣布将对住宅快递征收附加费

联邦快递宣布将对住宅

联邦快递(FDX.US)将对其大客户的住宅快递征收一项新的
最新文章
在pycharm中为项目导入anacodna环境的操作方法

在pycharm中为项目导

这篇文章主要介绍了在pycharm中为项目导入anacodna环
tensorflow的ckpt及pb模型持久化方式及转化详解

tensorflow的ckpt及pb

今天小编就为大家分享一篇tensorflow的ckpt及pb模型持
PyTorch笔记之scatter()函数的使用

PyTorch笔记之scatter

这篇文章主要介绍了PyTorch笔记之scatter()函数的使用
python3实现网页版raspberry pi(树莓派)小车控制

python3实现网页版ras

这篇文章主要为大家详细介绍了python3实现网页版raspb
完美解决pycharm导入自己写的py文件爆红问题

完美解决pycharm导入

今天小编就为大家分享一篇完美解决pycharm导入自己写
pycharm内无法import已安装的模块问题解决

pycharm内无法import

今天小编就为大家分享一篇pycharm内无法import已安装