覆盖循环数组中的迭代器

Question

我正在编写自己的双端队列class，我需要覆盖迭代器。

示例：假设数组是 [3,4,5,null,null,null,1,2]，其中 1 是前面，5 是结尾。我需要能够使用迭代器从 1 开始并在 5 之后结束。

这是我的整个 Deque Class。我相信除了 hasNext 方法之外，我对迭代器的一切都正确。

import java.util.Iterator;
import java.util.*;
import javax.swing.border.*;

public class Deque20<E> implements Iterable<E> {

    public final int INITIAL_SIZE = 16;

    private E[] items;
    private E[] temp;
    private int size;
    private int first;

    @SuppressWarnings("unchecked")  // Casting Object[] to E[]
    public Deque20() {
        items = (E[]) new Object[INITIAL_SIZE];
        size = 0;
        first = 0;
    }

    public void addFirst(E e){
        if(size == items.length){
            doubleSize();
        }
        first -= 1;
        if(first == -1){
            first = items.length - 1;
        }
        items[first] = e;
        size += 1;
    }

    public void addLast(E e){
        if(size == items.length){
            doubleSize();
        }
        items[(first + size) % items.length] = e;
        size++; 
    }

    public void removeFirst(){
        items[first] = null;
        first++;
        size--;
    }

    public void removeLast(){
        items[((first + size) % items.length) - 1] = null;
        size--;
    }

    public E peekFirst(){
        if(size == 1){
            return items[first];
        }else{
            return items[first];
        }
    }

    public E peekLast(){
        if(size == 1){
            return items[first];
        }else{
            return items[((first + size) % items.length) - 1];
        }
    }

    @SuppressWarnings("unchecked")
    private void doubleSize(){
        temp = (E[]) new Object[size * 2];
        for(int i = 0; i < size; i++){
            temp[i] = items[(first + i) % items.length];
        }
        items = temp;
        first = 0;
    }

    @SuppressWarnings("unchecked")
    private void realign(){
        temp = (E[]) new Object[size];
        for(int i = 0; i < size; i++){
            temp[i] = items[(first + i) % items.length];
        }
        items = temp;
        first = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        if(size == 0){
            return true;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        Iterator<E> it = new Iterator<E>(){
            private int currentIndex = first;

            @Override
            public boolean hasNext() {
                return currentIndex < size && items[currentIndex] != null;
            }

            @Override
            public E next() {
                return items[currentIndex++];
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
        return it;
    }

    public String toString(){
        String str = "[";
        for(E e : items){
            str += e + ",";
        }
        str += "]";
        return str;
    }
}

编辑：我的问题是如何为我的 Iterator.When 迭代修复 hasNext 方法，它只会转到列表的末尾而不是绕到前面。

Deque20 class 只是一个任务，我必须编写自己的 class，它的行为类似于内置的 ArrayDeque。

Answer 1

您可能需要在内部迭代器的构造函数中初始化 currentIndex class 并在超过大小时将 currentIndex 设置为 0（假设 hasNext 将始终在 next 之前调用，否则 next 应该具有相同的.)，如：

        public Iterator() {
            // init first position - assuming first element is always available somewhere in the array.
            for (int i = 0;i<items.length;i++) {
                if (items[i] == first) {
                    currentIndex = i;
                    break;
                }
            }
        }
    @Override
    public boolean hasNext() {
        if (currentIndex >= size()) {
            currentIndex = 0;
        }
        return  items[currentIndex] != null;
    }

如果有没有 hasNext() 的 next() 调用：

 public E next() {
            if (currentIndex >= size()) {
                currentIndex = 0;
            }
            return items[currentIndex++];
        }

Answer 2

我会使用来自 first 的 currentOffset:

@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        private int currentOffset = 0;

        @Override
        public boolean hasNext() {
            return currentOffset < size;
        }

        @Override
        public E next() {
            E n = items[(first + currentOffset) % items.length];
            currentOffset += 1;
            return n;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
}

此外，我建议您将方法 doubleSize() 重命名为 doubleCapacity()，因为您实际上是在不对双端队列的大小进行任何更改的情况下将容量增加一倍。理想情况下，您应该考虑处理一个 SimultaneousModificationException，其中您在迭代时检测对双端队列的更改。

覆盖循环数组中的迭代器

Overriding Iterator in circular array

java

arrays

iterator

deque

circular-list