节点、队列、出队列

Question

我正在做这个小项目，在同一个类中创建一个队列和一个出队，同时使用我自己的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++;

    }
  }

Answer 1

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

你可以创建你的列表doubly-linked

• you可以使用随机访问数组而不是链表

• 你可以使用Okasaki的"purely functional datastructures"

Answer 2

你也可以让你的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;
 }

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

Answer 3

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