不使用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元素)的内部类和其中的一些方法…

我做了一个实现，这是我下面的代码:

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，但我不确定，在enqueue和dequeue方法中会发生什么变化…如果你们能给点建议，我会很高兴的提前致谢

Answer 1

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

• public boolean enqueue(T element)

  应该是布尔值，而不是Void。

• public T dequeue();

  应该是T，而不是Void。

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

3 + 4行:

当一个新元素到来时，你用相同的数据(T)创建2个不同的链接，而不是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;
  }

}

Answer 2

我也试着实现ADTStack，如果你们中有人能告诉我，它看起来是否很好，我应该改进什么

public class Stack<T> implements ADTStack<T> {
private ListElement<T> firstElement;
int size = 0;
public static void main(String[] args) {
    // TODO Auto-generated method stub
}
@Override
public void push(T element) {
    if (empty()){
        firstElement = new ListElement(element);
        size++;
    }
    else{
        firstElement.nextElement=firstElement;
        firstElement=new ListElement(element);
        size++;
    }
}
@Override
public void pop() {
    if(empty()){
        throw new RuntimeException("stack is empty");
    }
    else {
        T element = top();
        firstElement=firstElement.nextElement;
        size--;
    }

}
@Override
public T top() {
    if(empty()){
        return null;
    }
    else{
        return firstElement.element;
    }
}
@Override
public boolean empty() {
    return (firstElement==null);
}
@Override
public int size() {
    return size;
}
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> element){
        this.nextElement = nextElement;
    }
}

}