devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【入门必备】Java数据结构详解_java 数据结构编程

作者：从前慢现在也慢 | 2024-05-29 13:10:42

赞

踩

java 数据结构编程

文章目录

数据结构所必备的知识，适合入门学习，作者也是一边学习一边分享，如果觉得写的还不错的话，欢迎点一个收藏再走哦~~~，后续会出更多有关于数据结构与算法的文章，也请大家多多关注！

在这里插入图片描述

队列

队列最显著的特点就是先进先出。

  • 思路：
    使用front和rear两个指针，front永远指向队列头的前一个元素，rear指向队列尾。
    入队：rear后移，给数组赋值。
    出队：front后移，取出该数组。
    arr[front+1]为队列头部。
    在这里插入图片描述

代码实现

/**
 * arr[] 用数组来模拟队列。
 * maxSize 表示数组最大容量。
 * front 用于指向队列头。
 * rear 用于指向队列尾。
 */
public class ArrayQueue {
    private int []arr;
    private int maxSize;
    private int front;
    private int rear;
    public ArrayQueue(int maxSize){
        this.maxSize=maxSize;
        arr = new int[maxSize];
        front=-1;
        rear=-1;
    }
    // 判断队列是否满
    public boolean isFull(){
        return rear==maxSize-1;
    }
    //判断队列是否空
    public boolean isEmpty(){
        return rear==front;
    }
    //添加数据到队列。
    public void addQueue(int date){
        if(isFull()){
            System.out.println("False");
            return ;
        }
        rear++;
        arr[rear]=date;
    }
    //出队列
    public int getQueue(){
        if(isEmpty()){
            //由于返回int所以这里利用抛出异常。
            throw new RuntimeException("Error");
        }
        front++;
        return  arr[front];
    }
    // 显示队列的所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空的，没有数据~~");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

环形队列

这里可以直接参考之前写的一篇文章，里面讲的非常详细！
链接：环形队列详解

LRU

LRU（Least Recently Used，最近最少使用算法）

  • 传统的LRU算法
    • 用链表管理数据。
    • 当访问的数据在链表中，把链表中的数据移动到表头；当访问的数据不在链表中，从磁盘中读取数据，把数据放到链表头，同时还要淘汰LRU链表末尾的节点。
  • 操作系统中的LRU：页面置换算法中可以使用LRU页面置换算法，将最近最少使用的页面置换出内存。
  • MySQL中的LRU：InnoDB存储引擎中的Buffer Pool，使用LRU算法管理缓存页。
  • Redis中的LRU：Redis中的内存淘汰策略中，有LRU算法，将最近最少使用的key淘汰出内存。

MySQL和Redis都对传统的LRU算法做了一定的修改。

如果使用传统的LRU算法，MySQL中可能出现预读失效和Buffer Pool污染的问题。

  • 预读失效：MySQL 在加载数据页时，会提前把它相邻的数据页一并加载进来，目的是为了减少磁盘 IO。但是可能这些被提前加载进来的数据页，并没有被访问，相当于这个预读是白做了，这个就是预读失效。
    • 解决预读失效（提前淘汰预读页），可以将LRU划分为young区域和old区域。用户直接读取的页面，直接移动到young区域的头部；预读到的页放到old区域的头部中，当真正被访问到时，才放入young区域的头部。这样才不会让我们的预读白做，即使预读页没被访问，也会很快被删除。
  • Buffer Pool污染：当某一个 SQL 语句扫描了大量的数据时，在 Buffer Pool 空间比较有限的情况下，可能会将 Buffer Pool 里的所有页都替换出去，导致大量热数据被淘汰了，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 IO，MySQL 性能就会急剧下降，这个过程被称为 Buffer Pool 污染。
    • 解决Buffer Pool污染。
      • 设置LRU链表的插入点，也就是设置old区域所占的百分比。新扫描到的数据插入到old区域，防止替换掉young区域的热数据。innodb_old_blocks_pct参数控制该百分比，默认值为 37，即young / old = 63/37。
      • 并且提高进入到 young 区域的门槛，增加一个old区域停留的时间判断，只有满足被访问 + 大于该停留时间，才会将数据页放在young区域头部。这个间隔时间是由 innodb_old_blocks_time 控制的，默认是 1000 ms。
  • 另外，MySQL 针对 young 区域其实做了一个优化，为了防止 young 区域节点频繁移动到头部。young 区域前面 1/4 被访问不会移动到链表头部，只有后面的 3/4被访问了才会。

https://blog.csdn.net/weixin_40869022/article/details/103020194

如果使用传统的LRU算法，Redis不想维护一个较大的链表，占用内存空间。

Redis实现的是近似LRU算法，它的实现方式是在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间。当 Redis 进行内存淘汰时，会使用随机采样的方式来淘汰数据，它是随机取 5 个值（此值可配置），然后淘汰最久没有使用的那个。

Redis的LRU算法存在缓存污染的问题，比如应用一次读取了大量的数据，而这些数据只会被读取这一次，那么这些数据会留存在 Redis 缓存中很长一段时间，造成缓存污染。所以Redis4.0之后新增了lfu淘汰策略。LFU(Least Frequently Used，最近最不常用算法)

链表

单链表不需要连续的存储空间，所以在删除和增加结点时不需要像顺序表一样需要移动全部的元素，提高运行效率。

单链表

单链表示意图

add/addByOrder
  • （add）设置辅助变量
  • 循环遍历链表，找到链表的最后一个结点。
  • temp.next=node
  • （addByOrder）设置辅助变量
  • 循环遍历链表，找到插入点的前一个位置。（考虑：如果序号相同，无法插入。）
  • node.next=temp.next 和 temp.next=node（注意顺序，要让新增节点先指向。）
delete/update
  • (delete)设置辅助变量。
  • 遍历链表，找到需要删除的结点的前一个结点。
  • temp.next=temp.next.next
  • (update)设置辅助变量。
  • 遍历链表，找到需要更改的结点。
  • temp.date=node.date

代码实现

class SingleList{
    Node1 head=new Node1(0,0);
    //增加链表到最后
    public void add(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
    }
    //按序号增加链表
    public void addByOrder(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no>=node.no){
                break;
            }
            temp=temp.next;
        }
        node.next=temp.next;
        temp.next=node;
    }
    //删除指定结点
    public void delNode(Node1 node){
        Node1 temp=head;
        while(true){
            if(temp.next==node){
                break;
            }
            temp=temp.next;
        }
        temp.next=temp.next.next;
    }
    //修改单链表的结点
    public void update(Node1 node,int update){
        Node1 temp=head;
        while(true){
            if(temp.no==node.no){
                break;
            }
            temp=temp.next;
        }
        temp.date=update;
    }
    //打印单链表
    public void list(){
        Node1 temp=head.next;
        if(head.next==null){
            System.out.println("Empty!");
        }
        while(temp!=null){
            System.out.println(temp.toString());
            temp=temp.next;
        }
    }
}
//创建一个类，每个类的对象就是一个结点。
class Node1{
    public int date;
    public int no;
    public Node1 next;

