文档章节

CircularArray 环形数组

一贱书生
 一贱书生
发布于 2016/11/25 09:22
字数 1004
阅读 33
收藏 0

这道题让我们实现一个环形数组类CircularArray,由于环形数组需要调用rotate(int shiftRight)函数,在这里,我们并不会真的去旋转数组,因为这样十分不高效。我们采用另一种实现方法,用一个变量head来记录环形数组的起始 位置,那么调用rotate实际上就是改变head的位置而已。请参见如下代码:

 

复制代码

public static class CircularArray<T> implements Iterable<T> {
    private T[] items;
    private int head = 0;
    
    public CircularArray(int size) {
        items = (T[]) new Object[size];
    }
    
    private int convert(int idx) {
        if (idx < 0) {
            idx += items.length;
        }
        return (head + idx) % items.length;
    }
    
    public void rotate(int shiftRight) {
        head = convert(shiftRight);
    }
    
    public T get(int i) {
        if (i < 0 || i >= items.length) {
            throw new java.lang.IndexOutOfBoundsException("...");
        }
        return items[convert(i)];
    }
    
    public void set(int i, T item) {
        items[convert(i)] = item;
    }
    
    public Iterator<T> iterator() {
        return new CircularArrayIterator<T> (this);
    }
    
    private class CircularArrayIterator<TI> implements Iterator<TI> {
        private int _current = -1;
        private TI[] _items;
        
        public CircularArrayIterator(CircularArray<TI> array) {
            _items = array.items;
        }
        
        @Override
        public boolean hasNext() {
            return _current < items.length - 1;
        }
        
        @Override
        public TI next() {
            ++_current;
            TI item = (TI) _items[convert(_current)];
            return item;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException("...");
        }
    }
}

复制代码

 

上述代码中主要有两部分:

1. 实现CircularArray类

实现的过程中容易犯一些错误,比如:

- 我们不能新建一个泛类的数组,我们必须cast数组或者定义类型为List<T>.

- 取余操作符%对于负数运算后会得到负数,这和数学家们定义的取余运算不同,所以我们需要给负数序列加上items.length,时期变为正数再做运算。

- 我们必须一致地保证将原序列转为旋转序列。

2. 实现迭代器Iterator接口

为了使用迭代来遍历数组for (Obj o : CircularArray),我们必须实现迭代器Iterator接口:

- 修改CircularArray<T>的定义,添加implements Iteratble<T>。这需要我们添加一个iterator()方法给CircularArray<T>。

- 建立CircularArrayIterator<T>类implements Iterator<T>,这需要我们实现CircularArrayIterator的一些方法,如hasNext(), next(), 和 remove()。

