1、数组
定义：数组指的就是一组相同类型的变量集合。这些变量可以按照统一的方式进行操作。（如for循环
数组是一种引用数据类型，所以使用前必须先开辟空间，否则会有NullPointerException
两种定义语法：
1、动态初始化。（只开辟空间未赋值）
如
Int [] a = new Int[5]; // 等同于 Int a [] = new Int[5];
Int a[] = null , a = new Int[5]; // 等同于 Int []a = null , a = new Int[5]; 区别：
前一种是一步开辟，即直接在内存中申请开辟5个连续的空间，再对5个空间赋予该数组数据类型的默认值；
后一种是分步开辟，即先在内存申请了空间，new时再开辟5个连续的空间，再对5个空间赋予该数组数据类型的默认值；
2、静态初始化。（开辟空间且赋值）
如：
int []a = new int[]{1,2,3,4,5}; //完整格式（亦可 a[]
int a[] = {1,2,3,4,5}; //简化格式 (亦可 []a此处建议使用完整模式，因为可以使用匿名数组。
数组是引用数据类型，可以发生引用传递。即：同一块堆内存空间可以被不同的栈内存所指向。
若赋值另一个数组 b = a，那么它们将指向同一块堆内存。也就是说，无论是 引用a 还是 b 对堆中的对象进行改变，另一方都会随着变化。
（注：这一特征区别与Integer、String、Double等引用数据类型截然不同，作为不可变类，改变时往往改变的不是值，而是引用）
注：二维数组需要行索引和列索引来定位，定义语法：
**动态初始化：**
int a[][] = new int[2][2]; //当然还有分步开辟方式**静态初始化：**
int a[][] = new int[2][2] { {2,2}, {2,2} }; //当然也有简化模式总结：
优点：
1、按照索引查询元素速度快
2、遍历数组方便
缺点：
1、数组的大小固定
2、数据类型单一
3、添加，删除的操作慢。（因为要移动其他的元素。
适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。
栈：一种特殊的线性表
安装存储方式分为： 顺序栈（基于数组实现，长度固定
链式栈（基于链表实现，需要自己定义节点，长度不固定
个人认为：
当使用数组实现栈/队列，指针 top/rear 总指向 栈顶/队尾 元素的下一个元素，即空元素；而使用链式时，总指向 栈顶/队尾 元素。
记得出栈/出队时要判空，（若用动态数组还要判断是否缩容）；入栈/入队要判满（若使用动态数组还要判断是否扩容；若基于链表实现则无需判满）。
特点：后进先出。只允许从表的一端进行插入、删除
因为在进栈只需要移动一个变量存储空间，所以它的时间复杂度为O(1)，但是对于出栈分两种情况，栈未满时，时间复杂度也为O(1)，但是当栈满时，需要重新分配内存，并移动栈内所有数据，所以此时的时间复杂度为O(n)。
栈的应用：递归、后缀表达式运算、括号匹配
注：验证括号匹配时，若只有一种类型括号，则遇左括号push，遇右括号pop，最后看isEmpty==true即可；
若有多种，则要使用for循环，栈空时push，然后判断栈顶元素是否与char[i]配对；若是，则pop；否则继续push，再比较…
链式栈
//定义栈的接口
package starkTest;
public interface Stark<T> {
public T pop();
public void push(T t);
public T getTop();
public boolean isEmpty();
}//栈的实现及验证（包括定义节点
public class StarkImp<T> implements Stark<T>{
int size;
Node top; //
class Node{
private T element;
private Node next;
public Node(T element, Node next) {
this.element = element;
this.next = next;
}
public Node getNext() {
return next;
}
public T getElement() {
return element;
}
}
public StarkImp() {
size = 0;
top = null;
}
public StarkImp(Node top) {
size = 0;
this.top = top;
}
public T getTop() {
return top.getElement();
}
public boolean isEmpty() {
return top == null;
}
public T pop() {
if(isEmpty()) {
return null;
}
T t = top.getElement();
top = top.getNext();
size--;
return t;
}
public void push(T t) {
Node node = new Node(t, top);
top = node;
size ++;
}
public static void main(String[] args) {
StarkImp<String> si = new StarkImp<String>();
si.push("1");
si.push("2");
si.push("3");
si.push("4");
for(int i=si.size; i>=0; i--) {
System.out.println(si.pop());
}
}
}队列
也是一种受限的线性结构。只能在队尾插入、队首删除。
类似于栈，根据存储安装方式可分为：
1、基于数组的顺序队列/ 循环队列；
2、基于链表的顺序队列/ 循环队列；
（ps：使用链表的话自身亦可动态增长，但每次都要创建/删除节点，效率较低；
而使用数组则长度固定，或者每次都要重新开辟新空间；依情况选择）
应用：多线程阻塞队列管理等；
顺序队列使用数组来实现时，可以自己定义一个动态数组提高灵活性。
即插入时 判定数组已满时，扩容为2倍；删除时判定数组使用不超过1/4时，缩容为1/2（注意要判断数组长度/2不等于0才可以）。
而之所以是1/4，是因为若设为1/2的话，假如数组原本长度为10，加一元素扩容为20，此时再删一元素，又会触发缩容操作，频繁的扩容缩容太消耗资源。
循环队列：对于数组实现的队列来说，当队首删除一元素时，后面所有元素都要向前移动，此时时间复杂度为O（n）。为了改善这个情况，可以使用循环队列。循环队列删除时只需 head = (head +1) % length ，把队首元素空出，可供后续插入使用。
对循环队列来说，由于 head = tail 的有队空队满的双重意义，因此规定当数组剩一个储存单元时即为满，即 （tail + 1）% length = head % length 时为满。
之所以要让其对数组容量求余，是因为当队首元素删除后，其位置有可能会被新插入的元素占用，此时 tail +1 会造成下标溢出。
使用数组方式实现循环队列：
//定义队列的各种方法
public interface MyQueue {
boolean isEmpty();
boolean isFull();
void enQueue(int i);
int outQueue();
}//因泛型不能实例化，使用数组传参方式不能从根本解决问题，且尚未寻找方案，故此处使用int类型
//实现类
public class QueueImp implements MyQueue{
int size;
int nowLength = 0;
int[] queue;
int head = 0;
int tail = 0;
public QueueImp(int size) {
this.size = size;
queue = new int[size];
}
public boolean isEmpty() {
return nowLength == 0;
}
public boolean isFull() {
return nowLength == size;
}
public void enQueue(int i) {
if(isFull()) {
reSize(size*2);
}
queue[tail%size] = i;
tail++;
nowLength++;
}
public int outQueue() {
if(isEmpty()) {
System.out.print("队列为空");
return 0;
}
if(nowLength == size/4 && size/2 != 0) {
reSize(size/2);
}
int i = queue[head];
head = (head+1)%size;
size--;
return i;
}
public void reSize(int newSize) {
int []newQueue = new int[newSize];
int i = 0;
//此处要注意，由于循环队列的特性，此时的数据不一定从下标为0处开始
//并且，考虑到可能会缩容，在新数组中从应该从0开始放数据
for(int j=head; j<size+head; j++) {
newQueue[i] = queue[j];
i++;
}
queue = newQueue;
size = newSize;
head = 0;
tail = nowLength-1;
}
}//测试类
public class Main {
public static void main(String[] args) {
QueueImp queue = new QueueImp(4);
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.enQueue(5);
for(int i=0; i<queue.nowLength; i++) {
System.out.print(queue.outQueue());
}
}
}
结果为：12345
ps：泛型数组的使用过于繁杂，直接使用 ArrayList ，自带add（）、remove（）、get（）香的多。
个人总结：无论是队列还是栈，对于核心操作 出/入，都是同一个套路：
出：
1、判空；（使用动态数组时判是否缩容）
2、获取元素数据
3、数组实现：改变指针索引；
链表实现：改变指针指向；
4、长度–；
入：
1、判满；（使用动态数组时判是否缩容）
2、数组实现：元素赋值；
链表实现：Top/Tail = new Node（…）；改变指针指向；
3、长度++；
栈和队列都是只能添加、删除，不能查找、修改的。
链表
定义：物理存储单元上非连续的存储结构，利用指针来实现数据的逻辑顺序。
分为：单链表、双向链表、循环链表
每个节点由 数据元素 + 指针 构成。
优点：无需初始化、无大小限制；
添加、删除简单，只需要改变指针指向。
缺点：查找时要一个个遍历，最差情况下时间复杂度达O（n）；
由于还要存放指针，空间占用较多。
适用于：
需要频繁添加删除，数据量较小的情况。（与数组相反呢）
关于单链表的一些操作代码在这篇文章：
添加链接描述
ps：判断链表的有无环 、交点问题要善利用两指针。
转载：https://blog.csdn.net/weixin_45003809/article/details/105450779