用Python实现数据结构之栈

栈

栈是最简单的数据结构，也是最重要的数据结构。它的原则就是后进先出（LIFO），栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制，接下来我们用Python来具体实现这个数据结构。

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语言实现》

​