CircularArray 环形数组
CircularArray 环形数组
一贱书生 发表于1年前
CircularArray 环形数组
  • 发表于 1年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

这道题让我们实现一个环形数组类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. }  
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: