java - 无法解决Java Deque 迭代Bug

问题描述

在我进行测试时，我发现了我的代码中的错误。

我很难找到我的Deque迭代器出了什么问题。它没有正确迭代，我不知道如何修复它。我已经包含了失败测试的屏幕截图和我完成的代码。

附注：我的教授希望迭代器在向前迭代或反向迭代时从头部出列元素，这就是为什么迭代器更难弄清楚的原因。

失败的单元测试截图： https ://imgur.com/a/srlmrNQ

非常感谢你的帮助！

完整的源代码：

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<E> implements Iterable<E>
{
    private class DequeNode<E>
    {
        private DequeNode<E> _next;
        private DequeNode<E> _previous;
        private E _data;

        private DequeNode(E data)
        {
            _data = data;
        }
    }

    private DequeNode<E> _head;
    private DequeNode<E> _tail;
    private int _depth;
    private static final int EXCLUSIVE_INDEX_START = -1;


    public Deque()
    {
        _head = null;
        _tail = null;
        _depth = 0;
    }

    public boolean enqueue(E element) // This is INSERTION at the TAIL //TODO: DONE!!
    {
        DequeNode<E> newNode = new DequeNode<E>(element);

        if (isEmpty())
        {
            _head = newNode;
        }
        else
        {
            _tail._next = newNode;
            newNode._previous = _tail;
        }
        _tail = newNode;
        _depth++;

        return true;
    }

    public void enqueueAll(Iterable<E> elements)
    {
        for (E eachElement : elements)
        {
            enqueue(eachElement);
        }
    }

    public boolean enqueueHead(E element) // This is insertion at the head //TODO: DONE!!
    {
        DequeNode<E> newNode = new DequeNode<E>(element);

        if (isEmpty())
        {
            _tail = newNode;
        }
        else
        {
            _head._previous = newNode;
            newNode._next = _head;
        }
        _head = newNode;
        _depth++;

        return true;
    }

    public E head()
    {
        checkForStackUnderflow();
        return _head._data;
    }

    public E tail()
    {
        checkForStackUnderflow();
        return _tail._data;
    }

    public E dequeue() // This is removal at the head //TODO: DONE!!
    {
        checkForStackUnderflow();

        E removed = _head._data;

        if (_head._next == null)
        {
            _tail = null;
        }
        else
        {
            _head._next._previous = null;
        }
        _head = _head._next;
        _depth--;

        return removed;
    }

    public E dequeueTail() // This is removal at the tail //TODO: DONE!!
    {
        checkForStackUnderflow();

        E removed = _tail._data;

        if (_head._next == null)
        {
            _head = null;
        }
        else
        {
            _tail._previous._next = null;
        }
        _tail = _tail._previous;
        _depth--;

        return removed;
    }

    public void clear()
    {
        _head = _tail = null;
        _depth = 0;
    }

    public int depth()
    {
        return _depth;
    }

    public boolean isEmpty()
    {
        return _depth == 0;
    }

    public Iterator<E> iterator()
    {
        return new DequeIterator(this, false);
    }

    public Iterator<E> reverseIterator()
    {
        return new DequeIterator(this, true);
    }

    private void checkForStackUnderflow()
    {
        if (isEmpty())
        {
            throw new NoSuchElementException("Stack underflow captain!!!");
        }
    }

    private class DequeIterator implements Iterator<E>
    {
        // The instance variables used throughout the program.
        private int _index;
        private Deque<E> _theList;
        private DequeNode<E> _current;
        private boolean _iterateReverse;


        public DequeIterator(Deque<E> deque, boolean reverse)
        {
            _theList = deque;
            _iterateReverse = reverse;
            _index = 0;
            _current = _head;

            /* If the flag for reverse iteration is detected, then just start
            the index at the end and iterate from the tail.
             */
            if (reverse)
            {
                _index = _theList._depth - 1;
                _current = _theList._tail;
            }
        }

        public boolean hasNext()
        {
            boolean results;

            // If we are reverse iterating check if the index is > than -1.
            if (_iterateReverse)
            {
                results = _index > EXCLUSIVE_INDEX_START;
            }
            /* Getting here means that we are forward iterating so check if the
            index is less than size AKA if we have more elements to go through.
             */
            else
            {
                results = _index < _theList._depth;
            }
            return  results;
        }


        public E next()
        {
            // If we don't have more elements to iterate through then we throw.
            if (!hasNext())
            {
                throw new NoSuchElementException();
            }
            // Update the current to descent if we are reverse iterating.
            if (_iterateReverse)
            {
                _current = _current._previous;
                _index--;
            }
            // If we get to here then just update the current value forward.
            else
            {
                _current = _current._next;
                _index++;
            }

            return dequeue();
        }
    }
}

标签： javaiteratordoubly-linked-listdequereverse-iterator

java - 无法解决Java Deque 迭代Bug

问题描述

解决方案

推荐阅读