使用Python手搓一个堆栈类

内容纲要

在计算机科学中，堆栈是一种由项目集合表示的数据结构，利用后进先出 (LIFO) 模型进行访问。
python
该数据结构有两个基本操作：

push()将项目添加到堆栈的函数。
pop()删除最近添加到堆栈中的项目的函数。

通过这种方式，这种类型的收藏类似于一堆物品，例如餐盘，其中必须移除最上面的物品才能访问下面的物品。堆栈在实现深度优先搜索等操作时非常有用。本文将探讨在Python中实现堆栈的过程。

python实现stack

1.设计堆栈实践

在开始之前，我们需要决定在堆栈实现中需要什么样的功能，.push()，.pop()函数是最低要求。但我们可能还需要以下内容：

Python的len()函数: 让我们知道堆栈中有多少项，并在堆栈为空时发出警告。在程序中使用堆栈时检查堆栈是否为空是一种很好的做法。

一个.peek()函数，告诉我们堆栈顶部项目的值而不删除它。

最后，我们想要决定.peek()或.pop()方法在空堆栈上调用时的行为方式。我们可以返回类似NaN的内容，但这可能会导致细微的错误，特别是在NaN将值添加到堆栈时。

在这种情况下，更好的做法是当我们尝试在空堆栈上使用这些函数时引发异常。这样，就可以在测试期间捕获此类事件，并且可以适当地更新使用堆栈的代码。

2.开始构建堆栈类

我们的堆栈将是一个Python类。一旦声明了类，我们首先要添加的是一个容器来保存堆栈中的项目。为此，我们创建一个内部变量：

class stack:
  def __init__(self):
    self.__index = []

在初始化stack类时，它将把__index变量初始化为空列表。该列表将保存我们堆栈中的项目。

3.设置len()功能

首先为stack类设置len()函数，因为我们需要在使用.pop()和.peek()方法之前检查它。

我们将通过实现一个“神奇”方法来做到这一点，也称为 Dunder（双下划线）方法。双下划线方法允许我们覆盖内置 Python 操作的行为。
对于我们的堆栈，我们可以利用len()双下划线方法来制定我们需要的“长度”行为：

class stack:
  def __init__(self):
    self.__index = []

  def __len__(self):
    return len(self.__index)

现在，当我们调用len(stack_instance)时，它将返回变量中的项目数__index。

>>> s = stack()
>>> # some additional stack operations go here
>>> len(s) # fetch number of items in the stack
2

4.设置.push()方法

接下来，我们要设置.push()将项目放入__index变量中的方法。

由于__index是一个列表，我们的主要决定是我们应该在列表的哪个“末尾”插入我们的项目。

第一个行为可能是将项目附加到我们的__index列表中，因为我们通常认为索引最高的项目是“顶部”。

然而，这种方法对于我们的目的来说可能是有问题的。这是因为当我们在堆栈上执行操作时，我们的引用“顶部”索引始终会发生变化。此外，每次引用该值时都需要重新计算。

从列表的“开始”添加和删除项目会更有效，因为“开始”的索引永远不会改变。它永远为零。因此，我们的__index变量将按照“顶部”项目作为列表的第一项进行排序。

由于我们使用的是 Python 列表，因此可以使用内置.insert()方法来完成此操作：

class stack:
 def __init__(self):
   self.__index = []

 def __len__(self):
   return len(self.__index)

 def push(self,item):
   self.__index.insert(0,item)

5.设置.peek()方法

.peek()方法非常简单。它返回堆栈的“顶部”值，它指的是列表中的第一项__index[0]。

但是，我们需要考虑列表为空的可能性。我们需要使用函数len()检查堆栈，如果我们尝试在空堆栈上使用.peek()，则抛出异常：

class stack:
 def __init__(self):
   self.__index = []

 def __len__(self):
   return len(self.__index)

 def push(self,item):
   self.__index.insert(0,item)

 def peek(self):
   if len(self) == 0:
     raise Exception("peek() called on empty stack.")
   return self.__index[0]

6.设置.pop()方法

.pop()方法与.peek()方法类似。我们需要在尝试返回值之前检查是否有空列表：

class stack:
 def __init__(self):
   self.__index = []

 def __len__(self):
   return len(self.__index)

 def push(self,item):
   self.__index.insert(0,item)

 def peek(self):
   if len(self) == 0:
     raise Exception("peek() called on empty stack.")
   return self.__index[0]

 def pop(self):
   if len(self) == 0:
     raise Exception("pop() called on empty stack.")
   return self.__index.pop(0)

值得注意的是，Python 列表有自己的.pop()方法，其行为几乎与我们的堆栈方法.pop()相同。
只是列表可以采用索引,并从列表中的任何位置“弹出”项目。

7.设置str()功能

我们可以做的另一件事是告诉 Python 我们希望使用函数打印str()堆栈。目前，使用它会产生以下结果：

>>> s = stack()
>>> print(str(s))
'<__main__.stack object at 0x000002296C8ED160>'

为了理解堆栈的内容，我们需要一些更有用的东西。这就是__str__()双下划线方法派上用场的地方：

class stack:
 def __init__(self):
   self.__index = []

 def __len__(self):
   return len(self.__index)

 def push(self,item):
   self.__index.insert(0,item)

 def peek(self):
   if len(self) == 0:
     raise Exception("peek() called on empty stack.")
   return self.__index[0]

 def pop(self):
   if len(self) == 0:
     raise Exception("pop() called on empty stack.")
   return self.__index.pop(0)

 def __str__(self):
   return str(self.__index)

这将返回堆栈的内容，就像打印出通用列表的项目一样。

8.使用stack类

我们现在有了一个可用的stack类。下面的代码突出显示了我们在自定义类中实现的所有功能：

>>> s = stack()
>>> s.peek()           # stack = []
Exception: peek() called on empty stack.
>>> len(s)
0
>>> s.push(5)          # stack = [5]
>>> s.peek()
5
>>> s.push('Apple')    # stack = ['Apple',5]
>>> s.push({'A':'B'})  # stack = [{'A':'B'},'Apple',5]
>>> s.push(25)         # stack = [25,{'A':'B'},'Apple',5]
>>> len(s)
4
>>> str(s)
"[25, {'A': 'B'}, 'Apple', 5]"
>>> s.pop()            # stack = [{'A':'B'},'Apple',5]
25
>>> s.pop()            # stack = ['Apple',5]
{'A': 'B'}
>>> str(s)
"['Apple', 5]"
>>> len(s)
2

9.结论

我们已经学习了如何在 Python 中实现堆栈类的核心功能。我们还可以为此实现添加更多功能。比如以下几点：

重构.peek()以按索引查看堆栈中的任何项目。
支持将列表内容作为堆栈中的一系列项目附加。
添加一个.clear()清空堆栈的方法。
定义堆栈大小的上限，这在生产使用中可能很有价值，可以防止失控操作重复向堆栈添加项目并导致“内存不足”异常。

以此为基础，我们就可以顺利开发自己的堆栈实现了。