• 线性数据—栈、队列、链表

    一、栈 Stack（存取O(1)）

    先进后出，进去123，出来321。
    基于数组：最后一位为栈尾，用于取操作。
    基于链表：第一位为栈尾，用于取操作。

    1.1、数组栈 

    1. /**
    2.  * 基于数组实现的顺序栈； items[0]：表头/栈底；  items[size-1]：表尾/栈顶；
    3.  */
    4. public class MyArrayStack {
    5.     // 存储元素的 数组
    6.     private String items[];
    7.     // 栈实际大小
    8.     private int size =0;
    9.     // 栈的容量
    10.     private int capacity = 0;
    11.  
    12.     public MyArrayStack(int capacity) {
    13.         this.size = 0;
    14.         this.capacity = capacity;
    15.         this.items = new String[capacity];
    16.     }
    17.  
    18.     /**
    19.      * 入栈
    20.      */
    21.     public boolean push(String item) {
    22.         if(size >= capacity){
    23.             throw new IndexOutOfBoundsException("MyArrayStack 栈的内存满了");
    24.         }
    25.         items[size] = item;
    26.         size++;
    27.         return true;
    28.     }
    29.  
    30.     /**
    31.      * 出栈
    32.      */
    33.     public String pop() {
    34.         if(size<=0){
    35.             throw new IndexOutOfBoundsException("MyArrayStack 栈的内存空了");
    36.         }
    37.         String item = items[size-1];
    38.         items[size-1] = null;
    39.         size--;
    40.         return item;
    41.     }
    42. }

    1.2、链表栈 

    1. /**
    2.  * 基于链表实现的链式栈  top: 表尾/栈顶；
    3.  */
    4. public class MyLinkedStack {
    5.  
    6.     // 表尾/栈顶；
    7.     private Node top = null;
    8.  
    9.     /**
    10.      * 入栈
    11.      */
    12.     public void push(String value) {
    13.         Node node = new Node(value,null);
    14.         if(top != null){
    15.             node.nextNode = top;
    16.         }
    17.         top = node;
    18.     }
    19.  
    20.     /**
    21.      * 出栈
    22.      */
    23.     public String pop() {
    24.         if(top==null){
    25.             throw new IndexOutOfBoundsException("MyLinkedStack 栈的内存空了");
    26.         }
    27.         String retValue = top.getValue();
    28.         top = top.nextNode;
    29.         return retValue;
    30.     }
    31.  
    32.     /**
    33.      * 节点
    34.      */
    35.     private static class Node{
    36.         // 存储数据
    37.         private String value;
    38.         // 下个节点
    39.         private Node nextNode;
    40.         public Node(String value, Node nextNode) {
    41.             this.value = value;
    42.             this.nextNode = nextNode;
    43.         }
    44.         public String getValue() {
    45.             return value;
    46.         }
    47.     }
    48. }

    二、队列 Queue （存取O(1)）

    先进先出（FIFO）的有序列表 

    2.1、数组单向队列 （存取O(1)）

    1. /**
    2.  * 基于数组实现的顺序队列
    3.  */
    4. public class MyArrayQueue {
    5.  
    6.     private String [] items;
    7.  
    8.     // 容量
    9.     private int capacity = 0;
    10.  
    11.     // 队头下标
    12.     private int head = 0;
    13.  
    14.     // 队尾下标
    15.     private int tail = 0;
    16.  
    17.     public MyArrayQueue(int capacity) {
    18.         this.items = new String [capacity];
    19.         this.capacity = capacity;
    20.     }
    21.  
    22.     /**
    23.      * 入队
    24.      */
    25.     public boolean enqueue(String item) {
    26.         if(capacity == tail){
    27.             throw new IndexOutOfBoundsException("MyArrayQueue 容量满了");
    28.         }
    29.         items[tail] = item;
    30.         tail++;
    31.         return true;
    32.     }
    33.  
    34.     /**
    35.      * 出队
    36.      */
    37.     public String dequeue() {
    38.         if(head==tail){
    39.             throw new IndexOutOfBoundsException("MyArrayQueue 容量空了");
    40.         }
    41.         String retValue = items[head];
    42.         head++;
    43.         return retValue;
    44.     }
    45. }

    2.2、链表单向队列 

    1. /**
    2.  * 基于链表实现的链式队列
    3.  */
    4. public class MyLinkedListQueue {
    5.     // 队头
    6.     private Node head = null;
    7.     // 队尾
    8.     private Node tail = null;
    9.  
    10.     /**
    11.      * 入队
    12.      */
    13.     public void enqueue(String value) {
    14.         Node node = new Node(value,null);
    15.         if(tail==null){
    16.             head = node;
    17.             tail = node;
    18.         }else {
    19.             tail.next=node;
    20.             tail=node;
    21.         }
    22.     }
    23.  
    24.     /**
    25.      * 出队
    26.      */
    27.     public String dequeue() {
    28.         if(head==null){
    29.             throw new IndexOutOfBoundsException("MyLinkedListQueue 队列空了");
    30.         }
    31.         String retValue = head.getValue();
    32.         head = head.next;
    33.         if (head == null) {
    34.             tail = null;
    35.         }
    36.         return retValue;
    37.     }
    38.  
    39.     private static class Node{
    40.         private String value;
    41.         private Node next;
    42.         public Node(String value, Node next) {
    43.             this.value = value;
    44.             this.next = next;
    45.         }
    46.         public String getValue() {
    47.             return value;
    48.         }
    49.     }
    50. }

    三、链表 LinkedList 

    3.1、单向链表 

    1. /**
    2.  * 单向普通链表
    3.  */
    4. public class MyLinkedList {
    5.     // 链表大小
    6.     private int size;
    7.     // 表头
    8.     private Node head;
    9.  
    10.     /**
    11.      * 插入
    12.      */
    13.     public void insert(int index, String value) {
    14.         if(index<0){
    15.             throw new IndexOutOfBoundsException("MyLinkedList 下标越界了");
    16.         } else {
    17.             if(head==null){
    18.                 head = new Node(value,null);
    19.             }else {
    20.                 if(index>=size){
    21.                     index = size-1;
    22.                 }
    23.                 Node prev = head;
    24.                 for(int i=0;i
    25.                     prev = prev.next;
    26.                 }
    27.                 Node node = new Node(value,prev);
    28.                 prev.next =node;
    29.             }
    30.             size++;
    31.         }
    32.     }
    33.  
    34.     /**
    35.      * 获取
    36.      */
    37.     public String get(int index){
    38.         if(size<=0){
    39.             throw new IllegalArgumentException("MyLinkedList 空链表");
    40.         }
    41.         if(index<0 || index>=size) {
    42.             throw new IllegalArgumentException("MyLinkedList 下标越界了");
    43.         }
    44.         Node prev = head;
    45.         for (int i=0;i
    46.             prev = prev.next;
    47.         }
    48.         return prev.getValue();
    49.     }
    50.  
    51.     private class Node{
    52.         private String value;
    53.         private Node next;
    54.         public Node(String value, Node next) {
    55.             this.value = value;
    56.             this.next = next;
    57.         }
    58.         public String getValue() {
    59.             return value;
    60.         }
    61.     }
    62. }

    3.2、双向链表 

    1.  
    2. public class MyDoubleLinkedList {
    3.     // 链表大小
    4.     private int size;
    5.     // 表头
    6.     private Node head;
    7.     // 表尾
    8.     private Node tail;
    9.  
    10.     /**
    11.      * 插入
    12.      */
    13.     public void insert(int index,String data) {
    14.         if(index < 0) {
    15.             throw new IndexOutOfBoundsException("MyDoubleLinkedList  insert 下标越界");
    16.         }
    17.         Node node = new Node(data,null,null);
    18.         if(index == 0) {
    19.             head.next = node.next;
    20.             head= node;
    21.             return;
    22.         }
    23.         if(index >= size) {
    24.             tail.prev = node.prev;
    25.             tail= node;
    26.             return;
    27.         }
    28.         Node cur = this.head;
    29.         while(index != 0) {
    30.             cur = cur.next;
    31.             index--;
    32.         }
    33.         node.next = cur;
    34.         cur.prev.next = node;
    35.         node.prev = cur.prev;
    36.         cur.prev = node;
    37.     }
    38.  
    39.     public String get(int index){
    40.         if(index<0||index>size){
    41.             throw new IndexOutOfBoundsException("MyDoubleLinkedList get 下标越界了");
    42.         }
    43.         if(index<=(size/2)){
    44.             Node cur = head;
    45.             for(int i = 0;i1;i++){
    46.                cur = head.next;
    47.             }
    48.             return cur.getValue();
    49.         }else {
    50.             index = size-index;
    51.             Node cur = tail;
    52.             for (int i=size;i>index;i--){
    53.                 cur = cur.prev;
    54.             }
    55.             return cur.getValue();
    56.         }
    57.     }
    58.  
    59.  
    60.     private class Node{
    61.         public String value;
    62.         public Node prev;
    63.         public Node next;
    64.         public Node(String value, Node prev, Node next) {
    65.             this.value = value;
    66.             this.prev = prev;
    67.             this.next = next;
    68.         }
    69.  
    70.         public String getValue() {
    71.             return value;
    72.         }
    73.     }
    74. }

    3.3、跳表 

    1.跳表由很多层结构组成，level是通过一定的概率随机产生的；
    2.每一层都是一个有序的链表，默认是升序 ；
    3.最底层(Level 1)的链表包含所有元素；
    4.如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
    5.每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

    1.  
    2. import java.util.Random;
    3.  
    4. public class SkipList {
    5.  
    6.     // 跳表中存储的是正整数，并且存储的数据是不重复的
    7.     private static final int MAX_LEVEL = 16;
    8.     // 结点的个数
    9.     private int levelCount = 1;
    10.     // 索引的层级数
    11.     private final Node head = new Node();
    12.     // 头结点
    13.     private final Random random = new Random();
    14.  
    15.     // 查找操作
    16.     public Node find(int value) {
    17.         Node p = head;
    18.         for (int i = levelCount - 1; i >= 0; --i) {
    19.             while (p.next[i] != null && p.next[i].data < value) {
    20.                 p = p.next[i];
    21.             }
    22.         }
    23.         if (p.next[0] != null && p.next[0].data == value) {
    24.             return p.next[0];    // 找到，则返回原始链表中的结点
    25.         } else {
    26.             return null;
    27.         }
    28.     }
    29.  
    30.     // 插入操作
    31.     public void insert(int value) {
    32.         int level = randomLevel();
    33.         Node newNode = new Node();
    34.         newNode.data = value;
    35.         newNode.maxLevel = level;   // 通过随机函数改变索引层的结点布置
    36.         Node[] update = new Node[level];
    37.         for (int i = 0; i < level; ++i) {
    38.             update[i] = head;
    39.         }
    40.         Node p = head;
    41.         for (int i = level - 1; i >= 0; --i) {
    42.             while (p.next[i] != null && p.next[i].data < value) {
    43.                 p = p.next[i];
    44.             }
    45.             update[i] = p;
    46.         }
    47.         for (int i = 0; i < level; ++i) {
    48.             newNode.next[i] = update[i].next[i];
    49.             update[i].next[i] = newNode;
    50.         }
    51.         if (levelCount < level) {
    52.             levelCount = level;
    53.         }
    54.     }
    55.  
    56.     // 删除操作
    57.     public void delete(int value) {
    58.         Node[] update = new Node[levelCount];
    59.         Node p = head;
    60.         for (int i = levelCount - 1; i >= 0; --i) {
    61.             while (p.next[i] != null && p.next[i].data < value) {
    62.                 p = p.next[i];
    63.             }
    64.             update[i] = p;
    65.         }
    66.         if (p.next[0] != null && p.next[0].data == value) {
    67.             for (int i = levelCount - 1; i >= 0; --i) {
    68.                 if (update[i].next[i] != null && update[i].next[i].data == value) {
    69.                     update[i].next[i] = update[i].next[i].next[i];
    70.                 }
    71.             }
    72.         }
    73.     }
    74.  
    75.     // 随机函数
    76.     private int randomLevel() {
    77.         int level = 1;
    78.         for (int i = 1; i < MAX_LEVEL; ++i) {
    79.             if (random.nextInt() % 2 == 1) {
    80.                 level++;
    81.             }
    82.         }
    83.         return level;
    84.     }
    85.  
    86.     // Node内部类
    87.     public static class Node {
    88.         private int data = -1;
    89.         private final Node[] next = new Node[MAX_LEVEL];
    90.         private int maxLevel = 0;
    91.         // 重写toString方法
    92.         @Override
    93.         public String toString() {
    94.             return "{data:" +
    95.                     data +
    96.                     "; levels: " +
    97.                     maxLevel +
    98.                     " }";
    99.         }
    100.     }
    101.  
    102.     // 显示跳表中的结点
    103.     public void display() {
    104.         Node p = head;
    105.         while (p.next[0] != null) {
    106.             System.out.println(p.next[0] + " ");
    107.             p = p.next[0];
    108.         }
    109.         System.out.println();
    110.     }
    111. }

  • 相关阅读:
    使用vite搭建vue3
    xxis not in the sudoers file. This incident will be reported.
    【国科大——矩阵分析与应用】使用高斯消元法，测试二元一次方程系数产生的误差
    部署Docker玩转Docker
    一文读懂Layer 2：Layer 2指基于底层区块链...
    Nginx入门到搭建
    Python脚本打包
    设计模式之策略模式
    VS2022ide下使用C++实现简谐振动，C语言程序设计简谐运动的模拟,C语言课程设计简谐振动实验的模拟。
    Tungsten Fabric数据量过大问题处理初探
  • 原文地址：https://blog.csdn.net/weixin_42679286/article/details/133296952