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：字符串反转

java代码实现

    4.4 栈的举例2：括号匹配

        假设表达式中只允许两种括号：()、{}；检测括号嵌套是否正确     

        思路
        1.出现左括弧则进栈；
        2.出现右括弧则⾸先检测栈是否为空；
            若栈空则表明此右括弧多余，表达式不匹配。
            否则和栈顶数据⽐较，若匹配则栈顶出栈。
            否则表明表达式不匹配；
        3.最后若栈空，则表明匹配成功；否则表明不匹配。

java代码实现

    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右）

图1

        步骤3. 向后扫描，遇到 )，它与栈顶操作符 + 相比，优先级要高，因此将 + 出栈，弹出两个操作数3 和2 ，计算结果得到 5 ，并入栈（图2左）

        步骤4. 继续出栈,直到弹出左括号（图2右）

图2

        步骤5. 继续扫描，第二个 * 入栈, 与 stack1 栈顶 * 优先级相等, 故弹出 5 和 6 计算结果为30（如图3左）

        步骤6. 继续扫描 8 入栈，但是 + 优先级小于 * ，弹出结果240，将其重新入栈，之后 + 入栈（如图3中）

        步骤7.最后 5 入栈，发现stack1 不为空，弹出操作符 + 和两个操作数，并进行计算，得到 245 ，入栈，得到最终结果（如图3右）

图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. 这些数据结构都能由数组实现，但是可以⽤别的机制（后⾯讲的链表、堆等数据结构）实现。