双重链接列表Deque实现 [英] Doubly Linked List Deque implementation

问题描述

我正在尝试执行Deque的双重链接列表实现并且我一直收到此错误：

I am trying to do a Doubly linked list implementation of the Deque and I keep getting this error:

15 120
Exception in thread "main" EmptyDequeException: Deque is empty.
    at ListDeque.getFirst(ListDeque.java:83)
    at ListMain.main(ListMain.java:14)

我查了100遍我的代码，无法弄清楚出了什么问题。有人请帮忙..我的代码复制如下...提前感谢

I went over my code 100 times and can't figure out what's wrong..can someone please help.. my code is copied below...thanks in advance

import java.lang.*;
public class ListDeque
{
   protected DNode header, trailer;  // dummy nodes
   protected int size;    // number of elements
   public ListDeque()     // constructor: initialize an empty deque
   {
      header = new DNode( 0, null, null );
      trailer = new DNode( 0, null, null );
      header.setNext(trailer);  // make header point to trailer
      trailer.setPrev(header);  // make trailer point to header
      size = 0;
   }

    /**
     * Display the content of the deque
     *
     */
    public void printDeque()
    {
    for ( DNode p = header.getNext(); p != trailer; p = p.getNext() )
        System.out.print( p.getElement() + " " );
    System.out.println();
    }

   // ***************************************
   // DO NOT MODIFY THE CODE ABOVE THIS LINE.
   // ADD YOUR CODE BELOW THIS LINE.
   //
   // ***************************************
   /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size()
    {
      return size; // replace this line with your code
    }

    /**
     * Returns true if this collection is empty.
     * @return true if this collection is empty.
     */
    public boolean isEmpty()
    {
        if(size==0)
        {
             return true;
        }
        return false;
        //return header.getNaxt()== trailer;

    }

    /**
     * Returns the first element of the deque
     *
     */
    public int getFirst() throws EmptyDequeException
    {
        if(isEmpty())
        {
            throw new EmptyDequeException("Deque is empty.");
        }
        return header.getNext().getElement();
    }

    /**
     * Returns the last element of the deque
     *
     */
    public int getLast() throws EmptyDequeException
    {
        // COMPLETE THIS METHOD
        if(isEmpty())
        {
            throw new EmptyDequeException("Deque is empty.");
        }
        return trailer.getPrev().getElement(); // replace this line with your code
    }

    /**
     * Inserts e at the beginning (as the first element) of the deque
     *
     */
    public void insertFirst(int e)
    {
        DNode newNode = new DNode(e, header, header.getNext());
        header.getNext().setPrev(newNode);
        header.setNext(newNode);
        //addAfter(header, e);
    }

    /**
     * Inserts e at the end (as the last element) of the deque
     *
     */
    public void insertLast( int e )
    {
        DNode newNode = new DNode(e, trailer, trailer.getPrev());
        trailer.getPrev().setNext(newNode);
        trailer.setPrev(newNode);
        //addBefore(trailer, e);
    }

    /**
     * Removes and returns the first element of the deque
     *
     */
    public int removeFirst() throws EmptyDequeException
    {
      if(isEmpty())
      {
        throw new EmptyDequeException("Deque is empty.");
      }
      DNode first= header.getNext();
      int o = first.getElement();
      DNode second = first.getNext();
      header.setNext(second);
      second.setPrev(header);
      size--;
      return o;   // replace this line with your code
    }

    /**
     * Removes and returns the last element of the deque
     *
     */
    public int removeLast() throws EmptyDequeException
    {
      if(isEmpty())
      {
        throw new EmptyDequeException("Deque is empty.");
      }
      DNode last = trailer.getPrev();
      int o = last.getElement();
      DNode secondtolast = last.getPrev();
      trailer.setPrev(secondtolast);
      secondtolast.setNext(trailer);
      size--;
      return o;
    }

} // end class

推荐答案

我看不到你增加大小变量的任何地方。

你在 isEmpty中依赖它方法，但它没有在 insertFirst 方法中递增。



希望这有帮助，

Fredrik

I can't see any place where you're increasing the size variable.
You're relying on it in the isEmpty method but it's not incremented in the insertFirst method.

Hope this helps,
Fredrik

removeLast必须如下：

removeLast must be like:

if (!isEmpty()) {
  Node<T> last = trailer.getPrev();
  T o = last.getElement();
  Node<T> secondtolast = last.getPrev();
  trailer.setPrev(secondtolast);
  secondtolast.setNext(trailer);
  size--;
  return o;
  } else {
    throw new DequeEmptyException("Deque is empty!");
  }

这篇关于双重链接列表Deque实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！