目录
一.线性表的概念
线性表是0个或n个相同数据类型的有限序列
构成线性表的条件：除了头尾外每个结点有且仅有一个前驱和后继。
二.线性表的关系及分类
线性表按物理存储结构可分为顺序存储结构和链式存储结构。
基本顺序存储结构为数组，基本链式存储结构为链表。
以数组为底层可实现顺序表和栈及队列。
以链表为底层可实现栈和队列。
其关系图大致如下：
三.数组与顺序表
封装顺序表的使用：
定义
List<类型参数> 顺序表名 = new ArrayList<>();
ArrayList<类型参数> 顺序表名 = new ArrayList<>();
【ArrayList实现了List接口】
顺序表的底层实现：
底层是对数组的处理较简单
顺序表底层需要实现的一般方法:
(其余可自行到库中查看）
四.链表
链表的一般底层实现：
通过内部类定义结点与C语言中结构体类似
要实现的一般方法有：
1.静态链表(链表的的数组底层实现）
静态链表的实现的每一个结点需要值域和游标（游标用来存储下一节点的下标） 
2.循环链表
链表的尾部指针域指向头结点
3.双向链表
在单向链表的属性中多了一个指向前一个结点的“指针”.
五.栈
1.栈的概念
只在表首进行删除和插入操作的线性表
2.栈的底层实现
数组实现：
需要一top变量指示栈顶下标（栈空为-1，栈满为n)
大致框架如下，方法（push,pop,peek,empty等可参考库函数尝试实现)
链表实现：
以“头指针”指示栈顶，对头指针及其前一个结点进行操作即可实现栈的基本方法
基本结构如下：
3.共享空间栈
用于底层为数组实现的栈节省空间，两栈合并。
结构大致如下：
可定义top1,top2分别表示两栈顶当两栈顶相遇（top1+1=top2)时栈满。
当top1 = -1且top2 = n时栈空（n为栈大小）。
4.逆波兰表达式（后缀表达式）
中缀转后缀：
一种较容易推导方法为加括号，通过栈推导可自行查资料
5.栈与递归
递归的底层可以理解为一个栈，每次递归时所得数据存储在栈中直到递归出口再将数据依次弹出
六.队列
1.队列概念
只在头部进行删除尾部进行插入的线性表 （先进先出）
2.队列的底层实现
数组实现：
与栈相似多出一个属性指示队尾，对队首队尾进行操作
链表实现：
单向链表实现时与栈相似都是对头指针进行操作，只是加入删除元素的方式有所不同
双向链表实现队列较为快捷可同时对头尾指针进行操作。
3.循环队列
以数组为底层实现循环队列时防止假满状态（队尾元素删除后其空间无法利用，头指针一直向前走无法回头）实现空间重复利用。定义front rear指示队列首尾部
循环队列大小计算公式：
ret = (front - rear + maxSize) % maxSize
循环队列循环的实现：
添加删除元素时分别对尾头指针进行操作；
添加移动尾的下标：
(rear + 1) % maxSize
删除移动头的下标：
（front + 1) % maxSize
循环队列满空的判断：
空时front = rear
满时判断：
1.标记法
flag=false 时为空
flag=true时为满
2.留空法
留下一个位置不放元素
当(rear + 1) % maxSize = front 时为满
通过以上操作我们可以发现下标只在（0 ~ maxSize - 1)范围内变化，从而实现循环
七.链式储存与循序储存
顺序存储结构如数组及以其为底层实现的结构：
1.空间大小确定
2.如需查找，时间复杂度仅为O(1)较易进行
3.插入操作需移动插入位置后所有元素，时间复杂度为O(n),不便
链式存储结构如链表及以其为底层实现的结构：
1.大小不固定
2.只可按一定顺序进行查找O(n)不便
3.插入时找的指定元素时O(n)插入时O(1),插入愈多其优势越明显
故选用结构时需据实际情况。
标签：JAVA,线性表,队列,链表,实现,数组,数据结构,底层 From： https://blog.csdn.net/startshining_ys/article/details/145321224