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程序设计有所帮助。

(0)

相关推荐

  • python实现反转部分单向链表

    题目: 给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针. 例如: 单链表[1000, 5, 12, 100, 45, 'cecil', 999], a = 4, b = 6, 返回的链表是[1000, 5, 12, 100, 999, 'cecil', 45],也就是说, a 和 b分别为索引值.如果a 和 b 超过了索引范围就返回错误. 代码: 我写的不够简洁,比较繁琐,但是能跑通,繁琐的原因在于

  • python实现从尾到头打印单链表操作示例

    本文实例讲述了python实现从尾到头打印单链表操作.分享给大家供大家参考,具体如下: # coding=utf-8 class SingleNode: def __init__(self, item): self.item = item self.next = None class SingleLinkedList: """ is_empty() 链表是否为空 print_end_to_head() 从尾到头打印单链表 append(item) 链表尾部添加元素 "

  • python中的函数递归和迭代原理解析

    这篇文章主要介绍了python中的函数递归和迭代原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.递归 1.递归的介绍 什么是递归? 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • Python双链表原理与实现方法详解

    本文实例讲述了Python双链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现双链表 文章目录 Python实现双链表 单链表与双链表比较 双链表的实现 定义链表节点 初始化双链表 判断链表是否为空 双链表尾部添加元素 双链表头部添加节点: 双链表表头删除 双链表按位置插入 双链表删除指定节点 完整代码 单链表与双链表比较 双链表比单链表多一个前驱指针位置,空间效率不占优势 由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法) 双链表的实现 定

  • Python实现链表反转的方法分析【迭代法与递归法】

    本文实例讲述了Python实现链表反转的方法.分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点:同时需要引入一个变量new_link表示反转后的新链表:while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失. 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表): 首先需要将当前节点的后继节点传递

  • python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • Python实现队列的方法示例小结【数组,链表】

    本文实例讲述了Python实现队列的方法.分享给大家供大家参考,具体如下: Python实现队列 队列(FIFO),添加元素在队列尾,删除元素在队列头操作 列表实现队列:利用python列表方法 代码如下: # 列表实现队列 class listQueue(object): def __init__(self): self.items = [] def is_empty(self): return self.items == None def size(self): return len(sel

  • Python栈的实现方法示例【列表、单链表】

    本文实例讲述了Python栈的实现方法.分享给大家供大家参考,具体如下: Python实现栈 栈的数组实现:利用python列表方法 代码如下: # 列表实现栈,利用python列表方法 class listStack(object): def __init__(self): self.items = [] def is_empty(self): return self.items == 0 def size(self): return len(self.items) def top(self)

  • 单链表反转python实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

随机推荐