Java 双端队列实现

Question

Java 新手问题:我正在尝试在 Java 中实现双端队列，但遇到了 dequeueBack(从队列后部删除元素)和 enqueueFront(在队列前部添加元素)方法的问题。我已经得到了相反的方法来工作(dequeueFront 和 enqueueBack)，但我在这一点上被难住了。有什么建议吗？

public class Carr_A06Q4
{
/**
 * Program entry point for deque testing.
 * @param args Argument list.
 */    
public static void main(String[] args)
{
    LinkedDequeue<Integer> deque = new LinkedDequeue<Integer>();

    System.out.println("DEQUE TESTING");

    //per Q1
    deque.enqueueBack(3);
    deque.enqueueBack(7);
    deque.enqueueBack(4);
    deque.dequeueFront();        
    deque.enqueueBack(9);
    deque.enqueueBack(8);
    deque.dequeueFront();
    System.out.println("The size of the deque is: " + deque.size());
    System.out.println("The deque contains:\n" + deque.toString());   

    //new features
    System.out.println(deque.dequeueFront());
    deque.enqueueFront(1);
    deque.enqueueFront(11);                         
    deque.enqueueFront(3);                 
    deque.enqueueFront(5);
    System.out.println(deque.dequeueBack());
    System.out.println(deque.dequeueBack());        
    System.out.println(deque.last());
    deque.dequeueFront();
    deque.dequeueFront();
    System.out.println(deque.first());        
    System.out.println("The size of the deque is: " + deque.size());
    System.out.println("The deque contains:\n" + deque.toString());            
}

/**
 * LinkedDeque represents a linked implementation of a deque.
 * 
 */
public static class LinkedDequeue<T> implements DequeADT<T>
{
    private int count;
    private LinearDoubleNode<T> head, tail; //front, back

    /**
     * Creates an empty queue.
     */
    public LinkedDequeue()
    {
        count = 0;
        head = tail = null;
    }

    /**
     * Adds the specified element to the tail of this queue.
     * @param element the element to be added to the tail of the queue
     */
    public void enqueueBack(T element)
    {
        LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);

        if (isEmpty())
            head = node;
        else
            tail.setNext(node);

        tail = node;
        count++;
    }

    /**
     * Adds the specified element to the head of this queue.
     * @param element the element to be added to the head of the queue
     */
    public void enqueueFront(T element)
    {
        LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);

        count++ ;    
        if (head == null) 
        {
            head = node;
        }
        else 
        {
            node.setNext(head);
            head = node;
        }
    }

    /**
     * Removes the element at the head of this queue and returns a
     * reference to it. 
     * @return the element at the head of this queue
     * @throws EmptyCollectionException if the queue is empty
     */
    public T dequeueFront() throws EmptyCollectionException
    {
       if (isEmpty())
            throw new EmptyCollectionException("queue");

        T result = head.getElement();
        head = head.getNext();
        count--;

        if (isEmpty())
            head = null;

        return result;
    }

    /**
     * Removes the element at the tail of this queue and returns a
     * reference to it. 
     * @return the element at the tail of this queue
     * @throws EmptyCollectionException if the queue is empty
     */
    public T dequeueBack() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("queue");

        T result = tail.getElement();
        tail = tail.getNext();

        if (isEmpty())
            head = null;
        count --;

        return result;
    }

    /**
     * Returns a reference to the element at the head of this queue.
     * The element is not removed from the queue.  
     * @return a reference to the first element in this queue
     * @throws EmptyCollectionsException if the queue is empty
     */
    public T first() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        T result = head.getElement();
        return result;
    }

    /**
     * Returns a reference to the element at the tail of this queue.
     * The element is not removed from the queue.  
     * @return a reference to the first element in this queue
     * @throws EmptyCollectionsException if the queue is empty
     */
    public T last() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        T result = tail.getElement();
        return result;
    }

    /**
     * Returns true if this queue is empty and false otherwise. 
     * @return true if this queue is empty 
     */
    public boolean isEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    /**
     * Returns the number of elements currently in this queue.
     * @return the number of elements in the queue
     */
    public int size()
    {
        return count;
    }

    /**
     * Returns a string representation of this queue. The front element
     * occurs first, and each element is separated by a space. If the
     * queue is empty, returns "empty".
     * @return the string representation of the queue
     */
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
       LinearDoubleNode<T> tmp = head;
       while (tmp != null)
       {
        sb.append(tmp.getElement()).append(" ");
        tmp = tmp.getNext();
       }
       return sb.toString();
    }
}

}

我需要获得以下输出:

双端队列测试: 双端队列的大小为:3 双端队列包含:

498

4

8

9

1

11

双端队列的大小为:2 双端队列包含: 11 1

但我得到的是:

双端队列测试: 双端队列的大小为:3 双端队列包含:

498

4

8

然后我在 dequeueBack 方法中收到 NullPointerException。

感谢任何帮助!

此外，界面是:

public interface DequeADT<T>
{
/**  
 * Adds one element to the front of this deque. 
 * @param element the element to be added to the front of the deque  
 */
public void enqueueFront(T element); //deque specific

/**  
 * Adds one element to the back of this deque. 
 * @param element the element to be added to the back of the deque  
 */
public void enqueueBack(T element);

/**  
 * Removes and returns the element at the front of this deque.
 * Should throw an exception if the deque is empty.
 * @return the element at the front of this deque
 */
public T dequeueFront();

/**  
 * Removes and returns the element at the back of this deque.
 * Should throw an exception if the deque is empty.
 * @return the element at the back of the deque. 
 */
public T dequeueBack(); //deque specific  

/**  
 * Returns, without removing, the element at the front of this deque.
 * Should throw an exception if the deque is empty.
 * @return the first element in the deque
 */
public T first();

/**  
 * Returns, without removing, the element at the back of this deque.
 * Should throw an exception if the deque is empty.
 * @return the last element in the deque
 */
public T last(); //deque specific  

/**  
 * Returns true if this deque is empty and false otherwise.
 * @return true if this deque is empty
 */
public boolean isEmpty();

/**  
 * Returns the number of elements in this deque. 
 * @return the number of elements in the deque
 */
public int size();

/**  
 * Returns a string representation of this deque. The front element
 * occurs first, and each element is separated by a space. If the
 * deque is empty, returns "empty".
 * @return the string representation of the deque
 */
public String toString();

}

节点的描述是:

public class LinearDoubleNode<T>
{
private LinearDoubleNode<T> next;
private T element;

/**
 * Creates an empty node.
 */
public LinearDoubleNode()
{
    next = null;
    element = null;
}

/**
 * Creates a node storing the specified element.
 * @param elem element to be stored
 */
public LinearDoubleNode(T elem)
{
    next = null;
    element = elem;
}

/**
 * Returns the node that follows this one.
 * @return reference to next node
 */
public LinearDoubleNode<T> getNext()
{
    return next;
}

/**
 * Sets the node that follows this one.
 * @param node node to follow this one
 */
public void setNext(LinearDoubleNode<T> node)
{
    next = node;
}

/**
 * Returns the element stored in this node.
 * @return element stored at the node
 */
public T getElement()
{
    return element;
}

/**
 * Sets the element stored in this node.
 * @param elem element to be stored at this node
 */
public void setElement(T elem)
{
    element = elem;
}

}

Answer 1

执行此操作的唯一方法是将内部列表设置为 double-linked .

否则，您将必须扫描整个列表才能找到倒数第二个节点，以便删除最后一个节点。

Double-ended queue ➔ Double-linked list
或动态数组(请参阅 Implementations 部分)。