专栏首页python3用Python实现数据结构之栈

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Python3】02、python编码

           因为字符编码的问题而苦恼不已,于是阅读了大量的博客,再进行了一定的测试,基本搞清楚了编码问题的前因后果。

    py3study
  • python3 setdefault的

    py3study
  • mysql3

    MHA(Master High Availability)是目前在MySQL高可用方面相对成熟的一个解决方案,MHA在监控到master节点故障时,会提升其中拥...

    py3study
  • IP协议的数据帧长度是多少

    1、如果使用PPP协议,帧最大长度1510字节,其中数据长度(加载上层的协议数据)不超过1500字节; 2、如果在以太网中,帧的长度为:64~1518字节(1...

    葆宁
  • 聊一聊整数编码

    网络上有两个用户A和B,用户A想要向B发送一个4字节的整型数据,请问A应该怎么做呢?

    算法与编程之美
  • jmap命令使用

    如果想分析自己的JAVA Application时,可以使用jmap程序来生成heapdump文例: jmap -heap pid jmap是JDK自带的一个工...

    日薪月亿
  • 【技术创作101训练营】从Go语言角度剖析关于计算机位的问题

    我叫大家好,我是Go进阶者,公众号《Go进阶学习交流》公众号的号主。今天给大家分享的内容是从Go语言角度剖析关于计算机位的问题,分享的内容会比较枯燥一些,大家别...

    Go进阶者
  • mysql 数据类型及占用字节数

    秋日芒草
  • 计算机编码基础

         乱码是我们在日常的工作中经常遇到的问题,你可能从网上好不容易下载了一个炫酷的jQuery插件,但是却在打开的时候,发现某几个js文件都是类似“澶у0?...

    Single
  • 刨根究底字符编码之九——字符编码方案的演变与字节序

    前文已经提及,编号字符集CCS(简称字符集)与字符编码方式CEF(简称编码方式)这两个概念,在早期并没有必要严格区分。

    用户1876609

扫码关注云+社区

领取腾讯云代金券