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

上一篇:JuJu Beta Postmortem


下一篇:数据获取以及处理Beta版本展示