    public Node1(int date, int no) {
        this.date = date;
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node1{" +
                "date=" + date +
                ", no=" + no +
                '}';
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

双向链表

对于单向链表而言，只有一个查找方向，并且不能自我删除。
所以引入双向链表，与单向链表的主要不同点只是在于pre指针的引入和删除操作
next：指向下一个结点。
pre：指向前一个结点。

  • 操作思路：
  1. 遍历和修改：和单链表一样，遍历可以向前也可以向后查找。
  2. 添加(添加到最后)：先找到最后的节点。
    temp.next=newNode;
    newNode.pre=temp;
    2.1 添加（按序号添加）：除了单链表的两个基础指向代码，还需要新增以下代码：
    node.pre=temp;
    node.next.pre=node;
  3. 删除：直接找到待删除节点(temp)。
    (1)temp.pre.next=temp.next;
    //删除节点的前一个节点【指向】 删除节点的下一个节点。
    (2)注意！！ 如果要删除的结点不是最后一个结点，那么执行（3）
    (3)temp.next.pre=temp.pre;
    //删除节点的后一个节点向前【指向】删除节点的前一个节点。

代码实现

class DoubleLinkedlistDemo{
  private Nodes head=new Nodes(0,0);
   //默认加到链表最后。
   public void add(Nodes node){
       Nodes temp=head;
       while(true){
           if(temp.next==null){
               break;
           }
           temp=temp.next;
       }
       temp.next=node;
       node.pre=temp;
   }
   //按照no的顺序增加链表。
   public void addByOrder(Nodes node){
       Nodes temp=head;
       boolean flag=false;
       while(true){
           if(temp.next==null){
               flag=true;
               break;
           }
           if(temp.next.no>=node.no){
               break;
           }
           temp=temp.next;
       }
       if(flag){
           add(node);
           return;
       }
       //让添加进来的节点先指向。
       //单链表指向。
       node.next=temp.next;
       temp.next=node;
       //双向链表新增指向。
       node.pre=temp;
       node.next.pre=node;
   }
   //删除节点。（找到当前要删除的节点即可）
    public void del(Nodes node){
       Nodes temp=head;
       if(head.next==null){
           System.out.println("Empty!");
           return ;
       }
       while(true){
           if(temp== node){
               break;
           }
           temp=temp.next;
       }
       //绕过当前结点，指向下一个结点。
       temp.pre.next=temp.next;
       if(temp.next!=null){
           temp.next.pre=temp.pre;
       }
    }
    //打印链表,同单链表一样
    public void list(){
       Nodes temp=head;
       while(true) {
           temp=temp.next;
           System.out.println(temp);
           if(temp.next==null){
               break;
           }
       }
    }
}

class Nodes{
    public int no;
    public int date;
    public Nodes next;
    public Nodes pre;
    public Nodes(int no,int date){
        this.no=no;
        this.date=date;
    }
    @Override
    public String toString() {
        return "Nodes{" +
                "no=" + no +
                ", date=" + date +
                '}';
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

环形链表（Joseph Ring）

  • 思路分析：
  1. 创建first指针，永远指向第一个元素，并且自成环状。
  2. 建立辅助指针cur，通过移动辅助指针来添加节点。
    2.1 具体步骤为：辅助指针指向下一个节点、后移、再指向first。

环形链表代码实现

class CircleLinkedListDemo {
    //创建first节点，永远指向第一个元素，保持不动。
    private Node first = null;
    //创建环形链表。
    public void buildCLL(int nums) {
        if (nums < 1) {
            System.out.println("无法加入小于一个的链表");
            return;
        }
        //先创建第一个结点。
        Node node1 = new Node(1);
        //让first指向第一个节点
        first = node1;
        //first指向自己，形成环状。
        first.next = first;
        //建立辅助指针，通过移动辅助指针来添加节点。
        Node cur = null;
        cur = first;
        for (int i = 2; i <= nums; i++) {
            Node node = new Node(i);
            //辅助指针指向下一个节点。
            cur.next = node;
            //辅助指针后移。
            cur = cur.next;
            //辅助指针指向第一个节点。
            cur.next = first;
             }
        }
    //用来打印环形链表
    public void list1(){
        Node temp=first;
        while(true){
            //如果到了环形链表的最后，退出循环。
            if(temp.next==first){
                break;
            }
            System.out.println(temp.toString());
            temp=temp.next;
        }
        System.out.println(temp.toString());
    }
}
class Node{
    // 这里也可以设置为私有属性，重写方法getNext和setNext即可。
    public int no;
    public Node next;
    public Node(int no){
        this.no=no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
解决Joseph问题代码实现
  • 思路分析：
  1. 创建两个结点，first（遍历环形链表）和helper（帮助出圈）。
  2. first指向startNo的结点，helper则指向first的前一个结点。
  3. 找到需要出圈的结点后打印，并将结点出圈：
    first=first.next; helper.next=first;
    /**
     *
     * @param nums 表示环形链表节点个数。
     * @param startNo 表示从第几个节点开始数。
     * @param countNo 表示数了几下。 每数countNo下，就删除当前结点。
     */
    public void Joseph(int nums,int startNo,int countNo){
        if(startNo<1|| startNo>nums || nums<1){
            System.out.println("数据输入有误");
            return ;
        }
        // 创建一个辅助节点，初始化为指向first的前一个结点。
        Node helper=first;
        while(true){
            if(helper.next==first){
                break;
            }
            helper=helper.next;
        }
        // 在开始之前，先将first指向开始的节点。
        for(int i=0;i<startNo-1;i++){
            first=first.next;
            helper=helper.next;
        }
        // 出圈，是一个循环过程，使用while循环。
        while(true){
            // 开始寻找出圈节点，将first指向要删除的节点，helper指向删除节点的前一个节点。
            for(int j=0;j<countNo-1;j++){
                first=first.next;
                helper=helper.next;
            }
            // 当圈中只剩一个元素时，退出循环。
            if(helper==first){
                break;
            }
            System.out.println(first.toString());
            // 让first后移
            first=first.next;
            // helper指向first，就跳过了一个结点（出圈）。
            //注意：helper并没有后移。
            helper.next=first;
        }
        System.out.printf("最后一个是：%s",first.toString());
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

栈

特点：先入后出，变化的一端在栈顶，栈底固定。
入栈（push）：栈顶上移；
出栈（pop）：栈顶下移。

Java中也提供了关于栈的类，便于直接调用。

  • 数组模拟栈的思路分析
    1. 定义top表示栈顶指针，初始为-1；
    2. 入栈：top++；
      stack[top]=data;
    3. 出栈：拿到数据；top--；
代码实现
/**
 * max 表示栈的最大容量
 * top 栈顶指针
 * stack[] 用数组模拟栈
 */
 class stack{
    private int max;
    private int top=-1;
    private int stack[];
    public stack(int max){
        this.max=max;
        stack=new int[max];
    }
    public boolean isFull(){
        return top==max-1;
    }
    public boolean isEmpty(){
        return top==-1;
    }
    //入栈
    public void push(int date){
        if(isFull()){
            System.out.println("False");
            return;
        }
        top++;
        stack[top]=date;
    }
    //出栈
     public int pop(){
        if(isEmpty()){
            throw new RuntimeException("Empty");
        }
        int value= stack[top];
        top--;
        return value;
     }
     //遍历
     public void list(){
        for(int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d",i, stack[i]);
        }
     }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

栈的实际应用

栈的应用：子程序调用；递归调用；表达式转换（中缀转后缀表达式）；二叉树；深度优先。
关于更多的栈的实际应用，就先不在这里展开了，会写另外一篇文章展开来讲。

最重要的来啦~~~
⭐码字不易，求个关注⭐
⭐点个收藏不迷路哦~⭐

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/642279
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号