0

我有一个家庭作业，这是我在这里的第一个问题，并且已经为此工作了一段时间。通常我可以弄清楚事情，但我真的被卡住了。这是我的代码和我使用测试仪的输出。我的 moveToBack 是 enqueue 方法的一种复制粘贴。我仍然没有弄清楚为什么输出是古怪的。它甚至不像一个队列！

import java.util.*;

public class NoDuplicatesArrayQueue<T> implements
        NoDuplicatesQueueInterface<T>, java.io.Serializable {
    private T[] queue;
    private int frontIndex;
    private int backIndex;
    private static final int INITIAL_CAPACITY = 50;
    private int length = 0;

    public NoDuplicatesArrayQueue() {
        this(INITIAL_CAPACITY);
    }// end NoDuplicatesArrayQueue

    public NoDuplicatesArrayQueue(int initialCapacity) {
        queue = (T[]) new Object[initialCapacity + 1];
        frontIndex = 0;
        backIndex = initialCapacity;
    }// end NoDuplicatesArrayQueue

    public void display() {
        for (int i = 0; i < length; i++)
            System.out.println(queue[i]);
    }// end display

    public T dequeue() {
        T front = null;

        if (!isEmpty()) {
            front = queue[frontIndex];
            frontIndex = (frontIndex + 1) % queue.length;

        } // end if
        length--;
        return front;
    } // end dequeue

    public void enqueue(T newEntry) {
        boolean found = false;
        for (int index = 0; !found && (index < length); index++) {
            if (newEntry.equals(queue[index]))
                found = true;
        }// end for
        if (found == false) {
            if (isArrayFull())
                doubleArray();

            backIndex = (backIndex + 1) % queue.length;
            queue[backIndex] = newEntry;
            // System.out.println(length);
            length++;
        } else {
            System.out.println("A duplicate exists");
        }//end else
    }//end enqueue

    public T getFront() {
        T front = null;

        if (!isEmpty())
            front = queue[frontIndex];

        return front;
    } // end getFront

    public boolean isEmpty() {
        return frontIndex == ((backIndex + 1) % queue.length);
    } // end isEmpty

    public void clear() {
        if (!isEmpty()) { // deallocates only the used portion
            for (int index = frontIndex; index != backIndex; index = (index + 1)
                    % queue.length) {
                queue[index] = null;
            } // end for

            queue[backIndex] = null;
        } // end if

        frontIndex = 0;
        backIndex = queue.length - 1;
    } // end clear

    public void moveToBack(T newEntry) {
        boolean found = false;
        for (int index = 0; !found && (index < length); index++) {
            if (newEntry.equals(queue[index]))
                found = true;
        }//end for
        if (found == false) {
            // if (isArrayFull())
            // doubleArray();

            backIndex = (backIndex + 1) % queue.length;
            queue[backIndex] = newEntry;
            System.out.println(newEntry);
            length++;
        } else {
            System.out.println("A duplicate exists");
        }//end else
    }//end moveToBack

    private boolean isArrayFull() {
        return frontIndex == ((backIndex + 2) % queue.length);
    } // end isArrayFull

    private void doubleArray() {
        T[] oldQueue = queue;
        int oldSize = oldQueue.length;

        queue = (T[]) new Object[2 * oldSize];

        for (int index = 0; index < oldSize - 1; index++) {
            queue[index] = oldQueue[frontIndex];
            frontIndex = (frontIndex + 1) % oldSize;
        } // end for

        frontIndex = 0;
        backIndex = oldSize - 2;
    } // end doubleArray
}

输出测试仪

public class LabDPartBDriver {

      public static void main(String args[])
    {
        NoDuplicatesArrayQueue<Integer> test1 = new NoDuplicatesArrayQueue<Integer>();

        test1.enqueue(1);
        test1.enqueue(3);
        test1.enqueue(2);
        test1.enqueue(0);
        test1.enqueue(-1);
        System.out.println("The queue has ");
        test1.display();
        System.out.println();


        test1.enqueue(test1.dequeue());
        test1.enqueue(test1.dequeue());
        test1.enqueue(test1.dequeue());
        test1.enqueue(test1.dequeue());
        test1.enqueue(test1.dequeue());
        System.out.println("The queue should be the same ");
        test1.display();
        System.out.println();


        test1.enqueue(1);
        test1.enqueue(3);
        test1.enqueue(2);
        test1.enqueue(0);
        test1.enqueue(-1);
        System.out.println("The queue should be the same ");
        test1.display();
        System.out.println();


        test1.moveToBack(3);
        System.out.println("The queue should be 1, 2, 0, -1, 3 ");
        test1.display();
        System.out.println();

        test1.moveToBack(0);
        System.out.println("The queue should be 1, 2, -1, 3, 0 ");
        test1.display();
        System.out.println();

        test1.moveToBack(1);
        System.out.println("The queue should be 2, -1, 3, 0, 1");
        test1.display();
        System.out.println();

        test1.moveToBack(5);
        test1.moveToBack(5);
        test1.moveToBack(5);
        test1.moveToBack(5);
        test1.moveToBack(5);
        test1.moveToBack(5);
        System.out.println("The queue should be 2, -1, 3, 0, 1, 5");
        test1.display();
        System.out.println();


    }


}

OUTPUT.. 队列有 1 3 2 0 -1

存在重复 存在重复 队列应该相同 1 3 2

存在重复 存在重复 存在重复 队列应该相同 1 3 2 0 -1

存在重复队列应该是 1, 2, 0, -1, 3 1 3 2 0 -1

存在重复队列应该是 1, 2, -1, 3, 0 1 3 2 0 -1

存在重复队列应该是 2, -1, 3, 0, 1 1 3 2 0 -1

5 5 5 5 5 5 队列应该是 2, -1, 3, 0, 1, 5 1 3 2 0 -1 2 0 -1 0 -1 5

4

1 回答 1

0

它说它是重复的，因为当您将其出列时，您并没有从数组中删除值..您只是获取值并返回它..

详细解释考虑这个

  | 1 | 3 | 2 | 0 | -1 |

        ^(front pointer moved after deque)

在您从 index = 0 搜索的 for 循环中排队时，

并且在 queue[0] 中驻留值 1 并且您正在排队 dequed 1（这不是真正的 dequeued），这会导致重复的条目。

而且我还建议您考虑使用 anArrayList而不是数组，并使用 anIterator来迭代列表并在出队时删除。

于 2013-11-03T18:23:00.330 回答