一旦我们实现了上面两项,for (Obj o : CircularArray)循环就会神奇的运行了。

 

 

 

  1. package freer.Cupenoruler.ASCII_Player;  
  2.   
  3. /** 
  4.  * 环形缓冲器。逻辑上首尾衔接. 
  5.  * @author Cupenoruler 
  6.  * @version 2.0 
  7.  */  
  8. public  class CircularBuffer<T>  
  9. {  
  10.     /*************************************** 
  11.      * 为保证buffer的put和 get有序进行,用两个索引 
  12.      *  putIndex�待填入元素空位的索引 
  13.      *  getIndex�待取出元素的索引 
  14.      ***************************************/  
  15.     private int putIndex = 0;  
  16.     private int getIndex = 0;  
  17.     private Object[] buffer = null;  
  18.     private int capability = 0; //buffer容量  
  19.       
  20.     /** 
  21.      * jsut for test~  
  22.      * @param helloBaby 
  23.      */  
  24.     public static void main(String[] helloBaby){  
  25. //      CircularBuffer<String> a = new CircularBuffer<String>(1024);  
  26. //      System.out.println(a.putElement(null));  
  27. //      System.out.println(a.putElement("能存进去吗?"));  
  28. //      System.out.println(a.getElement());  
  29. //      System.out.println(a.getElement());  
  30. //      System.out.println(a.getElementWithBlock());  
  31. //      System.out.println("如果控制台木有这条信息,那么上一句代码造成阻塞了~");  
  32.           
  33.         CircularBuffer<String> test = new CircularBuffer<String>(128);  
  34.         int i = 0;  
  35.         for(boolean canPut = true; canPut;){  
  36.             canPut = test.putElement("第" + (++i) + "个元素~~" );  
  37. //          System.out.println(canPut);  
  38.         }  
  39.           
  40.         for(boolean canGet = true; canGet;) {  
  41.             String echoString = test.getElement();  
  42.             canGet = (null != echoString);  
  43.             if(canGet)  
  44.                 System.out.println(echoString);  
  45.         }  
  46.     }  
  47.       
  48.     /** 
  49.      *  
  50.      * @param capability 缓冲区大小 
  51.      */  
  52.     public CircularBuffer(int capability)  
  53.     {  
  54.         this.capability = capability;  
  55.         initialize();  
  56.     }  
  57.       
  58.     /** 
  59.      * @param capability 
  60.      */  
  61.     private void initialize()  
  62.     {  
  63.         this.buffer = new Object[this.capability];  
  64.     }  
  65.   
  66.     /** 
  67.      * 填入元素:注意此函数会造成阻塞 
  68.      * @param element- 带填入元素 
  69.      */  
  70.     public void putElementWithBlock(T element){  
  71.           
  72.         while(!putElement(element)){  
  73.             try {  
  74.                 Thread.sleep(50);  
  75.                   
  76.             } catch (InterruptedException e) {  
  77.                 e.printStackTrace();  
  78.                 System.out.println("put�߳��ж�");  
  79.             }  
  80.         }  
  81.     }  
  82.       
  83.     /** 
  84.      * 取出元素,注意此函数会造成阻塞 
  85.      */  
  86.     public T getElementWithBlock(){  
  87.         T temp = null;  
  88.         while(null == (temp = getElement()) ){  
  89.             try {  
  90.                 Thread.sleep(50);  
  91.                   
  92.             } catch (InterruptedException e) {  
  93.                 e.printStackTrace();  
  94.                 System.out.println("get�߳��ж�");  
  95.             }  
  96.         }  
  97.         return temp;  
  98.     }  
  99.       
  100.     /** 
  101.      * 填入元素,此函数会立即返回 
  102.      * @param element 
  103.      * @return true-操作成功  false-操作失败(待填入数据的元素位还有数据) 
  104.      */  
  105.     public boolean putElement(T element)  
  106.     {  
  107.         if(element == null)  
  108.             throw new NullPointerException("非要往里边填null么?");  
  109.           
  110.         /* 不要覆盖已有数据 */  
  111.         if(this.buffer[this.putIndex] != null){  
  112.             return false;  
  113.         }  
  114.           
  115.         this.buffer[this.putIndex] = element;  
  116.         this.putIndex++;  
  117.         this.putIndex %= this.capability;  
  118.         return true;  
  119.     }  
  120.   
  121.     /** 
  122.      * 取出元素,此函数会立即返回 
  123.      * @return null-待取数据的元素位为null ,非null-成功取出数据 
  124.      */  
  125.     @SuppressWarnings("unchecked")  
  126.     public T getElement()  
  127.     {  
  128.         if(this.buffer[this.getIndex] == null){  
  129.             return null;  
  130.         }  
  131.           
  132.         //拿到引用,并将元素位置空  
  133.         Object temp = this.buffer[this.getIndex];  
  134.         this.buffer[this.getIndex] = null;  
  135.         this.getIndex++;  
  136.         this.getIndex %= this.capability;  
  137.         return (T)temp;  
  138.     }  
  139.       
  140.     public void clear(){  
  141.         for(int i = 0, length = buffer.length; i < length; i++){  
  142.             buffer[i] = null;  
  143.         }  
  144.         this.putIndex = 0;  
  145.         this.getIndex = 0;   
  146.     }  
  147.     /****************************************************\ 
  148.      *              --Setter and Getter--               * 
  149.     \****************************************************/  
  150.     public int getCapability()  
  151.     {  
  152.         return capability;  
  153.     }  
  154.       
  155.     // 新元素是以 索引0 向 索引length 的顺序 put入  
  156.         // 有鉴于此,这里倒过来枚举,防止出现“同向追赶”导致落空的的囧事;  
  157.     public boolean isEmputy(){  
  158.             for(int i = this.buffer.length-1; i > 0; i--){  
  159.                     if( this.buffer[i] != null ){  
  160.                         return false;  
  161.                     }  
  162.             }  
  163.             return true;  
  164.     }  
  165.       
  166. }  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
