python-030-实现栈结构-用数组-适配器设计模式

栈是最简单的数据结构，但也是最重要的数据结构。它出现在很多不同的应用中，在更复杂的数据结构和算法中充当工具。
从形式上，栈支持两种操作的抽象数据类型ADT，压栈和入栈：

• S.push()
• S.pop()
  此外，他还有以下方法：
• S.top() 在不移除栈顶元素的前提下，返回栈顶元素，若栈为空，则报错。
• S.is_empty() 如果栈中没有元素，返回True。
• S.is_empty() 返回栈中元素的个数。
  初始化栈时，栈一半为空，且容量没有限制，栈元素可以是任意类型。

栈是一种先进后出的数据结构（Last In First Out）——LIFO。可以联想到python的列表，list.append()、list.pop()，是现成的方法。可以直接用。
有了以上信息，我们就可以开始着手实现一个栈类了。

这里涉及到一种设计模式——适配器模式。python的list类可以很方便的实现栈，所以我们通过改编它来实现。

适配器设计模式适用于任何上下文，可以使我们可以有效地使用一个现有的类，以使它的方法能够与那些与其相关但又不同的类或者接口相匹配。
通用的使用方法是将一个包含现存类作为一个新类的隐藏域，利用这个隐藏实例变量的方法实现新类的方法。
以这种方式应用适配器设计模式，我们已经创建了一个新类，可以执行一些现有类相同的方法，但是却用更加方便的方式进行封装。

改编列表类：

• S.push(e) -------------->L.append(e)
• S.pop(e) -------------->L.pop(e)
• S.top() -------------->L[-1]
• S.is_empty() -------------->len(L)==0
• len(S) -------------->len(L)

我们先定义一个异常类用来说明栈中为空。

class Empty(Exception):
    """Error attempting to access an empty container"""
    pass

下面是栈类的代码：

class Empty(Exception):
    """Error attempting to access an empty container"""
    pass


class ArrayStack:
    """LIFO Stack using a python list"""
    def __init__(self):
        self._data = []

    def __len__(self):
        """返回栈中的元素个数"""
        return len(self._data)

    def is_empty(self):
        """如果栈为空，返回True"""
        return len(self._data) == 0

    def push(self, e):
        """压栈"""
        return self._data.append(e)

    def top(self):
        """返回栈顶元素，但不返回不弹栈"""
        if self.is_empty():
            raise Empty('Stack is empty!')
        return self._data[-1]

    def pop(self):
        """弹出栈顶元素，并返回这个元素"""
        if self.is_empty():
            raise Empty('Stack is empty!')
        return self._data.pop()

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


if __name__ == '__main__':
    # 调用这个栈
    s = ArrayStack()
    s.push(1)
    s.push(2)
    s.push(3)
    print(s)
    print('len(s)', len(s))
    print('s.top()',s.top())
    s.pop()
    print(s)
    print('s.pop()',s.pop())
    print('len(s)', len(s))
    s.push(5)
    s.push(9)
    print(s)
    print('len(s)', len(s))

我在最下面又加了str()方法，可以打印栈，可以方便我们做测试。

运行结果：

image.png