不使用 Java 库的 ADT 队列

Question

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

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

我们现在必须使用构造函数 ListElement(T 元素) 和其中的一些方法来实现 class 队列以及内部 class...

我已经实现了，下面是我的代码：

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) 更好的建议Return 类型：

public boolean enqueue(T 元素)

应该是布尔值，而不是 Void。
public T dequeue();

应该是T，而不是Void。

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

第 3+4 行：

在新元素到达时，您创建 2 个具有相同数据 (T) 的不同 Link，而不是 1 个 Link（头部和尾部也指向此 Link).

第 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

我也尝试过实现一个 ADT 堆栈，如果你们中的任何一个能告诉我它看起来是否不错以及我应该改进什么，我会非常高兴

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;

    }
}


}

不使用 Java 库的 ADT 队列

ADT Queue without using Java libraries

java

queue

linked-list

abstract-data-type