文档章节

CircularArray 环形数组

一贱书生
 一贱书生
发布于 2016/11/25 09:22
字数 1004
阅读 46
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

Windows 10 设置 Java 环境变量

首先你需要在我的电脑中打开,找到环境变量属性。 找到环境变量属性 找到环境变量属性后单击将会看到下面的设置界面。 在这个界面中设置高级系统设置。 环境变量 在弹出的界面中选择设置环境...

honeymose
今天
2
0
用any-loader封装jQuery的XHR —— 随便写着玩系列

哎,都说没人用JQuery啦,叫你别写这个。 其实我也是好高骛远使用过npm上某个和某个很出名的XHR库,嗯,认识我的人都知道我喜欢喷JQ,以前天天喷,见面第一句,你还用JQ,赶紧丢了吧。但我也...

曾建凯
今天
7
0
聊聊storm的AggregateProcessor的execute及finishBatch方法

序 本文主要研究一下storm的AggregateProcessor的execute及finishBatch方法 实例 TridentTopology topology = new TridentTopology(); topology.newStream("spout1", spout......

go4it
今天
4
0
大数据教程(7.5)hadoop中内置rpc框架的使用教程

博主上一篇博客分享了hadoop客户端java API的使用,本章节带领小伙伴们一起来体验下hadoop的内置rpc框架。首先,由于hadoop的内置rpc框架的设计目的是为了内部的组件提供rpc访问的功能,并不...

em_aaron
今天
5
0
CentOS7+git+github创建Python开发环境

1.准备CentOS7 (1)下载VMware Workstation https://pan.baidu.com/s/1miFU8mk (2)下载CentOS7镜像 https://mirrors.aliyun.com/centos/ (3)安装CentOS7系统 http://blog.51cto.com/fengyuns......

枫叶云
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部