`

循环数组 and ArrayDeque

 
阅读更多

 

   我竟然今天才知道循环数组这个概念!

   1. 怎么实现循环?

      通过首尾两个下标!如果尾下标的下一个就是头下标,那么队列就满了?但是怎么知道尾下标的下一个了?可一通过下标与数组长度取余!

      还有就是如果首尾相等,那么这这个队列为空!

      ArrayDeque 就是通过一个循环数组实现的!它判断队列是否满了或者获得前一个元素?通过:

      分析源码的过程中,我就在纳闷,ArrayDeque里面的elements数组,通过位操作进行循环数组判断时是怎么做到的!

      比如说,如果elements.length - 1 = 4 , head = 2 , 那么无论怎么& 都是0 , 根本就得不到想得到的头元素啊!

     通过分析它的构造函数以及结合位运算的规律,发现,elements.length - 1 根本就不可能等于4 , 8 , 16 这样的2^n ,但是elments.length 却可以为8 , 16 , 32这样2^n ,4除外,最小为8

     再看看位运算的规律 : elements.length = 2 ^ n , 那么它的二进制形式,比如8 , 1000 ,那么比8小的数 , 一定是他后三位的随意组合,所以相与一定为0 ,但是对于elements.length - 1 , 比如7,

    0111 , 那么,<=7 的数与7相与,不就等于本本身吗,负数相反! 

   

负数的二进制规律:

1、取负数的绝对值的原码;

2、计算原码的反码;正数的反码与其原码相同;负数的反码是对其原码逐位取反,但符号位除外。
//原码10010= 反码11101 (10010,1为符号码,故为负) (11101)
3、对反码加一,获取补码。

 

  

   构造函数:

    分配elements数组空间

private void allocateElements(int numElements) { //假设numElements = 10 二进制 : 1010
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1); // 右移一位 0101 然后与 1010 相或 = 1111 = 15
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16); // 15 为什么要右移多次了?
            initialCapacity++; // 16

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

 

 

public void addFirst(E e) {  
    if (e == null)  
        throw new NullPointerException();  
    // 本来可以简单地写成head-1,但如果head为0,减1就变为-1了,和elements.length - 1进行与操作就是为了处理这种情况,这时结果为elements.length - 1。  
    elements[head = (head - 1) & (elements.length - 1)] = e;  
    if (head == tail) // head和tail不可以重叠  
        doubleCapacity();  
}  

 

  

public void addLast(E e) {  
    if (e == null)  
        throw new NullPointerException();  
    // tail位置是空的,把元素放到这。  
    elements[tail] = e;  
    // 和head的操作类似,为了处理临界情况 (tail为length - 1时),和length - 1进行与操作,结果为0。  
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)  
        doubleCapacity();  
}  

  代码来源 : http://blog.csdn.net/microtong/article/details/4626224

/** 
 * 数组实现的循环队列 
 * @author TongQiang 
 */  
public class QueueArray {  
    Object[] a; //对象数组,队列最多存储a.length-1个对象  
    int front;  //队首下标  
    int rear;   //队尾下标  
    public QueueArray(){  
        this(10); //调用其它构造方法  
    }  
    public QueueArray(int size){  
        a = new Object[size];  
        front = 0;  
        rear =0;  
    }  
    /** 
     * 将一个对象追加到队列尾部 
     * @param obj 对象 
     * @return 队列满时返回false,否则返回true 
     */  
    public boolean enqueue(Object obj){ 
    	// g关于这个地方为什么要rear+1 这样不就会少加一个元素吗?
//    	如果是rear%a.length 的话,那么dang rear = 4 ,接下来,出队列,那么front = 1 , 那么这是rear % a.length = 0 . a[rear] 不就出错了吗
        if((rear+1)%a.length==front){  
            return false;  
        }  
        a[rear]=obj;  
        rear = (rear+1)%a.length;  
        return true;  
    }  
    /** 
     * 队列头部的第一个对象出队 
     * @return 出队的对象,队列空时返回null 
     */  
    public Object dequeue(){  
        if(rear==front){  
            return null;  
        }  
        Object obj = a[front];  
        front = (front+1)%a.length;  
        return obj;  
    }  
    public static void main(String[] args) {  
        QueueArray q = new QueueArray(4);  
        System.out.println(q.enqueue("张三"));  
        System.out.println(q.enqueue("李斯"));  
        System.out.println(q.enqueue("赵五"));  
        System.out.println(q.enqueue("王一"));//无法入队列,队列满  
        for(int i=0;i<4;i++){  
            System.out.println(q.dequeue());  
        }  
    }  
}  

 

分享到:
评论

相关推荐

    循环数组实现队列

    循环数组实现队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。队列的操作受限制,和栈一样,它是一种操作受限制的线性表。进行插入操作的...

    队列代码 循环数组 自编的

    ### 队列数据结构与循环数组实现 #### 一、队列基本概念 队列是一种先进先出(First In First Out, FIFO)的数据结构,主要用于处理需要按顺序执行的任务集合。在计算机科学中,队列被广泛应用于操作系统任务调度...

    一个串口数据接收的循环数组管理函数库

    主要是对一个循环数组的管理,使用一个循环数组形成一个接收数据的无限缓冲机制。在数组中使用了三级缓冲进行接收调度,递次溢出覆盖或锁定处理数据。这样可以灵活的用一个数组来接收三个数据包或一个超大数据包。 ...

    利用Excel联合数组公式等比例构造一维循环数组.rar

    本压缩包文件“利用Excel联合数组公式等比例构造一维循环数组.rar”聚焦于如何通过MOD函数、COLUMN函数和LOOKUP函数来创建一个等比例的循环数组。下面我们将深入探讨这些知识点: 首先,我们需要理解什么是数组公式...

    PHP 数组切割分段循环 数组切割分段循环

    PHP 数组切割分段循环 数组切割分段循环

    循环数组的算法源代码。 这是一个环型数组模版。一般可用做缓冲区的使用.rar

    循环数组是一种特殊的数组数据结构,它在物理存储上与普通一维数组并无区别,但其逻辑上形成一个环形结构,使得数组的最后一个元素之后紧接着第一个元素,这种设计常用于实现高效的数据缓冲机制。在C#编程语言中,...

    同步队列-无锁队列-循环数组无锁队列.zip

    配套代码讲解:https://blog.csdn.net/songchuwang1868/article/details/90200251 ...同步队列-无锁队列-循环数组无锁队列 同步队列-无锁队列-循环数组无锁队列 同步队列-无锁队列-循环数组无锁队列

    循环链表队列 循环数组队列的代码实现

    ### 循环链表队列与循环数组队列的代码实现解析 在计算机科学中,队列是一种重要的数据结构,遵循先进先出(FIFO)原则。队列可以使用多种方式实现,包括链表和数组。本文将深入探讨两种队列实现方式:循环链表队列...

    matlab数组循环赋值

    matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值matlab数组循环赋值...

    xunhuan.rar_循环数组

    循环数组是一种特殊的数组结构,它在内存中形成一个闭合的环形,使得数组的最后一个元素之后紧跟着第一个元素。这种数据结构在处理循环逻辑或实现特定算法时非常有用,例如在游戏编程中的路径查找、音乐播放列表或者...

    Linux shell数组循环的实例详解

    shell数组循环 测试shell数组,循环的例子: arr=(a b c) echo 所有的内容如下:${arr[@]} echo 数组的长度:${#arr[*]} for var in ${arr[@]} do echo 打印的内容:$var done 输出的内容如下: 以上...

    计算机前端-核心编程. Smarty08foreach循环数组.avi

    计算机前端-核心编程. Smarty08foreach循环数组.avi

    FOR循环数组.vi

    LABVIEW学习时做的一个小课题,他将有利于你虚拟仪器的学习

    循环结构与数组-for

    第4章 循环结构与数组-for.ppt 让你跟好的学习Java循环

    Vue如何循环提取对象数组中的值

    1.数据如下,提取name和callcount 2代码. getQueryCallStatistics(sesp1, this.provinceId).then((res) =&gt; { let arr = []; let arr1 = []; let arr2 = [];... this.xunshiMap = res.data.callstatistics;...

    java集合-ArrayDeque的使用

    基于数组实现:ArrayDeque 内部使用循环数组来存储元素。这种实现方式使得在两端进行插入和删除操作时具有较高的效率。 不允许存储 null 元素:与大多数Java集合不同,ArrayDeque 不允许存储 null 元素。如果试图...

    java代码-使用java增强for循环 string数组赋值的源代码

    java代码-使用java增强for循环 string数组赋值的源代码 ——学习参考资料:仅用于个人学习使用!

    js代码-按数量循环截取数组元素

    标题提到的"js代码-按数量循环截取数组元素"涉及到的是如何使用JavaScript处理数组,特别是按照特定数量分块或分割数组。这种技术在数据处理、分页加载或者批量操作等场景中非常有用。下面将详细解释这个知识点。 ...

    数组循环移位问题的解法的探究

    ### 数组循环移位问题的解法探究 在计算机科学领域,数组作为一种基本的数据结构,在很多算法和数据处理中扮演着重要角色。特别是在涉及到数组元素的移动时,如何高效地进行数组元素的移位操作成为了许多算法研究的...

Global site tag (gtag.js) - Google Analytics