java - 不使用Java库的ADT队列

Question

我目前正在准备即将到来的考试，并且有一个旧考试的味道，我们已经获得了 ADTQueue

public interface ADTQueue<T> { public void enq(T element);
public void deq();
public T front();
public boolean empty(); } 

我们现在必须实现类 Queue 以及一个带有构造函数 ListElement(T element) 的内部类以及其中的一些方法...

我已经实现了，这是我的以下代码:

public class Queue<T> implements ADTQueue<T> {
private ListElement<T> head;
private ListElement<T> tail;

public Queue(){
    head=null;
    tail=null;
}

public void enq (T element){
    if (empty()){
        head= new ListElement(element);
        tail= new ListElement(element);
    }

    tail.nextElement=new ListElement(element);
    tail=tail.nextElement;
}

public void deq(){
    if (empty()){
        throw new Exception();
    }

    T firstElement=front();
    head=head.nextElement;
    if (head==null){
        tail = null;
    }
}

public T front(){
    if(empty()){
        return null;
    }
    return head.element;
}
public boolean empty(){
    return (head==null);
}

public class ListElement<T>{
    private T element = null;
    private ListElement<T> nextElement = null;

    public ListElement(T element) {
        this.element = element;
    }

    public T getElement() {
        return element;
    }

    public ListElement<T> getNextElement() {
        return nextElement;
    }

    public void setNextElement(ListElement<T> nextElement) {
        this.nextElement = nextElement;
    }



}

我想知道我所做的是否正确以及我是否可以做得更好。另外，如果我想做同样的事情但使用双链表，它会是什么样子？我知道，我还需要 get- 和 setPreviousElement，但我不确定入队和出队方法会发生什么变化......如果你们能给一些建议，我会很高兴提前谢谢

Answer 1

1)更好的返回类型的建议:

• 公共(public) boolean 排队(T元素)

  应该是 boolean 值，而不是 Void。

• 公共(public)T出队();

  应该是T，而不是Void。

2) 链接 - 链接列表中的单个对象。

第 3+4 行:

新元素到达后​​，您将创建 2 个具有相同数据 (T) 的不同链接，而不是 1 个链接(头和尾也指向此链接)。

第 5+6 行:我认为您忘记了用 else{...} 包装其余代码。

更改前:

1 public void enq (T element){
2 if (empty()){
3    head= new ListElement(element);
4    tail= new ListElement(element);
  }

5 tail.nextElement=new ListElement(element);
6 tail=tail.nextElement;

}

建议更改后:

1 public void enq (T element){
2 if (empty()){
3    head= new ListElement(element);
4    tail= head;
5  }else{

6   tail.nextElement=new ListElement(element);
7   tail=tail.nextElement;
  }

}