0

已经为此工作了一段时间，我想我终于破解了它，它适用于我所有的测试，但我感觉会有一些琐碎的问题。这是一个高度简化的双面队列（deque）版本，每次添加一个值时，都会创建一个临时数组来存储所有值，然后附加新值。我相信这种方式最容易解释。如果有人可以请仔细检查我是正确的，这里没有明显的错误，我将非常感激。非常感谢大家！:)

    public class ArrayBasedDeque<EltType> implements Deque<EltType> {

  private final int CAPACITY = 10;
  private int capacity;
  private int end;
  private EltType deque[];  

  public ArrayBasedDeque() {
    this.capacity = CAPACITY;
    deque = (EltType[]) (new Object[capacity]);  
  }
  public EltType first() {
    return  deque[0];
  }
  public EltType last() {
    return deque[end-1];
  }

  public boolean isEmpty() {
    return end == 0;
  }

  public int size() {
   return deque.length;
  }

  public boolean isFull() {
   return end == capacity;
  }
  public void insertFirst(EltType inserted) {
    if (!isEmpty()) {
    EltType[] tempArray;
    capacity+=1;
    tempArray = (EltType[]) new Object[capacity];
    for(int i=0;i<end;i++){
    tempArray[i+1] = deque[i]; 
    }
    deque=tempArray;
    }
    deque[0] = inserted;
    end++;
    }

  public void insertLast(EltType last) {
    if (isFull()){
          EltType[] tempArray;
          capacity+=1;
      tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<end;i++) {
        tempArray[i] = deque[i]; 
      }
//      System.out.print(deque[end]);
    }
    deque[end] = last;   
    end++;
  }

  public EltType removeFirst() {
    EltType[] tempArray;
    EltType returned = deque[0];
    tempArray = (EltType[]) new Object[capacity];
      for (int i=1;i<capacity;i++) {
        tempArray[i-1] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }

  public EltType removeLast() {
    EltType[] tempArray;
    EltType returned = deque[end-1];

    tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<capacity;i++) {
        tempArray[i] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }




}
4

2 回答 2

3

几点评论：

  • 我会使用TorE作为类型参数的名称，而不是EltType
  • 我会将常量重命名CAPACITY为DEFAULT_CAPACITY，并将其设为静态。
  • first()即使双端队列在逻辑上为空，也会返回一个值
  • last(),如果removeLast()为0removeFirst()则应抛出适当的异常end
  • 除非您使用它来避免每次都创建新数组，否则将容量与大小分开是没有意义的。如果您总是要在任何更改时扩展/缩小数组，只需单独使用数组 - 您可以仅从数组的长度判断大小
  • 在removeFirst和removeLast你的循环绑定是capacity而不是end
  • System.arraycopy用作复制数组的更简单方法
  • 您没有分配到dequein insertLast- 因此您在评论中看到的异常。

我不确定我是否看到了使用它的好处ArrayList<T>......拥有一个单独的Deque实现的主要目的是让头部和尾部都便宜......这里我们都没有！

...或者当然只是使用ArrayDequeor LinkedList:)

于 2011-02-08T19:29:04.697 回答
0

我会建议

  • 不要在每次添加或删除条目时创建新的 Object[]。
  • 使用 System.arrayCopy() 而不是手动复制。
  • 您不需要复制到容量，只需要复制到最后。
  • 您可以使用环形缓冲区来避免需要移动元素（不需要副本）
  • Drop Based 从名称 ArrayDeque 与 ArrayList、ArrayBlockingQueue 等更加一致。
于 2011-02-08T19:29:29.913 回答