文档章节

CircularArray 环形数组

一贱书生
 一贱书生
发布于 2016/11/25 09:22
字数 1004
阅读 16
收藏 0
点赞 0
评论 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
博文 723
码字总数 600072
作品 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
架构设计:生产者/消费者模式 第6页:环形缓冲区的实现

◇判断“空”和“满” 上述的操作并不复杂,不过有一个小小的麻烦:空环和满环的时候,R和W都指向同一个位置!这样就无法判断到底是“空”还是“满”。大体上有两种方法可以解决该问题。 办法...

冰雷卡尔
2014/05/06
0
0
一篇文章,从源码深入详解ThreadLocal内存泄漏问题

1. 造成内存泄漏的原因? threadLocal是为了解决对象不能被多线程共享访问的问题,通过threadLocal.set方法为每一个线程创建一个该对象,并保存在每个线程自己所拥有的threadLocalMap中,这样...

你听___
2017/11/27
0
0
一篇文章带你吃透 hashmap(面试指南升级版)

本篇为升级版 1:hashmap简介(如下,数组-链表形式) HashMap的存储结构 图中,紫色部分即代表哈希表,也称为哈希数组(默认数组大小是16,每对key-value键值对其实是存在map的内部类entry...

java进阶架构师
07/13
0
0
Ring Buffer 实现原理

简介 消息驱动机制是 GUI 系统的基础,消息驱动的底层基础设施之一是消息队列,它是整个 GUI 系统运转中枢,本文介绍了一个基于环形队列的消息队列实现方法,给出了它的数据结构、主要操作流...

AlphaJay
2011/12/06
0
2
C语言 ringBuffer 实现

一、 ringBuffer 介绍 ringBuffer 称作环形缓冲,也有叫 circleBuffer 的。就是取内存中一块连续的区域用作环形缓冲区的数据存储区。这块连续的存储会被反复使用,向 ringBuffer 写入数据总是...

u011303443
03/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

并发设计之A系统调用B系统

A-->B A在发送请求之前,用乐观锁,减少对B的重复调用,这样一定程度上是幂等性。 比如A系统支付功能,要调用B系统进行支付操作,但是前端对"支付"按钮不进行控制,即用户会不断多次点击支付...

汉斯-冯-拉特
16分钟前
0
0
HTTP协议通信原理

了解HTTP HTTP(HyperText Transfer Protocol)是一套计算机通过网络进行通信的规则。计算机专家设计出HTTP,使HTTP客户(如Web浏览器)能够从HTTP服务器(Web服务器)请求信息和服务。 HTTP使用...

寰宇01
39分钟前
0
0
【Java动态性】之反射机制

一、Java反射机制简介

谢余峰
40分钟前
1
0
Centos 6.X 部署环境搭建

1.Linux学习笔记CentOS 6.5(一)--CentOS 6.5安装过程

IT追寻者
53分钟前
0
0
博客即同步至腾讯云+社区声明

我的博客即将搬运同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=8vy9bsmadbko...

xiaoge2016
55分钟前
0
0
大数据教程(3.1):Linux系统搭建网络YUM源服务器

博主在前面的2.5章节讲述了linux系统本地YUM服务器的搭建和httpd轻量级静态网站服务器的安装,本节博主将为大家分享内网环境中搭建自己的网络YUM服务器的全过程。如果大家对本地YUM服务器还不...

em_aaron
59分钟前
0
0
蚂蚁技术专家:一篇文章带你学习分布式事务

小蚂蚁说: 分布式事务是企业集成中的一个技术难点,也是每一个分布式系统架构中都会涉及到的一个东西,特别是在这几年越来越火的微服务架构中,几乎可以说是无法避免,本文就围绕分布式事务...

Java大蜗牛
今天
1
0
新的Steam应用将拓展服务项目

导读 未来几周,Steam将推出两个免费的应用程序Steam Link和Steam Video。这两个应用程序都旨在拓展Steam平台的业务和便利性。 即将开放的Steam Link应用程序最先提供了Android测试版,它将允...

问题终结者
今天
0
0
golang 第三方包的使用总结

golang 第三方包的安装的方法: 1. go get 安装 $ go get github.com/gin-gonic/gin 注意:执行go get 命令需要先安装git命令,并配置git全局变量。 2. 源码包安装 由于国内网络问题,很多时...

科陆李明
今天
1
0
Android Studio调试运行时ADB not responding

最近有我朋友问我一个android studio的调试运行问题,我记得以前也是遇到过得,所以 来写一下 ADB not responding.If you'd like to retry, then please manually kill "adb.exe" and click...

切切歆语
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部