首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >有没有人能把我的deque代码快速看一遍?

有没有人能把我的deque代码快速看一遍?
EN

Stack Overflow用户
提问于 2011-02-09 03:22:40
回答 2查看 516关注 0票数 0

我已经在这上面工作了一段时间了,我想我终于破解了它,它对我所有的测试都有效,但我感觉会有一些微不足道的问题。这是一个高度简化的双边队列(deque)版本,每次添加一个值时,都会生成一个临时数组来存储所有值,然后再追加新值。我相信这是最容易解释的。如果有人能再检查一遍我是正确的,并且这里没有明显的错误,我将非常感谢。非常感谢大家!:)

代码语言:javascript
复制
    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;
  }




}
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2011-02-09 03:29:05

下面是一些评论:

  • 我会使用TE作为类型参数的名称,而不是将常量CAPACITY重命名为DEFAULT_CAPACITY,并使其返回一个值,即使双端队列在逻辑上是empty
  • last(),的,removeFirst()也会返回一个值,如果end为0<
  • >H218T><E>H119,则end将抛出适当的异常。将容量与大小分开没有意义,除非您使用它来避免每次都创建新的数组。如果您总是要在任何更改时扩展/收缩数组,只需使用数组本身-您可以根据数组的长度来判断大小,removeFirst
  • 中的循环界限是capacity而不是end
  • Use System.arraycopy作为复制数组的更简单方法,您在<代码>D32中没有分配给deque -因此您在注释中看到异常。<代码>H233<代码>F234

我不确定我是否看到了仅仅使用ArrayList<T>的好处……拥有单独的Deque实现的主要目的是使添加头部和尾部的成本更低……在这里我们两者都没有!

..。当然也可以使用ArrayDequeLinkedList :)

票数 3
EN

Stack Overflow用户

发布于 2011-02-09 03:29:30

我建议

  • 不会在每次添加或删除条目时都创建新的Object[]。
  • 使用System.arrayCopy()而不是手动复制。
  • 您不需要复制到最大容量,只需要复制到最后。
  • 您可以使用环形缓冲区来避免移动元素(不需要复制)
  • 基于名称的拖放与ArrayList、ArrayBlockingQueue等更加一致。
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4937326

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档