1.数据结构分类：
1.1 按逻辑结构分类：
1.2 按存储结构分类：
2.线性表
2.1 定义
2.2 分类
2.3 线性表的⼀些常⽤操作
2.4 选择合适的数据结构（顺序表和链表）
3.数组
3.1 Java数组的介绍
3.2 查看数组的底层实现
4.栈（后进先出表）
4.1 定义
4.2 栈的实现方式
4.3 栈的举例1：字符串反转
4.4 栈的举例2：括号匹配
4.5 栈的举例3：表达式求值
4.6 栈的举例4：浏览器的历史记录
5.队列
5.1 定义
5.2 队列的实现方式
5.3 队列的常用方法
5.4 应用场景
6.栈和队列总结
1.数据结构分类：
1.1 按逻辑结构分类：
|----线性结构（线性表)
|----顺序表
|----字符串
|----数组
|----栈
|----队列
|----链表
|----单链表
|----双链表
|----循环链表
|----非线性结构
|----树
|----图
|----多维数组
1.2 按存储结构分类：
|----顺序存储结构
|----链式存储结构
|----散列存储结构
|----索引存储结构
2.线性表
2.1 定义
线性表(List)全名为线性存储结构，其中数据元素之间的关系是⼀对⼀的关系，即除了第⼀个和最后⼀个数据元素之外，其它数据元素都是⾸尾相接的。它具备以下特点
1. 线性表(List)是零个或多个数据元素的集合
2. 线性表中的数据元素之间是有顺序的
3. 线性表中的数据元素个数是有限的
4. 线性表中的数据元素的类型必须相同
2.2 分类
线性表的分为顺序表和链表（具体分类见章节1.1）
顺序表：元素的存储空间是连续的。在内存中是以顺序存储，内存划分的区域是连续的。如下图左
链表：元素的存储空间是离散的，单独的（物理地址层面上），它们可以通过在逻辑上指针的联系使得它成为了整体的链表。存储上也分为数据和指针两部分。如下图右
2.3 线性表的⼀些常⽤操作
1. 创建线性表
2. 销毁线性表
3. 清空线性表
4. 将元素插⼊线性表
5. 将元素从线性表中删除
6. 获取线性表中某个位置的元素
7. 获取线性表的⻓度
2.4 选择合适的数据结构（顺序表和链表）
基于存储规模的考虑：
链表不⽤事先估计存储规模，但链表的存储密度较低
顺序表需要考虑maxSize，过⼤造成浪费，过⼩造成溢出
基于运算的考虑：
针对按序号访问操作，顺序表的时间性能为O(1)，⽽链表的时间性能为O(n)
而对于大数据量的插入和删除。顺序表需要移动表中平均一半以上的元素。链表显然优于顺序表
基于环境的考虑：
顺序表容易实现，任何⾼级语⾔中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，这也是需要考虑的⼀个因素。
3.数组
3.1 Java数组的介绍
引用类型，定长，一旦创建大小无法改变，也是一个类，拥有超类Object中的所有方法
注意：length并不是数组的成员属性（因为通过反射机制无法拿到）
3.2 查看数组的底层实现
idea中安装jclasslib插件查看字节码
4.栈（后进先出表）
4.1 定义
栈是一种只能在⼀端进⾏插⼊和删除操作的特殊线性表。
1.后进先出，对栈的插⼊与删除操作中，不需要改变栈底指针
2.允许插入和删除操作的⼀端称为栈顶(top)，另⼀端为栈底(bottom)；栈底固定，⽽栈顶浮动
3.栈中元素个数为零时称为空栈
4.数据⼊栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短
5.栈不需要⽐较和移动操作
4.2 栈的实现方式
栈可以用顺序存储，也可以?链式存储，分别称为顺序栈和链栈。
4.3 栈的举例1：字符串反转
4.4 栈的举例2：括号匹配
假设表达式中只允许两种括号：()、{}；检测括号嵌套是否正确
思路
1.出现左括弧则进栈；
2.出现右括弧则⾸先检测栈是否为空；
若栈空则表明此右括弧多余，表达式不匹配。
否则和栈顶数据⽐较，若匹配则栈顶出栈。
否则表明表达式不匹配；
3.最后若栈空，则表明匹配成功；否则表明不匹配。
4.5 栈的举例3：表达式求值
计算表达式: 6* (2 + 3 )*8 + 5
思路：
1.使用两个栈，stack0用于存储操作数，stack1用于存储操作符
2.从左往右扫描，遇到操作数入栈stack0，遇到操作符时，如果优先级低于或等于栈顶操作符优先级，则从stack0弹出两个元素进行计算，并压入stack0，继续与栈顶操作符的比较优先级
如果遇到操作符高于栈顶操作符优先级，则直接入栈stack1
3.遇到左括号，直接入栈stack1，遇到右括号，则直接出栈并计算直到弹出左括号
步骤1. 从左向右扫描表达式 6* ( 2 + 3 )*8 + 5， 首先6 和 * 分别入栈（图1左）
步骤2. 继续往后扫描，遇到 ( 直接入栈，遇到 2 入栈，遇到 + 入栈，遇到 3 入栈（图1右）
步骤3. 向后扫描，遇到 )，它与栈顶操作符 + 相比，优先级要高，因此将 + 出栈，弹出两个操作数3 和2 ，计算结果得到 5 ，并入栈（图2左）
步骤4. 继续出栈,直到弹出左括号（图2右）
步骤5. 继续扫描，第二个 * 入栈, 与 stack1 栈顶 * 优先级相等, 故弹出 5 和 6 计算结果为30（如图3左）
步骤6. 继续扫描 8 入栈，但是 + 优先级小于 * ，弹出结果240，将其重新入栈，之后 + 入栈（如图3中）
步骤7.最后 5 入栈，发现stack1 不为空，弹出操作符 + 和两个操作数，并进行计算，得到 245 ，入栈，得到最终结果（如图3右）
4.6 栈的举例4：浏览器的历史记录
1. 顺序查看了a->b->c三个页面，将a->b->c压入栈X
2. 点击后退按钮,从c->b->a 将 c, b 放入栈Y中
3. 点击前进按钮, 将 b 放入到栈X中
4. b 跳转新到新页面 d ,则需要清空栈Y
5.队列
5.1 定义
队列（queue）是⼀种特殊的线性表，特殊之处在于它只允许在表的前端（front）进⾏删除操作，⽽在表的后端（rear）进⾏插⼊操作
5.2 队列的实现方式
Queue是⼀种很常⻅的数据结构类型，在Java⾥⾯Queue是⼀个接⼝，它只是定义了⼀个基本的Queue应该有哪些功能规约。实际上有多个Queue的实现，有的是采⽤线性表实现，有的基于链表实现。还有的适⽤于多线程的环境
1. 单向队列（Queue）：只能在⼀端插⼊数据，另⼀端删除数据。
2. 双向队列（Deque）：队列的两端都可以进⾏插⼊数据和删除数据操作。
5.3 队列的常用方法
5.4 应用场景
1. 消息队列
2. 排队进站
3. Redis 队列实现秒杀/抢购
6.栈和队列总结
1. 栈、队列通常是⽤来简化某些程序操作的数据结构，⽽不是主要作为存储数据的；
2. 在这些数据结构中，只有⼀个数据项可以被访问；
3. 栈允许在栈顶压⼊（插⼊）数据，在栈顶弹出（移除）数据，但是只能访问最后⼀个插⼊的数据项，也就是栈顶元素；
4. 队列（单向队列）只能在队尾插⼊数据，队头删除数据，并且只能访问队头的数据。⽽且队列还可以实现循环队列，它基于数组，数组下标可以从数组末端绕回到数组的开始位置；
5. 这些数据结构都能由数组实现，但是可以⽤别的机制（后⾯讲的链表、堆等数据结构）实现。
