在 Java 中出队

Question

我在完全实现入队和出队部分时遇到了问题。这是我想要得到的结果：

DEQUE TESTING

The size of the deque is: 3

The deque contains:

4 9 8 

4

8

9

1

11

The size of the deque is: 2

The deque contains:


11 1

但这就是我得到的：

DEQUE TESTING
The size of the deque is: 3
The deque contains:
 4 9 8
4
null
null
null
null
The size of the deque is: 0
The deque contains:

所以，它只打印到某个点。我已经多次检查我的代码（实际上很多次）以试图纠正这个问题，但我无法确定问题出在哪里。我有一种感觉，这是一些需要改变的小事。

这是我的代码：

public class Murray_A06Q3 {
    public static void main(String[] args) {

        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();

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

        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());   

        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());            

    } // End of main method

public static class LinkedDeque<T> implements DequeADT<T> {

    private int count; 
    private LinearDoubleNode<T> firstNode, lastNode;

// constructor
    public LinkedDeque(){

        count = 0;
        firstNode = null;
        lastNode = null;

    } // end of constructor

// Beginning of enqueueFront
    public void enqueueFront(T element) {
        LinearDoubleNode newNode = new LinearDoubleNode();

        if(isEmpty()){
            lastNode = newNode;
            count++;
        }
        else
            firstNode.setPrev(newNode);
        firstNode = newNode;
        count--;

    } // end of enqueFront

// Beginning of enqueueBack
    public void enqueueBack(T element) {
        LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);

        if (isEmpty())
           firstNode = node;
        else
            lastNode.setNext(node);

        lastNode = node;
        count++;

    } // end of enqueueBack

// Beginning of dequeueFront
    public T dequeueFront() {

        T front = null;
        if (!isEmpty()) {
            front = firstNode.getElement();
            firstNode = firstNode.getNext();
            count--;

            if (firstNode == null) {
                lastNode = null;
            }
            else 
                firstNode.setPrev(firstNode);
        }
        return front;

    } // end of dequeueFront

// Beginning of dequeueBack
    public T dequeueBack() {

        T back = null;
        if (!isEmpty()) {
            back = lastNode.getElement();
            lastNode = lastNode.getPrev();

            if (lastNode == null) {
                firstNode = null;
            }
            else 
                lastNode.setNext(null);
        }
        return back;

    } // end of dequeueBack()

    public T first() {
        return firstNode.getElement();
    }

    public T last() {
        return lastNode.getElement();
    }

// Beginning of isEmpty()           
    public boolean isEmpty() {

        if (count == 0) {
            return true;
        }       
        else 
            return false;

    } // End of isEmpty()

// Beginning of size()          
    public int size() {
        return count;
    }

 // Begin of toString() method          
    public String toString() {

        if (isEmpty()) {
            return " ";
        }

        StringBuilder sb = new StringBuilder();
        LinearDoubleNode<T> next = firstNode;

        while(next != null){
            sb.append(" ").append(next.getElement());
            next = next.getNext();
        }

        return sb.toString();

    } // End of toString()

  } // End of LinkedDeque

} // End of class header

Answer 1

双linked 列表的第一条规则是当你添加一个元素时你必须维护两个 links。这是您的代码：

public void enqueueFront(T element) {
    LinearDoubleNode newNode = new LinearDoubleNode();

    if(isEmpty()){
        lastNode = newNode;
        count++;
    }
    else
        firstNode.setPrev(newNode);
    firstNode = newNode;
    count--;

} // end of enqueFront

首先，您永远不会将元素的值放入新节点。

其次，队列应该是这样的

A ⇆ B ⇆ C

但让我们看看当队列中只有 "B" 时如何添加 "A"。您的 firstNode 是 "B"，您将其 prev 设置为 setPrev 以指向您的 "A".

A ← B

但是你没有link从新的"A"回到"B"。这意味着当你需要从正面看队列时，它似乎只有一个元素——A 没有 "next"!

您的 else 子句应该是：

    else {
        firstNode.setPrev(newNode);
        newNode.setNext(firstNode);
    }

