首页 > 编程语言 >数据结构(Python版)——3、基本结构

数据结构(Python版)——3、基本结构

时间:2023-06-16 14:24:12浏览次数:42  
标签:数据项 Python items self pop 数据结构 Stack def 结构

数据结构(Python版)——3、基本结构

什么是线性结构Linear Structure

线性结构是一种有序数据项的集合,其中每个数据项都有唯一的前驱和后继

除了第一个没有前驱,最后一个没有后继

新的数据项加入到数据集中是,只会加入到原有某个数据项之前或之后

具有这种性质的数据集,就称为线性结构

线性结构总有两端,在不同的情况下,两端的称呼也不同

有时候称为“左”“右”端、“前”“后”端、“顶”“底”端

两端的称呼并不是关键,不同线性结构的关键区别在于数据项增减的方式

有的结构只允许数据项从一端添加,而有的结构则允许数据项从两端移除

我们从4中最简单但功能强大的结构入手,开始研究数据结构

栈Stack,队列Queue,双端队列Deque和列表List

这些数据集的共同点在于,数据项之间只存在先后的次序,都是线性结构

这些线性结构是应用最广泛的数据结构,它们出现在各种算法中,用来解决大量重要问题

栈抽象数据类型及Python实现

栈Stack:什么是栈?

一种有次序的数据项集合,在栈中,数据项的加入和移除都仅发生在同一端

在这一端叫栈“顶top”,另一端叫栈“底base”

日常生活中有很多栈的应用

盘子、托盘、书堆等等

距离栈底越近的数据项,留在栈中的时间就越长

而最新加入栈的数据项会被最先移除

这种次序通常称为“后进先出LIFO”:Last in First out

这是一种基于数据项保存时间的次序,时间越短的离栈顶越近,而时间越长的离栈底越近

栈的特性:反转次序

我们观察一个由混合的Python原生数据对象形成的栈

进栈和出栈的次序正好相反

这种访问次序反转的特性,我们在某些计算机操作上碰到过

浏览器的“后退back”按钮,最先back的是最近访问的网页

world的“Undo”按钮,最先撤销的是最近操作

抽象数据类型Stack

抽象数据类型“栈”是一个有次序的数据集,每个数据项近从“栈顶”一端加入到数据集中、从数据集中移除,栈具有后进先出LIFO的特性

抽象数据类型“栈”定义为如下的操作

Stack():创建一个空栈,不包括任何数据项

push(item):将item加入栈顶,无返回值

pop():将栈顶数据项移除,并返回,栈被修改

peek():“窥视”栈顶数据项,返回栈顶的数据项但不移除,栈不被修改

isEmpty():返回栈是否为空栈

size():返回栈中有多少个数据项

抽象数据类型Stack:操作样例

用Python实现ADT Stack

在清楚地定义了抽象数据类型Stack之后,我们看看如何用Python来实现它

Python的面向对象机制,可以用来实现用户自定义类型

将ADT Stack实现为Python的一个Class

将ADT Stack的操作实现为Class的方法

由于Stack是一个数据集,所以可以采用Python的原生数据集来实现,我们选用最常用的数据集List来实现

一个细节:Stack的两端对应list设置

可以将List的任意一端(index=0或者-1)设置为栈顶

我们选用List的末端(index=-1)作为栈顶

这样栈的操作就可以通过对list的append和pop来实现,很简单!

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)

Stack测试代码

s = Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())
print(s.items)

实验结果:

ADT Stack的另一个实现

如果我们把List的另一端(首端index=0)作为Stack的栈顶,同样也可以实现Stack

不同的实现方式保持了ADT接口的稳定性

但性能有所不同,栈顶首端的版本(左),其push/pop的复杂度为O(n),而栈顶尾端的实现(右),其push/pop的复杂度为O(1)

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]
        return self.items[0]

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

未完待续

标签:数据项,Python,items,self,pop,数据结构,Stack,def,结构
From: https://www.cnblogs.com/lightwower/p/17485397.html

