3

我正在做这个在同一个类中创建队列和出队的小项目，同时使用我自己的 Node 类和接口。

我面临的问题是我已经完成了所有方法，但无法让方法 removeLast 工作，因为在被删除后我无法让后链接到它之前的节点。请帮我提出你的建议？谢谢你。

我的节点类。

public class Node<T> {

  T info;
  Node<T> next;

  public Node(T element) {
    info = element;
    next = null;
  }

  public void setInfo(T element) {
    info = element;
  }

  public T getInfo() {
    return info;
  }

  public void setNext(Node<T> next) {
    this.next = next;
  }

  public Node<T> getNext() {
    return next;
  }

}

我的接口类

public interface DequeInterface<T> {

  void addFront(T element);

  void addLast(T element);

  T removeFront();

  T removeLast();

  boolean isEmpty();

  int getSize();
}

我的双端类

import java.util.NoSuchElementException;

public class Deqeue<T> implements DequeInterface {

  public Node<T> front;
  public Node<T> rear;
  int size;

  public Deqeue() {
    front = null;
    rear = null;
    size = 0;
  }

  @Override
  public T removeFront() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T element = front.getInfo();
    front = front.getNext();
    size--;
    return element;
  }

  @Override
  public T removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T element = rear.getInfo();
    size--;
    return element;
  }

  @Override
  public int getSize() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return rear == null;
  }

  @Override
  public void addFront(Object element) {
    Node<T> newNode = front;

    if (newNode == null) {
      rear = front;
    }
      front = new Node(element);
      front.setNext(newNode);
      size++;
  }

  @Override
  public void addLast(Object element) {
    Node<T> newNode = rear;

    if (newNode == null) {
      front = rear;
    }
      rear = new Node(element);
      newNode.setNext(rear);
      size++;

    }
  }
4

5 回答 5

2

问题是您的列表是单链接的。不幸的是，删除单链表的最后一个节点需要遍历整个列表。一些替代方案：

  • 你可以让你的列表双向链接
  • 您可以使用随机访问数组而不是链表
  • 你可以使用冈崎的“纯功能数据结构”双端队列
于 2013-04-11T22:09:03.850 回答
1

您也可以Node参考以前Node的内容。这将创建一个双向链表。

public class Node<T> {

    T info;
    Node<T> next;
    Node<T> prev;

    public Node(T element) {
        info = element;
        next = null;
        prev = null;
    }


    public void setInfo(T element) {
        info = element;
    }

    public T getInfo() {
        return info;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setPrev(Node<T> prev) {
        this.prev = prev;
    }

    public Node<T> getPrev() {
        return prev;
    }
}

然后在Deque课堂上改变你的removeFront和removeLast方法来解释prev 

public T removeFront() {
    if (isEmpty()) {
       throw new NoSuchElementException();
    }
    T element = front.getInfo();
    front = front.getNext();
    front.setPrev(null); //<<<--------------------------
    size--;
    return element;
}

@Override
public T removeLast() {
    if (isEmpty()) {
       throw new NoSuchElementException();
     }
    T element = rear.getInfo();
    rear.getPrev().setNext(null) //<<<--------------
    rear=rear.getPrev(); //<<<--------------

    size--;
    return element;
 }

当然addFirst和addLast方法也必须更新

@Override
public void addFront(Object element) {
    Node<T> newNode = front;

    front = new Node(element);
    front.setNext(newNode);
    if (newNode == null) {
        rear = front;
    }else{
        newNode.setPrev(front);
    }
    size++;
}

@Override
public void addLast(Object element) {
    Node<T> newNode = rear;
    rear = new Node(element);
    newNode.setNext(rear);

    if (newNode == null) {
        front = rear;
    }else{
        newNode.setNext(rear);
    } 
    size++;
}

如果您不允许更改代码Node并且只能更改removeLast()方法，那么您可以这样做：

@Override
public T removeLast() {
    if (isEmpty()) {
       throw new NoSuchElementException();
     }
    T element = rear.getInfo();
    if(rear==first){
        rear=null;
        first=null;
    }else{
        Node<T> prev = first;
        while(prev.getNext()!=rear){
            prev=prev.getNext();
        }
        rear=prev;
        prev.setNext(null);
   }
    size--;
    return element;
 }

但这将是相当低效的，因为它需要从一开始就遍历整个列表。

于 2013-04-11T22:13:08.667 回答
0

每个节点都应该有一个指向下一个节点和前一个节点的指针。

于 2013-04-11T22:05:26.430 回答
0

您可以使您的列表双重链接（额外的管理和错误的机会），或者您可以在每次 removeLast 并重新设置为新的最后一个时迭代列表（从最后一个删除时性能更差，尤其是在大型列表上。）

于 2013-04-11T22:08:05.240 回答
0

最简单的方法是实现一个双向链表，而不是链表。因此，您的节点类将需要跟踪前一个元素。您将需要更新您的添加功能以支持此功能。完成后，您的 remove last 函数将如下所示：

  @Override
  public T removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T element = rear.getInfo();
    size--;
    rear.getPrev().setNext(null);
    rear = rear.getPrev();
    return element;
  }
于 2013-04-11T22:09:22.317 回答