与代码的结构设计有着紧密关系
一个顺序结构的代码，时间复杂度是O(1), 即任务与算例个数 n 无关
空间复杂度 -- 廉价
与数据结构设计有关
数据结构 -- 考虑如何去组织计算机中一定量的数据。 数据结构连接时空，用空间换取时间。 数据处理 -- 了解问题，明确数据操作方法，设计出更加高效的数据结构类型
找到需要处理的数据，计算结果，再把结果保存下来
把结果存到新的内存空间中
把结果存到已使用的内存空间中
基本操作只有三个：增，删，查
增和删可以细分为数据结构的中间以及最后的增和删
查找可以细分为按照位置条件查找和数据数值特征查找
所有数据处理都是这些基本操着的组合和叠加
只有字典类型数据结构能在 O(1) 的时间复杂度内完成查找动作
回归问题本源，明确数据被处理的动作，来解决数据结构的问题
线性表 n 个具有相同特性的元素的有限序列，Linear List 数据元素之间的关系是一对一的关系
即除了头尾元素外，其它数据元素都是首尾相接的
这句话只适用大部分线性表，而不是全部
比如，循环链表尾的指针指向首位结点
实现方式
最常用的是链式表达，也叫线性链表或链表
每个结点包括具体的数据值和指向下一个结点的指针
单向链表，循环链表，双向链表，双向循环链表
新增和删除为 O(1) 时间复杂度，而查找为 O(n)
适合数据元素个数不确定，且经常进行新增和删除
链表的翻转，快慢指针的方法，是必须掌握的内容
使用数组实现，也叫顺序存储，顺序表
类别
一般线性表，可以自由的删除和添加结点
受限线性表，主要包含栈和队列
栈和队列是特殊的线性表，本质上他们都可以被看作是一类基本结构 线性表案例
链表的翻转
快慢指针
查找奇数个数的链表的中间位置结点的数值
判断链表是否有环
栈 后进先出的（限制后的）线性表，Last In First Out, Stack. 新增和删除操作只能在这个线性表的表尾进行，即在线性表基础上加了限制
新增: 压栈 push, which adds an element to the collection
删除: 出栈 pop, which removes the most recently added element
功能上，数组或者链表可以代替栈，但它们灵活性过高，数据量大时有风险 栈顶和栈底是用来表示这个栈的两个指针
栈顶 (top) 是表尾，用来输入数据
栈底 (bottom) 是表头，用来锁定栈内的某一单元的地址
栈有顺序表示和链式表示，分别称作顺序栈和链栈
顺序栈
数组的首元素存在栈底，尾元素放在栈顶
定义指针 top 来指示栈顶元素在数组的位置
可以借助数组来实现
栈中只有一个元素，则 top = 0
以 top 是否为 -1 来判定是否为空栈
栈顶 top 需小于栈的最大容量
出栈操作，只需要 top - 1 即可
链式栈
通常把栈顶放在单链表的头部
top 指针替换了链表原来的尾指针，去掉了头指针
用链表的方式实现
出栈操作，将 top 指针指向栈顶元素的 next 指针即可
对比栈和一般线性表
操作原理相似
时间复杂度一样
都依赖当前位置指针进行数据对象的操作
相同点：
区别：栈只能新增和删除栈顶的数据结点
栈的案例
判断括号字符串是否合法
浏览器页面访问的后退和前进
队列 先进先出 (限制后的) 线性表, First In First Out, Queue 新增和删除操作只能分别在队尾和队头进行
先进 - 队列的数据新增操作只能在末端进行, add
不允许在队列的中间某个结点后新增数据
先出 - 队列的数据删除操作只能在始端进行, remove
不允许在队列的中间某个结点后删除数据
队列适合面对数据处理顺序非常敏感的问题
可以确定队列长度最大值, 建议使用循环队列
无法确定队列长度时, 应考虑使用链式队列
front 和 rear 两个指针
队头 (front), 用来删除数据
队尾 (rear), 用来增加数据
队列有两种存储方式, 即顺序队列和链式队列
顺序队列
必须有一个固定的长度
实现删除的时间复杂度为 O(1)
使用 flag 来判断队列空或满
每次删除都需要把整个数组前移
时间复杂度为 O(n)
尾指针会向后移动
时间复杂度为 O(1)
数据在内存中也是顺序存储
依赖数组来实现
进行新增插入操作时,
如果只删除头的第一个元素时
使用循环队列
链式队列
让 front 指针指向头结点
头结点不存储数据, 只是辅助标识
数据依赖每个结点的指针互联
是离散存储线性结构
实际上就是尾进头出的单链线性表
在空间上更为灵活
依赖链表来实现
通常会增加一个头结点
当进行数据删除时, 实际删除的是头结点的后继结点
队列为空时, 头尾指针都指向头结点
对比队列和一般线性表
队列继承了线性表的优点和不足
是加了限制的线性表
队列案例
约瑟夫环 - Josephus problem
数组 数组可以看成是线性表的一种推广，它属于另外一种基本的数据结构 数组是数据结构中的最基本结构
几乎所有的程序设计语言都把数组类型设定为固定的基础变量类型。
可以把数组理解为一种容器，它可以用来存放若干个相同类型的数据元素。
例如：
存放的数据是整数型的数组，称作整型数组；
存放的数据是字符型的数组，则称作字符数组；
另外还有一类数组比较特殊，它是数组的数组，也可以叫作二维数组。
可以把普通的数组看成是一个向量，那么二维数组就是一个矩阵。
数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到。
数组的索引就是对应数组空间
在进行新增、删除、查询操作的时候，完全可以根据代表数组空间位置的索引值进行。
只要记录该数组头部的第一个数据位置，然后累加空间位置即可。
数组的基本操作具有增删困难、查找容易的特点，可以在任意位置增删数据，所以数组的增删操作会更为多样。
新增操作
若插入数据在最后，则时间复杂度为 O(1)
如果中间某处插入数据，则时间复杂度为 O(n)
删除操作
在数组的最后删除一个数据元素，则时间复杂度是 O(1)
在这个数组的中间某个位置删除一条数据, 时间复杂度为 O(n)
查找操作
如果只需根据索引值进行一次查找，时间复杂度是 O(1)
要在数组中查找一个数值满足指定条件的数据，则时间复杂度是 O(n)。
对比数组和链表