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

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，/code> 应该抛出适当的异常
• 将容量与大小分开是没有意义的，除非您使用它来避免每次创建新数组。如果您总是要在任何更改时扩展/缩小数组，只需单独使用该数组 - 您可以仅根据数组的长度来判断其大小
• 在removeFirst中并且 removeLast 循环边界是 capacity 而不是 end
• 的更简单方法
• 使用 System.arraycopy 作为复制数组 在 insertLast 中没有分配给 deque - 因此您在注释中看到了异常。

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

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

Answer 2

我建议

• 不要在每次添加或删除条目时创建一个新的 Object[]。
• 使用 System.arrayCopy() 而不是手动复制。
• 您不需要复制到容量上限，只需复制到末尾即可。
• 您可以使用环形缓冲区来避免需要移动元素（不需要副本）。
• Drop Based 的名称 ArrayDeque 与 ArrayList、ArrayBlockingQueue 等更一致。