数据的结构

贺小武

栈：（装子弹的原理）是一种数据结构，只能在一端进行插入和删除操作的特殊线性表。
1.栈顶允许进行插入和删除操作的一段
2.方法：push压栈，pop出栈
3.实现栈操作的方式：数组，LinkedList ，deque

队列：（排队的原理）先进先出，front：记录数组头-记录取值的游标，real记录数组的尾-记录存值的游标，使用方法：一个存 一个取的话，那么取过的地方的空间又浪费了，所以要做出环形队列，循环使用资源。使用——移位：排队向前挪一个可以用来节省资源
1.代码实现：
/*数组队列的实现*/
public class QueueArr {
    private int[] arr;
    int index = 0;

    public QueueArr(int len) {
        arr = new int[len];
    }

    // 1.入队列 添加
    public void add(int zhi) {
        arr[index] = zhi;
        index++;
    }

    // 判断队列是否是空队列
    public boolean isNull() {
        return index == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return index == arr.length;
    }

    // 2.出队列，取
    public int pop(int i) {
        if (isNull()) {
            throw new RuntimeException("队列为空，不能取出数据");
        }
        // 判断 如果有值
        int zhi = arr[0];
        // 移位：排队向前挪一个
        for (int j = 1; j < index; j++) {
            arr[j - 1] = arr[j]; // 移位赋值
        }
        index--; // 利用了刚刚用的空间
        return zhi;
    }

    // 遍历数组
    public void list(){
        for (int i = 0; i < index; i++) {
            System.out.print(arr+"  ");
        }
        System.out.println();
    }
}

链表：
单向链表：单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向源头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点
2.两个部分解析：第一个部分(data)保存或者显示关于节点的信息，第二个部分存储下一个节点的地址，最后一个节点存储地址的部分指向空值
3.插入：只知道链表头节点的信息，在头部添加

双端链表：只能从一个方向遍历，相当于单向链表多了一个对尾节点的引用

二叉树：
三大遍历：前序遍历，中序遍历，后序遍历

递归：
1.是什么？运行的过程中调用自己
2.把大问题化解成小问题来解决，递归策略值需要少量的程序就可以描述出解题过程中所需要的多次重复计算，大大减少程序的代码量
3.递归三要素：1.边界条件，2.递归前进段，3.递归返回段，当边界条件不满足时，递归前进，边界条件满足时，递归返回

序列化的作用：
1.是什么？把对象转换成二进制的过程，是为了网络传输

红黑树：
1.是什么？红黑节点并能自平衡的二叉查找树