java - 有人可以给我一个双端队列的代码吗？

Question

我已经为此工作了一段时间了，我想我终于解决了它，它适用于我的所有测试，但我有一种感觉，会有一些棘手的问题。这是双边队列(双端队列)的高度简化版本，每次添加值时，都会创建一个临时数组来存储所有值，然后附加新值。我相信这样解释是最简单的。如果有人可以仔细检查我的正确性并且这里没有任何明显的错误，我将非常感激。非常感谢大家! :)

    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;
  }




}

Answer 1

一些评论:

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

我不确定我是否看到这样做比仅使用 ArrayList<T> 有什么好处。不过...拥有单独的 Deque 的要点实现将是使添加到头部和尾部变得便宜......这里我们两者都没有!

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