北大陈斌Python算法笔记（一）

前言

?作者简介：被吉师散养、喜欢前端、学过后端、练过CTF、玩过DOS、不喜欢java的不知名学生。 ?个人主页：红中 ?不就是蓝桥杯嘛，干他！！我堂堂 

线性结构

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

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

新的数据项加入到数据集中时，只会加入到原有某个数据项之前或者之后，不会加到其他特殊的空间中

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

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

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

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

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

 接下来从四个有代表性的来研究数据结构，分别是：

1. 结构栈
2. 队列
3. 双端队列
4. 列表

这些结构的共同点在于他们都是线性结构，只存在先后的次序关系

栈抽象数据类型以及Python实现

什么是栈

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

这一端叫

栈顶(top)

另一端叫

栈底(base)

 日常生活中的栈

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

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

 怎么说呢，就类似于从箱子里取书吧

如果想拿最底下的，你总不能把箱子拆了

那就得从第一本开始往外拿

这种次序被称为后进先出

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

栈的特性：反转次序

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

来观察一个由混合的python组成的原生栈

 左侧的1st、2st等是放入的顺序，右侧则是取出顺序

8.4为栈顶数据，4为栈底数据

抽象数据类型

抽象数据类型“栈”

是一个有次序的数据集，每个数据项只从“栈顶”一端加入数据集中、从数据集中移除，栈具有后进先出的特性(简称为LIFO)

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

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

push(item):将item加到栈顶，无返回值

pop():移除顶端数据并返回，栈被修改

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

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

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

以下为应用例子