栈是最简单的数据结构，但也是最重要的数据结构。它出现在很多不同的应用中，在更复杂的数据结构和算法中充当工具。
从形式上，栈支持两种操作的抽象数据类型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
网友评论