调整大小的圆形阵列，在双端队列实施

Question

我想在这里使用圆形阵列来实现双端队列为我的代码（抱歉张贴整个班级）

public class Deque<Item> implements Iterable<Item> { 

    private int frontIndex; 
    private int backIndex; 
    private static final int defaulSize = 8; 
    private int size; 
    private Item holder[]; 

    private int capacity; 

    public Deque() { 
     holder = (Item[]) new Object[defaulSize]; 
     this.size = 0; 
     this.frontIndex = 0; 
     this.backIndex = 0; 
     this.capacity = defaulSize; 
    } 

    public boolean isEmpty() { 

     return this.size == 0; 

    } 

    public int size() { 
     return this.size; 
    } 

    public void addFirst(Item item) throws Exception { 

     if (item == null) { 

      throw new NoSuchElementException(); 
     } 
     if (size == capacity) { 

      doubleCapacity(); 
     } 
     holder[this.frontIndex] = item; 
     this.frontIndex = Math.floorMod((this.frontIndex + 1), capacity); 
     size++; 

    } 

    public void addLast(Item item) throws Exception { 

     if (item == null) { 

      throw new NoSuchElementException(); 
     } 

     if (size == capacity) { 

      doubleCapacity(); 
     } 
     holder[this.backIndex] = item; 
     this.backIndex = Math.floorMod((this.backIndex - 1), capacity); 
     size++; 

    } 

    public Item removeFirst() throws Exception { 

     if (isEmpty()) { 
      throw new Exception("Deque is empty."); 
     } 

     this.frontIndex = Math.floorMod((this.frontIndex - 1), capacity); 
     this.size--; 
     Item e = holder[this.frontIndex]; 
     holder[this.frontIndex] = null; 
     return e; 
    } 

    public Item removeLast() throws Exception { 

     if (isEmpty()) { 
      throw new Exception("Deque is empty."); 
     } 
     this.backIndex = Math.floorMod((this.backIndex + 1), capacity); 
     this.size--; 

     Item e = holder[this.backIndex]; 
     holder[this.backIndex] = null; 
     return e; 
    } 

    private void doubleCapacity() { 

     int p = this.backIndex; 
     int n = holder.length; 
     int r = n - p; // number of elements to the right of p 
     capacity = (n) * 2; 
     Object[] a = new Object[capacity]; 
     System.arraycopy(holder, p, a, 0, r); 
     System.arraycopy(holder, 0, a, r, p); 
     holder = (Item[]) a; 
     this.backIndex = n; 
     this.frontIndex = 0; 

    } 

    private class DequeIterator<E> implements Iterator<E> { 

     private int pos = 0; 

     public boolean hasNext() { 
      return holder.length > pos; 
     } 

     public E next() { 

      return (E) holder[pos++]; 
     } 

     public void remove() { 
      throw new UnsupportedOperationException("Cannot remove an element of an array."); 
     } 
    } 

    @Override 
    public Iterator<Item> iterator() { 
     return this.new DequeIterator<Item>(); 
    } 

} 

的问题来了，当我试图调整用双端队列圆阵，好像所有的指标都得到搞砸

我用类似于它的Java实现如何完成这种方法进行实验

private void doubleCapacity() { 

    int p = this.backIndex; 
    int n = holder.length; 
    int r = n - p; // number of elements to the right of p 
    capacity = (n) * 2; 
    Object[] a = new Object[capacity]; 
    System.arraycopy(holder, p, a, 0, r); 
    System.arraycopy(holder, 0, a, r, p); 
    holder = (Item[]) a; 
    this.backIndex = n; 
    this.frontIndex = 0; 

} 

有没有对如何，如果它作为双端队列调整大小的圆形阵列，或者我如何可以调整此双端以特定的方式

（如果不是一门功课只是个人的研究）

Answer 1

的问题基本上是由于事实这

1将项目添加到deque的

2-加倍的能力，当你不使用正确的索引时，你不更新正确frontIndex和backIndex。

问题1

当frontIndex和backIndex都是平等的，你在任何的双端队列的入口点的添加元素，你需要更新他们都否则你的双端队列的失去控制。例如：开始时frontIndex和backIndex都是== 0。如果你在前面添加一个项目，那么你将有frontIndex = 1（正确）和backIndex = 0（不正确，因为位置0被新项目占用）。这有很多副作用

解决方案1 ​​

public void addFirst(Item item) throws Exception { 

     ... unchanged handling of capacity... 

     holder[this.frontIndex] = item; 
     //CHECK OF THE 2 INDEXES 
     if(this.frontIndex==this.backIndex){ 
      this.backIndex= floorMod((this.backIndex - 1), capacity); 
     } 
     this.frontIndex = floorMod((this.frontIndex + 1), capacity); 
     size++; 
    } 

    public void addLast(Item item) throws Exception { 

     ... unchanged handling of capacity... 

     holder[this.backIndex] = item; 
     if(this.frontIndex==this.backIndex){ 
      this.frontIndex= floorMod((this.frontIndex + 1), capacity); 
     } 
     this.backIndex = floorMod((this.backIndex - 1), capacity); 
     size++; 
    } 

注意，在删除功能中存在的问题以及你应该正确处理它。我没有时间来处理，但解决的办法是直接的

问题2

你总是使用backIndex（和它的概念OK）来处理项目的副本的新阵中，但理想backIndex指向之前的位置 Deque中的第一个元素，因此使用该值会使Deque本身更加混乱。 此外，您还将完全错误的索引分配给新的 backIndex（它应该等于新创建的数组的最后一个元素的索引，而不是指向旧的数组的大小）以及frontIndex（它应该等于位置n，即最后一个填充项目之后的一个元素）。

溶液中2

private void doubleCapacity() { 

    int p = floorMod((this.backIndex+1), capacity); 
    int n = holder.length; 
    int r = n - p; // number of elements to the right of p 
    capacity = (n) * 2; 
    Object[] a = new Object[capacity]; 
    System.arraycopy(holder, p, a, 0, r); 
    System.arraycopy(holder, 0, a, r, p); 
    holder = (Item[]) a; 
    //backIndex should be the last element of the whole array 
    this.backIndex = capacity-1; 
    //frontIndex must be 1 after the last element of the portio of array populated by items 
    this.frontIndex = n; 
} 

随着设计我会不为指标之前和之后处理frontIndex和backIndex如在双端队列已经在第一和最后一个元素的（圆形的）索引，并他们。但这只是我的方式。