栈是最简单的数据结构，也是最重要的数据结构。它的原则就是后进先出（LIFO），栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制，接下来我们用python来具体实现这个数据结构。
栈中的方法
作为一个栈（用S来表示），最基本的方法有下面几个：
-
S.push(e): 将元素e添加到S的栈顶
-
S.pop(): 从栈S中移除并返回栈顶的元素，如果此时栈是空的，那么这个操作将会报错
-
S.top(): 不移除栈顶元素，但返回栈顶元素，如果此时栈是空的，那么这个操作将会报错
-
S.is_empty(): 如果栈为空，则返回True，否则返回False
-
len(S): 返回栈中元素的数量，使用len的特殊方法实现
具体实现
Python中的list类与栈的结构很像，但是又有许多不同之处，所以我们以list为基础创建一个新的栈类,代码如下：
class Stack():
"""
以list为基础实现的栈
"""
def __init__(self):
self._data = []
def __len__(self):
return len(self._data)
def is_empty(self):
return len(self._data) == 0
def push(self, e):
self._data.append(e)
def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
return self._data.pop()
def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1]
其中pop与top方法中对于空栈时报的异常是我们自定义的：
class Empty(Exception):
pass
因为列表对于这种情况会产生IndexError，但这个异常与栈并不是很符合，所以我们使用了自定义的异常
简单分析
由于Python是一门动态语言，与一些其他的语言相比，栈中的元素类型可以不一样，所以栈在Python中的使用很灵活，但也有可能会因此使程序理解起来更复杂，如果想要实现这种要求严格的栈类型，可以使用基于array模块中的紧凑数组实现
我们栈中的push方法是利用列表中的append方式实现的，那么列表中的这种动态增加长度的方式我们是有必要了解一下的，先看一个例子：
import sys
data = []
for _ in range(30):
a = len(data)
b = sys.getsizeof(data)
print('长度：{0:3D}; 占用字节：{1:4d}'.fORMat(a,b))
data.append(None)
运行结果为：
长度： 0; 占用字节： 64
长度： 1; 占用字节： 96
长度： 2; 占用字节： 96
长度： 3; 占用字节： 96
长度： 4; 占用字节： 96
长度： 5; 占用字节： 128
长度： 6; 占用字节： 128
长度： 7; 占用字节： 128
长度： 8; 占用字节： 128
长度： 9; 占用字节： 192
长度： 10; 占用字节： 192
长度： 11; 占用字节： 192
长度： 12; 占用字节： 192
长度： 13; 占用字节： 192
长度： 14; 占用字节： 192
长度： 15; 占用字节： 192
长度： 16; 占用字节： 192
长度： 17; 占用字节： 264
长度： 18; 占用字节： 264
长度： 19; 占用字节： 264
长度： 20; 占用字节： 264
长度： 21; 占用字节： 264
长度： 22; 占用字节： 264
长度： 23; 占用字节： 264
长度： 24; 占用字节： 264
长度： 25; 占用字节： 264
长度： 26; 占用字节： 344
长度： 27; 占用字节： 344
长度： 28; 占用字节： 344
长度： 29; 占用字节： 344
通过观察data列表占用字节大小的增长规律，发现在不断的添加中，data的占用的字节每次增加的是越来越大。这是由于list在底层还是基于数组实现的，它每次都会先申请一个长度，当占用的字节要超过最大范围时，再将数组的大小增加。
很明显，当不得不在底层增加数组长度的时候，这时的消耗必然比只添加数据时要大，所以在某些情况下，我们的栈的实现，可以增加一个设置固定长度，提前将所有位置初始化为None，那么在程序运行时，就会减少了再增大底层数组时的开销，这样做有时会非常有用。
参考《数据结构与算法Python语言实现》
0