然后你就可以从两边遍历列表了。同样的逻辑也应该应用于您的 enqueueBack。

现在，您的出队逻辑：

public T dequeueFront() {

    T front = null;
    if (!isEmpty()) {
        front = firstNode.getElement();
        firstNode = firstNode.getNext();
        count--;

        if (firstNode == null) {
            lastNode = null;
        }
        else 
            firstNode.setPrev(firstNode);
    }
    return front;

}

现在，出队后，将新的 firstNode 的设置为它自己。这意味着您可能有一个无限循环。执行此操作一次后，如果您尝试通过从后面出队来遍历 "prev" link，您将一次又一次地获得相同的节点。 backlink 应该设置为 null（顺便说一下，你在 dequeueBack 中正确设置）。

Answer 2

您忘记设置上一个和元素。在增加计数时你也有一些错误。并对一些未抛出的异常保持谨慎。尽管如此，现在应该很简单了。您有以下具有所需输出的工作代码：

  public static class LinkedDeque<T> {

        private int count;
        private LinearDoubleNode<T> firstNode, lastNode;

        // constructor
        public LinkedDeque(){

            count = 0;
            firstNode = null;
            lastNode = null;

        } // end of constructor

        // Beginning of enqueueFront
        public void enqueueFront(T element) {
            LinearDoubleNode newNode = new LinearDoubleNode();
            newNode.setElement(element);
            if(isEmpty()){

                lastNode = newNode;
                firstNode = newNode;
            }
            else {
                LinearDoubleNode second=firstNode;
                firstNode=newNode;
                firstNode.setNext(second);
                second.setPrev(firstNode);
               // firstNode.setPrev(newNode);

            }

            count++;

        } // end of enqueFront

        // Beginning of enqueueBack
        public void enqueueBack(T element) {
            if (element==null) throw  new NullPointerException("cannot add null to the list");

            LinearDoubleNode<T> node = new LinearDoubleNode<T>(element);
            node.setElement(element);
            if (isEmpty()){
                firstNode = node;
                lastNode=node;}
            else{
                LinearDoubleNode<T> before=lastNode;
                lastNode=node;
                before.setNext(lastNode);
                lastNode.setPrev(before);
            }


            count++;

        } // end of enqueueBack

        // Beginning of dequeueFront
        public T dequeueFront() {

            T front = null;
            if (count==1){
                front=firstNode.getElement();
                firstNode=null;
                lastNode=null;
                count--;
            }
            else if (!isEmpty()) {
                count--;
                front = firstNode.getElement();
                firstNode = firstNode.getNext();
            }

            return front;

        } // end of dequeueFront

        // Beginning of dequeueBack
        public T dequeueBack() {

            T back = null;
            if (count==1){
                back = lastNode.getElement();
                lastNode = null;
                firstNode = null;
                count--;
            }
             else if (!isEmpty()) {
                count--;
                back = lastNode.getElement();
                lastNode = lastNode.getPrev();
                lastNode.setNext(null);
            }
            return back;

        } // end of dequeueBack()

        public T first() {
            return firstNode.getElement();
        }

        public T last() {
            return lastNode.getElement();
        }

        // Beginning of isEmpty()
        public boolean isEmpty() {

            return count==0;

        } // End of isEmpty()

        // Beginning of size()
        public int size() {
            return count;
        }

        // Begin of toString() method
        public String toString() {

            if (isEmpty()) {
                return " ";
            }

            StringBuilder sb = new StringBuilder();
            LinearDoubleNode<T> next = firstNode;

            while(next != null){
                sb.append(" ").append(next.getElement());
                next = next.getNext();
            }

            return sb.toString();

        } // End of toString()

    } // End of LinkedDeque

} // End of class header

    DEQUE TESTING
The size of the deque is: 3
The deque contains:
 4 9 8
4
8
9
1
11
The size of the deque is: 2
The deque contains:
 11 1

在 Java 中出队

Dequeues in Java

java

deque