鱼C论坛

 找回密码
 立即注册
查看: 3613|回复: 2

[技术交流] python基本数据结构类型--初识栈

[复制链接]
发表于 2020-3-28 21:06:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 dlnb526 于 2020-3-31 17:42 编辑
MOOC课程 《数据结构与算法》(北大地空)笔记
by dlnb526
2020.3

预备知识:线性结构(线性表)
  • 前驱和后继

线性结构的特点就在于其线性,也就是说整个结构里面的元素都只有一个前驱和一个后继(除了开头和结尾的元素),就像是一串糖葫芦或者列车一样。
当我们向线性结构中添加一个项目时,他会放在之前的项和后来的项之间。


什么是栈
  • 栈是线性结构
  • 栈是一个项的有序集合
  • 栈遵循LIFO原则

LIFO原则(Last in, First out.后进先出)。栈的添加项和移除项都会发生在同一端,另一端我们不妨称之为‘底’。这样每当添加一个项,原本就靠近‘底’的元素就会更加被压在底下,因此它在栈中存储的时间会更长。

栈的抽象数据类型
  • Stack(): 创建一个新的空栈,它不需要参数并返回一个空栈。
  • push(item): 将一个新项目添加到堆栈的顶部。
  • pop(): 从栈顶删除项目,不需要参数,返回所删除的item,进行操作后栈会被修改
  • peek(): 返回栈顶的项,不删除。
  • isEmpty(): 测试栈是否为空,返回一个布尔值
  • size(): 返回栈的项目数

接下来我们通过python来构建上面的栈的结构。

构建栈
# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
# 
#stack.py

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

通过上面的方法就完成了栈的构建。

复杂度分析

对栈进行操作,其实都是相当于直接对列表的尾端进行操作,因此我们可以知道其时间复杂度如下:
操作    复杂度  

push(item)   O(1)
pop()   O(1)
peek()O(1)
isEmpty()O(1)
size()O(1)


之后
下次的内容将是栈的两个应用举例~

评分!评分!评分!~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-3-28 21:30:08 | 显示全部楼层
class Stack(list):

    def isEmpty(self):
        return not self

    def push(self, item):
        self.append(item)

    def pop(self):
        return list.pop(self)

    def peek(self):
        return self[-1]

    def size(self):
        return self.__len__()
直接继承List不也很好吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-28 21:45:49 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-3-28 21:30
直接继承List不也很好吗


额这个我放的是  pythonds 模块中栈(stack)的源代码。pythonds 中有各种数据结构的实现~我以后都直接用这里的电池~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-25 20:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表