• 队列--环形数组实现

     具体代码可参考：https://github.com/1693905917/DataStructure.git

    好处

    1. 对比普通数组，起点和终点更为自由，不用考虑数据移动

    2. “环”意味着不会存在【越界】问题

    3. 数组性能更佳

    4. 环形数组比较适合实现有界队列、RingBuffer 等

     

    下标计算

    例如，数组长度是 5，当前位置是 3 ，向前走 2 步，此时下标为 (3 + 2)\%5 = 0

    • cur 当前指针位置

    • step 前进步数

    • length 数组长度

    注意：

    • 如果 step = 1，也就是一次走一步，可以在 >= length 时重置为 0 即可

    判断空

    判断该数组是否为空：头指针==尾指针

    判断满

    判断该数组是否满：（尾指针的索引+1）%数组长度==头指针的索引

    满之后的策略可以根据业务需求决定

    • 例如我们要实现的环形队列，满之后就拒绝入队

    代码：

    1. //仅用head,tail判断空满，head,tail即为索引值
    2. public class ArrayQueue implements Queue, Iterable{
    3.     
    4.     private int head = 0;
    5.     private int tail = 0;
    6.     private final E[] array;
    7.     private final int length;
    8.  
    9.     //SuppressWarnings:抑制警告
    10.     @SuppressWarnings("all")
    11.     public ArrayQueue(int capacity) {
    12.         //你设定的容量+1：在你添加满容量时，需要有多出一个的位置给尾指针
    13.         length = capacity + 1;
    14.         array = (E[]) new Object[length];
    15.     }
    16.  
    17.     @Override
    18.     public boolean offer(E value) {
    19.         if (isFull()) {
    20.             return false;
    21.         }
    22.         array[tail] = value;
    23.         //当加到数组最大索引位置时，应该让tail=数组初始索引位置0
    24.         tail = (tail + 1) % length;
    25.         return true;
    26.     }
    27.  
    28.     @Override
    29.     public E poll() {
    30.         if (isEmpty()) {
    31.             return null;
    32.         }
    33.         E value = array[head];
    34.         //当加到数组最大索引位置时，应该让tail=数组初始索引位置0
    35.         head = (head + 1) % length;
    36.         return value;
    37.     }
    38.  
    39.     @Override
    40.     public E peek() {
    41.         if (isEmpty()) {
    42.             return null;
    43.         }
    44.         return array[head];
    45.     }
    46.  
    47.     @Override
    48.     public boolean isEmpty() {
    49.         return tail == head;
    50.     }
    51.  
    52.     @Override
    53.     public boolean isFull() {
    54.         return (tail + 1) % length == head;
    55.     }
    56.  
    57.     @Override
    58.     public Iterator iterator() {
    59.         return new Iterator() {
    60.             int p = head;
    61.             @Override
    62.             public boolean hasNext() {
    63.                 return p != tail;
    64.             }
    65.  
    66.             @Override
    67.             public E next() {
    68.                 E value = array[p];
    69.                 p = (p + 1) % array.length;
    70.                 return value;
    71.             }
    72.         };
    73.     }
    74. }

    判断空、满方法2

    //修改在数组满的时候，不用给尾指针留个位置

    引入 size

    1. public class ArrayQueue2 implements Queue, Iterable {
    2.  
    3.     private int head = 0;
    4.     private int tail = 0;
    5.     private final E[] array;
    6.     private final int capacity;
    7.     private int size = 0;
    8.  
    9.     @SuppressWarnings("all")
    10.     public ArrayQueue2(int capacity) {
    11.         this.capacity = capacity;
    12.         array = (E[]) new Object[capacity];
    13.     }
    14.  
    15.     @Override
    16.     public boolean offer(E value) {
    17.         if (isFull()) {
    18.             return false;
    19.         }
    20.         array[tail] = value;
    21.         tail = (tail + 1) % capacity;
    22.         size++;
    23.         return true;
    24.     }
    25.  
    26.     @Override
    27.     public E poll() {
    28.         if (isEmpty()) {
    29.             return null;
    30.         }
    31.         E value = array[head];
    32.         head = (head + 1) % capacity;
    33.         size--;
    34.         return value;
    35.     }
    36.  
    37.     @Override
    38.     public E peek() {
    39.         if (isEmpty()) {
    40.             return null;
    41.         }
    42.         return array[head];
    43.     }
    44.  
    45.     @Override
    46.     public boolean isEmpty() {
    47.         return size == 0;
    48.     }
    49.  
    50.     @Override
    51.     public boolean isFull() {
    52.         return size == capacity;
    53.     }
    54.  
    55.     @Override
    56.     public Iterator iterator() {
    57.         return new Iterator() {
    58.             int p = head;
    59.  
    60.             @Override
    61.             public boolean hasNext() {
    62.                 return p != tail;
    63.             }
    64.  
    65.             @Override
    66.             public E next() {
    67.                 E value = array[p];
    68.                 p = (p + 1) % capacity;
    69.                 return value;
    70.             }
    71.         };
    72.     }
    73. }

    判断空、满方法3

    • head 和 tail 不断递增，用到索引时，再用它们进行计算，两个问题

      • 如何保证 head 和 tail 自增超过正整数最大值的正确性

      • 如何让取模运算性能更高

    • 答案：让 capacity 为 2 的幂

    1. public class ArrayQueue3 implements Queue, Iterable {
    2.  
    3.     private int head = 0;
    4.     private int tail = 0;
    5.     private final E[] array;
    6.     private final int capacity;
    7.  
    8.     @SuppressWarnings("all")
    9.     public ArrayQueue3(int capacity) {
    10.         if ((capacity & capacity - 1) != 0) {
    11.             throw new IllegalArgumentException("capacity 必须为 2 的幂");
    12.         }
    13.         this.capacity = capacity;
    14.         array = (E[]) new Object[this.capacity];
    15.     }
    16.  
    17.     @Override
    18.     public boolean offer(E value) {
    19.         if (isFull()) {
    20.             return false;
    21.         }
    22.         array[tail & capacity - 1] = value;
    23.         tail++;
    24.         return true;
    25.     }
    26.  
    27.     @Override
    28.     public E poll() {
    29.         if (isEmpty()) {
    30.             return null;
    31.         }
    32.         E value = array[head & capacity - 1];
    33.         head++;
    34.         return value;
    35.     }
    36.  
    37.     @Override
    38.     public E peek() {
    39.         if (isEmpty()) {
    40.             return null;
    41.         }
    42.         return array[head & capacity - 1];
    43.     }
    44.  
    45.     @Override
    46.     public boolean isEmpty() {
    47.         return tail - head == 0;
    48.     }
    49.  
    50.     @Override
    51.     public boolean isFull() {
    52.         return tail - head == capacity;
    53.     }
    54.  
    55.     @Override
    56.     public Iterator iterator() {
    57.         return new Iterator() {
    58.             int p = head;
    59.  
    60.             @Override
    61.             public boolean hasNext() {
    62.                 return p != tail;
    63.             }
    64.  
    65.             @Override
    66.             public E next() {
    67.                 E value = array[p & capacity - 1];
    68.                 
    69.                 p++;
    70.                 return value;
    71.             }
    72.         };
    73.     }
    74. }

    第三个方法暴露了一个问题:因为我们的head、tail都是整型int类型，正整数的最大值int：2147483647

    测试：

    如果是使用C语言就会解决：unsigned int 0 ~2^32-1

    对于JAVA语言，它有种方法：可以将int整型超出的时候，及时将int转换为Long类型：

    Integer.toUnsignedLong(tail)

    优化以后的代码：

    1. /**
    2.  * @BelongsProject: arithmetic
    3.  * @BelongsPackage: com.hzp.algorithm.queue
    4.  * @Author: ASUS
    5.  * @CreateTime: 2023-09-25  11:26
    6.  * @Description: TODO  环形数组实现3.0
    7.  * @Version: 1.0
    8.  */
    9. //修改在数组满的时候，不用给尾指针留个位置
    10. public class ArrayQueue3 implements Queue, Iterable{
    11.  
    12.     private int head = 0;
    13.     private int tail = 0;
    14.     private  E[] array;
    15.  
    16.     //SuppressWarnings:抑制警告
    17.     @SuppressWarnings("all")
    18.     public ArrayQueue3(int capacity) {
    19.         array = (E[]) new Object[ capacity ];//这个时候就不需要给尾指针留个位置
    20.     }
    21.  
    22.     @Override
    23.     public boolean offer(E value) {
    24.         if (isFull()) {
    25.             return false;
    26.         }
    27.         //进行(int):数组中只能存储Int类型，不能是long类型所以要转换
    28.         array[(int) (Integer.toUnsignedLong(tail)% array.length)] = value;
    29.         tail++;
    30.         return true;
    31.     }
    32.  
    33.     @Override
    34.     public E poll() {
    35.         if (isEmpty()) {
    36.             return null;
    37.         }
    38.         E value = array[(int) (Integer.toUnsignedLong(head)% array.length)];
    39.         head++;
    40.         return value;
    41.     }
    42.  
    43.     @Override
    44.     public E peek() {
    45.         if (isEmpty()) {
    46.             return null;
    47.         }
    48.         return array[(int) (Integer.toUnsignedLong(head)% array.length)];
    49.     }
    50.  
    51.     @Override
    52.     public boolean isEmpty() {
    53.         return head==tail;
    54.     }
    55.  
    56.     @Override
    57.     public boolean isFull() {
    58.         return tail-head==array.length;
    59.     }
    60.  
    61.     @Override
    62.     public Iterator iterator() {
    63.         return new Iterator() {
    64.             int p = head;
    65.             @Override
    66.             public boolean hasNext() {
    67.                 return p!=tail;
    68.             }
    69.  
    70.             @Override
    71.             public E next() {
    72.                 E value = array[(int) (Integer.toUnsignedLong(p)%array.length)];
    73.                 p++;
    74.                 return value;
    75.             }
    76.         };
    77.     }
    78. }

    判断空、满方法4

    我们以二进制的角度来看求模运算的规律：

    //求模运算：
    //          被除数是什么都无所谓
    //        如果除数是2的n次方
    //        那么被除数的后n位即为余数（馍）
    //        求被除数的后n位方法：与2^n-1按位与

    演示：

    总结规律：当除数是2的n次方，则余数是被除数的二进制后n位，被除数剩余的二进制就是商的二进制

    对于我们求模运算而言，我们只需要余数即可：

    所以结论：求余数：被除数与2^n-1按位与即可得到余数：

    1. //求模运算：
    2. //        如果除数是2的n次方
    3. //        那么被除数的后n位即为余数（馍）
    4. //        求被除数的后n位方法：与2^n-1按位与
    5. public class ArrayQueue3_1 implements Queue, Iterable{
    6.  
    7.     private int head = 0;
    8.     private int tail = 0;
    9.     private  E[] array;
    10.  
    11.     //SuppressWarnings:抑制警告
    12.     @SuppressWarnings("all")
    13.     //这个方法的条件就是 capacity的取值必须是2的n次方
    14.     public ArrayQueue3_1(int capacity) {
    15.         array = (E[]) new Object[ capacity ];//这个时候就不需要给尾指针留个位置
    16.     }
    17.  
    18.     @Override
    19.     public boolean offer(E value) {
    20.         if (isFull()) {
    21.             return false;
    22.         }
    23.         //进行(int):数组中只能存储Int类型，不能是long类型所以要转换
    24.         //array[(int) (Integer.toUnsignedLong(tail)% array.length)] = value;
    25.         //以下方法比以上方法的优点：1.&的运算更加优化   2.这也防止了int类型超出最大值的情况
    26.         array[tail& (array.length-1)]=value;
    27.         tail++;
    28.         return true;
    29.     }
    30.  
    31.     @Override
    32.     public E poll() {
    33.         if (isEmpty()) {
    34.             return null;
    35.         }
    36.         //E value = array[(int) (Integer.toUnsignedLong(head)% array.length)];
    37.         E value = array[head& (array.length-1)];
    38.         head++;
    39.         return value;
    40.     }
    41.  
    42.     @Override
    43.     public E peek() {
    44.         if (isEmpty()) {
    45.             return null;
    46.         }
    47.         //return array[(int) (Integer.toUnsignedLong(head)% array.length)];
    48.         return array[head& (array.length-1)];
    49.     }
    50.  
    51.     @Override
    52.     public boolean isEmpty() {
    53.         return head==tail;
    54.     }
    55.  
    56.     @Override
    57.     public boolean isFull() {
    58.         return tail-head==array.length;
    59.     }
    60.  
    61.     @Override
    62.     public Iterator iterator() {
    63.         return new Iterator() {
    64.             int p = head;
    65.             @Override
    66.             public boolean hasNext() {
    67.                 return p!=tail;
    68.             }
    69.  
    70.             @Override
    71.             public E next() {
    72.                 //E value = array[(int) (Integer.toUnsignedLong(p)%array.length)];
    73.                 E value = array[p& (array.length-1)];
    74.                 p++;
    75.                 return value;
    76.             }
    77.         };
    78.     }
    79. }

    但是注意：这个方法的条件就是 capacity的取值必须是2的n次方！！！！

    因此，这个方法是有缺陷的。

    判断空、满方法5

    这个方法的条件就是 capacity的取值没有限制

    就是对于第四种方法的优化：

    第一种优化：就是对于“当输入的数不是2的幂则跑异常”：

    1. //1.抛异常:当输入的数不是2的幂则跑异常
    2. if(((capacity&capacity-1)!=0)){
    3.     throw new IllegalArgumentException("capactiy 必须是2的幂");
    4. }

    对于“capacity&capacity-1”演示：

    第二种优化：将输入的数不是2的幂改成2^n

    这是利用第一种结论来写：

    1. /*
    2. 当我输入的是数是30
    3. c=30;
    4. 2^4 == 16
    5. 2^4.？ == 30
    6. 2^5 == 32
    8. 我们要找到的是这个数最近并且大于这个数的2^n：
    9. 对于幂的获取：log2(30)==4.?  --->(int)log2(30)==4 -->(int)log2(30)+1 ==5
    11. int c=30;
    12.         int n= (int)(Math.log10(c-1)/Math.log10(2))+1;
    13.         System.out.println(n);
    14.         System.out.println(1<
    16. 验证1<
    17.         1           2^0
    18.         10          2^1
    19.         100         2^2
    20.         1000        2^3
    21.  */

    利用第二种结论：求离c最近，比c大的2^n(方法2)

    1. c=30;
    2. c -= 1;
    3. c |= c >> 1;
    4. c |= c >> 2;
    5. c |= c >> 4;
    6. c |= c >> 8;
    7. c |= c >> 16;
    8. c += 1;

    代码：

    1. public class ArrayQueue3_2 implements Queue, Iterable{
    2.  
    3.     private int head = 0;
    4.     private int tail = 0;
    5.     private  E[] array;
    6.  
    7.     //SuppressWarnings:抑制警告
    8.     @SuppressWarnings("all")
    9.     public ArrayQueue3_2(int capacity) {
    10.         //1.抛异常:当输入的数不是2的幂则跑异常
    11.         if(((capacity&capacity-1)!=0)){
    12.             throw new IllegalArgumentException("capactiy 必须是2的幂");
    13.         }
    14.         //2.将输入的数不是2的幂改成2^n 
    15.         capacity -= 1;
    16.         capacity |= capacity >> 1;
    17.         capacity |= capacity >> 2;
    18.         capacity |= capacity >> 4;
    19.         capacity |= capacity >> 8;
    20.         capacity |= capacity >> 16;
    21.         capacity += 1;
    22.         array = (E[]) new Object[ capacity ];//这个时候就不需要给尾指针留个位置
    23.     }
    24.  
    25.     @Override
    26.     public boolean offer(E value) {
    27.         if (isFull()) {
    28.             return false;
    29.         }
    30.         //进行(int):数组中只能存储Int类型，不能是long类型所以要转换
    31.         //array[(int) (Integer.toUnsignedLong(tail)% array.length)] = value;
    32.         //以下方法比以上方法的优点：1.&的运算更加优化   2.这也防止了int类型超出最大值的情况
    33.         array[tail& (array.length-1)]=value;
    34.         tail++;
    35.         return true;
    36.     }
    37.  
    38.     @Override
    39.     public E poll() {
    40.         if (isEmpty()) {
    41.             return null;
    42.         }
    43.         //E value = array[(int) (Integer.toUnsignedLong(head)% array.length)];
    44.         E value = array[head& (array.length-1)];
    45.         head++;
    46.         return value;
    47.     }
    48.  
    49.     @Override
    50.     public E peek() {
    51.         if (isEmpty()) {
    52.             return null;
    53.         }
    54.         //return array[(int) (Integer.toUnsignedLong(head)% array.length)];
    55.         return array[head& (array.length-1)];
    56.     }
    57.  
    58.     @Override
    59.     public boolean isEmpty() {
    60.         return head==tail;
    61.     }
    62.  
    63.     @Override
    64.     public boolean isFull() {
    65.         return tail-head==array.length;
    66.     }
    67.  
    68.     @Override
    69.     public Iterator iterator() {
    70.         return new Iterator() {
    71.             int p = head;
    72.             @Override
    73.             public boolean hasNext() {
    74.                 return p!=tail;
    75.             }
    76.  
    77.             @Override
    78.             public E next() {
    79.                 //E value = array[(int) (Integer.toUnsignedLong(p)%array.length)];
    80.                 E value = array[p& (array.length-1)];
    81.                 p++;
    82.                 return value;
    83.             }
    84.         };
    85.     }
    86. }

  • 相关阅读:
    Leetcode 1769. 移动所有球到每个盒子所需的最小操作数
    编程学：关于同类词的等长拼写问题
    金仓数据库 KingbaseGIS 使用手册（6.6. 几何对象校验函数、6.7. 空间参考系函数）
    aosp定制android系统
    百度地图自定义覆盖物(html)格式
    【HMS Core】定位地图服务常见问题，穿戴设备支持、比例尺支持、在非华为手机上逆地理编码的支持？
    眺望 2023，一线汽车品牌营销玩得越来越花了
    Servlet执行流程&&Servlet 生命周期
    pandas定位选取某列某指标最大值所在的行记录，比如月底
    Acrel-3000WEB电能管理系统在都巴高速的应用
  • 原文地址：https://blog.csdn.net/m0_60333804/article/details/133419586