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:咱们都是阳沟里的虫子,但总还是得有人俯视星空。