相关文章

  • Python几个数字计算最接近某个值的和(用于报销的)
    一、序场景:公司报销需要用打车发票,金额不能多于报销额度,自己搭配出最接近报销的金额二、实现思路读取全部打车能报销的金额,全部相加,留下小等于报销金额的组合,然后取最大值与组合三、实现代码实现代码importitertoolsimportpandasaspdimportnumpyas......
  • python基础语法练习题
    """一、必做题1、下面变量名正确的是(ABD)A.nameB.num1C.1_numD.name_A_12、Python不支持的数据类型有(A)A、charB、intC、floatD、list3、python源程序执行的方式(B)A编译执行B解析执行C直接执行D边编译边执行4、Python语言语句块的标记是(C)A分号B......
  • python基础-字符串
    基础必做题:题目1:现在有字符串:str1='pythoncainiao666'请使用代码找出第5个字符请复制一份字符串,保存在变量str_two当中(赋值运算符)"""str1='pythoncainiao666'str_two=str1[4]print(str_two)#输出o"""题目2:卖橘子的计算器(字符串转化)写一段代码,用户输入橘子的价格......
  • Python数据类型-列表与元组
    #题目1:删除如下列表中的"矮穷丑",写出2种或以上方法:#info=["yuze",18,"男","矮穷丑",["高","富","帅"],True,None,"狼的眼睛是啥样的"]info=["yuze",18,"男","矮穷丑",["......
  • Python中常用set()方法详解!
    set是Python中一种集合数据类型,表示一个无序且不重复的集合。set()方法可以用于创建一个空的集合,也可以将其他可迭代对象转换为集合。与其他Python数据类型不同,set没有索引,不能通过索引访问其元素,但可以使用一些方法来操作和访问集合中的元素。1、add():添加一个元素到set集......
  • CST电磁仿真软件对火箭发射场雷击仿真与电子设备结构设计
    火箭发射场雷击仿真,模型中包含大的塔台、地面等结构,也包含火箭上的缝隙及内部的电缆等细节。CST内置了雷击信号模型,使用时域求解器可直接仿真雷击下的各类瞬态电磁效应,比如瞬态电流分布,电缆上的瞬态电压等。     振动试验模拟@Wave6音响阵列常用于运载火箭的振动......
  • Python初学者友好丨详解参数传递类型
    摘要: 本文清晰地解释了Python中的不同参数传递类型,并提供了示例代码来说明每种类型的用法。对于初学者或不清楚Python传参的读者们来说是非常有益的,文中提供了足够的信息来理解和使用Python中的函数参数传递。本文分享自华为云社区《提升Python函数调用灵活性:参数传递类型详解》......
  • Python初学者友好丨详解参数传递类型
    摘要: 本文清晰地解释了Python中的不同参数传递类型,并提供了示例代码来说明每种类型的用法。对于初学者或不清楚Python传参的读者们来说是非常有益的,文中提供了足够的信息来理解和使用Python中的函数参数传递。本文分享自华为云社区《提升Python函数调用灵活性:参数传递类型详解》,作......
  • Python学了基本语法 下一步该干什么 ?
    刚入门Python,学习了基本语法后,你可以开始编写简单的程序了。接下来,你可以学习Python的标准库和第三方库,掌握更多的编程技巧和知识,提高自己的编程能力。同时,也可以通过实践项目来巩固所学知识,提高自己的实战能力。学习Python基本语法是入门的第一步,接下来你可以考虑以下几个方向......
  • Python——Besutiful soup(网页)
    什么是beautifulsoup:是一个可以从HTML或XML文件中提取数据的Python库。它能够通过你喜欢的转换器实现惯用的文档导航,查找,修改文档的方式。(官方)beautifulsoup是一个解析器,可以特定的解析出内容,省去了我们编写正则表达式的麻烦。这里我们用的是bs4:1、导入模块:frombs4importbea......