共计 7744 个字符，预计需要花费 20 分钟才能阅读完成。
Java 八大数据结构之数组，栈，队列
一：介绍
数据结构是计算机存储，组织数据的形式，指相互之间存在一种或多种特定的数据元素的汇合
二: 数组 (Array)
数组是用来寄存同一种数据类型的汇合，留神只能寄存同一种数据类型 (Object 类型数组除外)
数组申明
形式一：
数据类型 [] 数组名称 =new 数据类型[数组长度];
// 申明一个数组长度为 5，只能寄存 int 类型的数据
int[] num=new int[5];
// 给数组第二个元素赋值
num[1]=12;
// 输入第一个元素和第二个元素，后果 0,12 默认没赋值的是 0
System.out.println(num[0]);
System.out.println(num[1]);
// 后果
System.out: 0
System.out: 12
String[] ss=new String[4];
ss[0]="Rocky";
System.out.println(ss[0]);
System.out.println(ss[1]);
// 后果
System.out: Rocky
System.out: null
// 能够看到：int：默认是 0，String: 默认是 null,boolean: 默认是 flase形式二：
数据类型 [] 数组名称 = {数组元素 1，数组元素 2，……}
int[] ss= {1,4,3,5,7,3};
for (int i=0;i<ss.length;i++){System.out.println(ss[i]);
}
自定义一个数组的实现，实现数组的增删改查
public class MyArray {
// 定义一个数组
private int[] intArray;
// 定义数组的理论无效长度
private int elems;
// 定义数组的最大长度
private int length;
// 默认结构一个长度为 50 的数组
public MyArray() {
elems = 0;
length = 50;
intArray = new int[length];
}
// 构造函数，初始化一个长度为 length 的数组
public MyArray(int length) {
elems = 0;
this.length = length;
intArray = new int[length];
}
// 获取数组的无效长度
public int getSize() {return elems;}
// 增加数组
// 假如操作人是不会增加反复元素的，如果有反复元素对于前面的操作都会有影响
public boolean add(int value) {
// 增加元素默认是从角标 elems，0 开始增加
if (elems == length) {return false;} else {intArray[elems] = value;
elems++;
}
return true;
}
// 依据下标获取元素，查找下标值在数组下标无效范畴内，返回下标所示意的元素，查找下标超出数组下标有效值，提醒拜访下标越界
public int get(int i) {if (i < 0 || i > elems) {System.out.println("拜访下标越界");
}
return intArray[i];
}
// 查找元素，查找的元素如果存在则返回下标值，如果不存在，返回 -1
public int find(int searchValue) {
int i;
for (i = 0; i < elems; i++) {if (intArray[i] == searchValue) {break;}
}
if (i == elems) {return -1;}
return i;
}
// 删除元素，果要删除的值不存在，间接返回 false; 否则返回 true，删除胜利
public boolean delete(int value) {int k = find(value);
if (k == -1) {return false;} else {if (k == elems - 1) {elems--;} else {
// 删除元素最要害的是遍历元素，并替换删除元素之后坐标的数值
for (int i = k; i < elems - 1; i++) {intArray[i] = intArray[i + 1];
}
elems--;
}
return true;
}
}
// 批改数据, 批改胜利返回 true，批改失败返回 false
public boolean modify(int oldValue, int newValue) {int i = find(oldValue);
if (i == -1) {System.out.println("须要批改的数据不存在");
return false;
} else {intArray[i] = newValue;
return true;
}
}
/**
* 遍历显示元素
*/
public void display() {for (int i = 0; i < elems; i++) {System.out.print(intArray[i] + " ");
}
System.out.println();}
}调用
// 创立自定义封装数组构造，数组大小为 4
MyArray array=new MyArray(4);
// 增加 4 个元素
array.add(3);
array.add(5);
array.add(6);
array.add(7);
// 显示数据
array.display();
// 依据下标为 0 的元素
int i = array.get(0);
System.out.println(i);
// 删除 7 的元素
array.delete(7);
// 将元素 6 批改为 12
array.modify(6, 12);
array.display();
// 后果
System.out: 3 5 6 7
System.out: 3
System.out: 3 5 12 数组一旦创立后，大小就固定了，不能动静扩大数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，前面数据个数减少了又增加不进去了。
二维数组
定义：二维数组其实就是一个元素为一维数组的数组；
// 形式一
int a[][] = new int[3][4];
int[][] b = new int[3][4];// 个别应用
int[] c[] = new int[3][3];
b[0][0]=1;
b[0][1]=5;
System.out.print(b[0][0]+",");
System.out.print(b[0][1]+",");
System.out.print(b[3][6]+","); //java.lang.ArrayIndexOutOfBoundsException: length=3; index=3
// 后果
System.out: 1,5,
// 形式二
int d[][] = {{1, 3, 5, 7}, {9, 11, 13, 15}, {17, 19, 21, 23}};
// 遍历后果
for(int x=0;x<d.length;x++){for(int y=0;y<d[x].length;y++){System.out.print(d[x][y]+",");
}
System.out.println();}
// 后果
System.out: 1,3,5,7,
System.out: 9,11,13,15,
System.out: 17,19,21,23,
// 形式三
int e[][] = new int[3][];
e[0] = new int[2];
e[1] = new int[2];
e[2] = new int[2];
三：栈（Stack）
栈（英语：stack）又称为堆栈或重叠，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的非凡线性表。它依照先进后出的准则存储数据，先进入的数据被压入栈底，最初的数据在栈顶，须要读数据的时候从栈顶开始弹出数据（最初一个数据被第一个读出来）。栈具备记忆作用，对栈的插入与删除操作中，不须要扭转栈底指针。
栈是容许在同一端进行插入和删除操作的非凡线性表。容许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入个别称为进栈（PUSH），删除则称为退栈（POP）
因为重叠数据结构只容许在一端进行操作，因此依照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。
自定义实现一个栈，能够出栈，入栈，能够扩容，能够拜访栈顶数据
public class MyStack {
// 存储元素的数组, 申明为 Object 类型能存储任意类型的数据
private Object[] elementData;// 数组
private int maxSize;// 栈最大数量
private int top;// 栈顶的指针
public MyStack() {this.elementData = new Object[10];
this.top = -1;
this.maxSize = 10;
}
public MyStack(int initialCapacity) {if (initialCapacity < 0) {throw new IllegalArgumentException("栈初始容量不能小于 0:" + initialCapacity);
}
this.elementData = new Object[initialCapacity];
this.maxSize = initialCapacity;
top = -1;
}
// 压入数据
public Object push(Object value) {
// 是否须要扩容
isGrow(top + 1);
elementData[++top] = value;
return value;
}
// 弹出栈顶数据
public Object pop() {Object obj = peek();
remove(top);
return obj;
}
// 拜访栈顶数据
public Object peek() {if(top == -1){throw new EmptyStackException();
}
return elementData[top];
}
// 判断栈是否为空
public boolean isEmpty() {return (top == -1);
}
// 删除栈顶元素
public void remove(int top){
// 栈顶元素置为 null
elementData[top] = null;
this.top--;
}
// 判断栈是否满了
public boolean isFull() {return (top == maxSize - 1);
}
/**
* 是否须要扩容，如果须要，则扩充一倍并返回 true，不须要则返回 false
*
* @param minCapacity
* @return
*/
public boolean isGrow(int minCapacity) {
int oldCapacity = maxSize;
// 如果以后元素压入栈之后总容量大于后面定义的容量，则须要扩容
if (minCapacity >= oldCapacity) {
// 定义扩充之后栈的总容量
int newCapacity = 0;
// 栈容量扩充两倍 (左移一位) 看是否超过 int 类型所示意的最大范畴
if ((oldCapacity << 1) - Integer.MAX_VALUE > 0) {newCapacity = Integer.MAX_VALUE;} else {newCapacity = (oldCapacity << 1);// 左移一位，相当于 *2
}
this.maxSize = newCapacity;
int[] newArray = new int[maxSize];
elementData = Arrays.copyOf(elementData, maxSize);
return true;
} else {return false;}
}
}调用
MyStack stack = new MyStack(3);
stack.push(2);
System.out.println(stack.peek());
stack.push("Rocky");
stack.push(true);
stack.push("fight");// 超过了 3 个主动扩容
// 拜访栈顶数据
System.out.println(stack.peek());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.peek());
// 判断栈是否为空
boolean aa=stack.isEmpty();
System.out.println(aa);
// 后果
System.out: 2
System.out: fight
System.out: 2
System.out: false
// 利用栈实现字符翻转
MyStack myStack = new MyStack();
String str = "HelloWorld";
char[] cha = str.toCharArray();
for(char c : cha){myStack.push(c);
}
while(!myStack.isEmpty()){System.out.println(myStack.pop());
}四：队列（Queue）
队列（queue）是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只容许在一端插入，在另一端删除，所以只有最早进入队列的元素能力最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
1. 与栈不同的是，队列中的数据不总是从数组的 0 下标开始的，移除一些队头 front 的数据后，队头指针会指向一个较高的下标地位
2. 咱们再设计时，队列中新增一个数据时，队尾的指针 rear 会向上挪动，也就是向下标大的方向。移除数据项时，队头指针 front 向上挪动。那么这样设计如同和现实情况相同，比方排队买电影票，队头的买完票就来到了，而后队伍整体向前挪动。在计算机中也能够在队列中删除一个数之后，队列整体向前挪动，然而这样做效率很差。咱们抉择的做法是挪动队头和队尾的指针。
自定队列实现增删
3. 如果向第②步这样挪动指针，置信队尾指针很快就挪动到数据的最末端了，这时候可能移除过数据，那么队头会有空着的地位，而后新来了一个数据项，因为队尾不能再向上挪动了，那该怎么办呢？
4. 为了防止队列不满却不能插入新的数据，咱们能够让队尾指针绕回到数组开始的地位，这也称为“循环队列”。
弄懂原理之后实现：
public class MyQueue {private Object[] queArray;
// 队列总大小
private int maxSize;
// 前端指针，队头指针
private int front;
// 后端指针，队尾指针
private int rear;
// 队列中元素的理论数量
private int nItems;
public MyQueue(int size){
maxSize=size;
queArray=new Object[maxSize];
front=0;
rear=-1;
nItems=0;
}
// 队列新增数据
public void insert(int value){if (isFull()){System.out.println("队列已满！！！");
}else {
// 如果队尾部指向顶了，那么循环回来，执行队列的第一个元素
if (rear==maxSize-1){rear=-1;}
// 队尾指针加 1，而后在队尾指针处插入新的数据
queArray[++rear] = value;
nItems++;
}
}
// 移除数据
public Object remove(){
Object removeValue = null ;
if (!isEmpty()){removeValue=queArray[front];
// 把队头数据置为空
queArray[front]=null;
// 队头指针 +1
front++;
if (front==maxSize){
// 如果队头为总容量大小，置为 0
front=0;
}
nItems--;
return removeValue;
}
return removeValue;
}
// 返回队列的大小
public int getSize(){return nItems;}
// 查看对头数据
public Object peekFront(){return queArray[front];
}
// 判断队列是否为空
public boolean isEmpty(){return (nItems ==0);
}
// 判断队列是否满了
public boolean isFull(){return (nItems == maxSize);
}
}
调用
MyQueue queue = new MyQueue(3);
queue.insert(1);
queue.insert(2);
queue.insert(3);//queArray 数组数据为[1,2,3]
System.out.println(queue.peekFront()); //1
queue.remove();//queArray 数组数据为[null,2,3]
System.out.println(queue.peekFront()); //2
queue.insert(4);//queArray 数组数据为[4,2,3]
// 为什么是 [4,2,3] 不是[2,3,4]
// 应为队列队尾满了当前会循环到后面去
/* 如果队尾部指向顶了，那么循环回来，执行队列的第一个元素
if (rear==maxSize-1){
rear=-1;
// 这个决定的, 队尾的指针变了，到了最初了，就会循环回去，然而队头的指针是没有变动的
}*/
System.out.println(queue.peekFront()); //2，应为队头指针没有变动
queue.remove();//queArray 数组数据为[4,null,3]
queue.remove();//queArray 数组数据为[4,null,null]
queue.insert(5);//queArray 数组数据为[4,5,null]
queue.insert(6);//queArray 数组数据为[4,5,6]
queue.insert(7);// 队列已满,queArray 数组数据为[4,5,6]
System.out.println(queue.peekFront()); //4
// 后果
System.out: 1
System.out: 2
System.out: 2
System.out: 队列已满！！！System.out: 4 请大家先看看什么是前缀表达式，中断表达式，后缀表达式：这三种表达式其实就是算术表达式的三种写法，以 3+4- 5 为例
前缀表达式：操作符在操作数的后面，比方 +-543（计算机从右向左扫描）
中断表达式：操作符在操作数的两头，这也是人类最容易辨认的算术表达式 3+4-5
后缀表达式：操作符在操作数的前面，比方 34+5-（计算机从左向右扫描）
END: 咱们都是阳沟里的虫子, 但总还是得有人俯视星空。
正文完