架构设计:生产者/消费者模式 第5页:环形缓冲区

[3]:环形缓冲区 前一个帖子提及了队列缓冲区可能存在的性能问题及解决方法:环形缓冲区。今天就专门来描述一下这个话题。 为了防止有人给咱扣上“过度设计”的大帽子,事先声明一下:只有当...

冰雷卡尔
2014/05/06
0
0
无锁阻塞队列--unlock-blocking-queue

该组件内部是一个环形数组,受Disruptor启发而创建! Disruptor是一个优秀的无锁队列,内部使用环形数组避免java对象的频繁受垃圾回收器回收。Disruptor本身在使用时会过于复杂而且是基于回调...

吴卫_Mars
2013/11/05
1K
1
Hadoop深入学习:MapTask详解

我们主要来学习MapTask的内部实现。 整体执行流程 如上图示,MapTask的整个处理流程分五个阶段: ●read阶段:通过RecordReader从InputSplit分片中将数据解析成一个个key/value。 ●map阶段:...

李超
2015/04/03
0
0
HashMap高并发

首先讲一下HashMap的Resize机制: 1.Hashmap在插入元素过多的时候需要进行Resize,Resize的条件是 HashMap.Size >= Capacity * LoadFactor。 Resize:HashMap的容量是有限的。当经过多次元素插...

qq_39566598
2017/12/13
0
0
jqPlot图表插件使用说明(二)

柱状图 在jqPlot图表插件使用说明(一)中,我们已经可以通过jqPlot绘制出比较简单的线形图。通过查看源代码,我们也可以看出,线形图是jqPlot默认的图表类型: /** * Class: Series * An i...

纠结名字
2015/08/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring IOC实现原理

1、BeanDefinition 对依赖翻转模式中管理对象依赖关系的数据抽象 实现依赖翻转功能的核心数据结构 依赖翻转功能都是围绕对BeanDefinition 处理完成的 有了这些BeanDefinition 基础数据结构,...

职业搬砖20年
14分钟前
0
0
Python判断变量的数据类型的两种方法

1、isinstance(变量名,类型) def varargsql(self, sql, *args): if isinstance(args, tuple): self.cursor.execute(sql, args) self.conn.commit() 2、通过与其他已......

fang_faye
14分钟前
0
0
xml 转义特殊字符

XML中共有5个特殊的字符,分别是:&<>“’。如果配置文件中的注入值包括这些特殊字符,就需要进行特别处理。有两种解决方法:其一,采用本例中的特殊标签,将包含特殊字符的字符串封装起来;...

inidcard
16分钟前
0
0
Mysql中哪些sql 不会走索引

1. 索引列参与了计算 SELECT `sname` FROM `stu` WHERE `age`+10=30; 2. 索引使用了函数运算 SELECT `sname` FROM `stu` WHERE LEFT(`date`,4) <1990; 3. like SELECT * FROM `houdunwang` W......

ChyiHuang
25分钟前
1
0
nginx 504 Gateway Time-out

打开nginx.config: 参数介绍: #设定http服务器http{include mime.types; #文件扩展名与文件类型映射表default_type application/octet-stream; #默认文件类型#charset utf-8; #默...

lyle_luo
27分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部