1

我正在尝试使用数组来实现队列 ADT 来完成家庭作业（如果由我决定，我会使用链表，但我猜教授希望我们学习新事物或 XD 的东西）。无论如何，我正在研究一种将元素添加到队列末尾的方法，如果它超出范围，同样的方法应该创建一个新的调整大小的数组，这就是我正在努力解决的方法（ enqueue() 方法）。这是我的代码：

import java.util.Arrays;


public class Queue<T> implements QueueInterface<T> {

    private T[] a;
    private int sz;

    public Queue(int capacity) {
        sz = 0;
        @SuppressWarnings("unchecked")
        T[] tempQueue = (T[])new Object[capacity];
        a= tempQueue;
    }

    public void enqueue(T newEntry) {
        try {
        for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }
            }
        sz++;
        }
        catch (ArrayIndexOutOfBoundsException e) {
            @SuppressWarnings("unchecked")
            T[] tempQueue = (T[])new Object[a.length*+5];
            a= tempQueue;
            for (int i=0; i<a.length; i++) {
                if (a[i] == null) {
                    a[i] = newEntry;
                    break;
                }

            }
        }
    }

    public T dequeue() {
        T result = a[0];
        a[0] = null;
        for (int i=1; i<a.length;i++) {
            a[i-1] = a[i];
        }
        sz--;
        return result;
    }

    public T getFront() {
        return a[0];
    }

    public boolean isEmpty() {
        for (int i=0; i<a.length; i++) {
            if (a[i] != null) {
                return false;
            }
        }
        return true;
    }

    public void clear() {
        for (int i=0; i<a.length; i++) {
            a[i] = null;
            sz--;
        }
    }

    @Override
    public String toString() {
        return "Queue [a=" + Arrays.toString(a) + ", sz=" + sz + "]";
    }

}

非常感谢大家的时间！！！

4

5 回答 5

2

如果要使用数组实现队列，我认为最好的方法是使用循环数组。这样，当您dequeue. 但是由于您想实现一个可调整大小（有界）的队列，因此循环数组实现变得有点困难。这里有一些有用的链接，

如果您想要一个实现，只需谷歌即可。

（这可能不是您问题的答案，但我无法评论您的问题。）

于 2012-11-04T23:45:08.997 回答
1

检查数组长度以检测出界 - 异常是昂贵的。

要复制数组，请创建一个适当大小的新数组，然后使用 System.arrayCopy

经验法则不是将大小增加固定数量，而是增加原始大小的百分比（例如大 30%）

于 2012-11-04T23:39:12.153 回答
0

尝试将调整大小的逻辑放入一个名为ensureSize或其他的私有方法中。在那里检查所需的尺寸；如果它太小，请调整数组大小并复制内容。从可能需要增加数组大小的任何方法中调用此方法。

于 2012-11-04T23:29:23.390 回答
0

您的实现可能不是使用数组来实现队列的最有效方式，但鉴于您已决定以这种方式实现它，您的入队方法比它需要的要复杂一些。

您有一个字段sz可用于确定必须放置新条目的位置，而不是检查以查找第一个非空值。并且由于出队没有清除向前移动的最后一个元素，因此对非 null 的搜索无论如何都不会正常工作。

该sz字段还会告诉您何时需要调整大小，而不是通过异常检测该需求。

于 2012-11-04T23:30:22.343 回答
0

补充 Alan Krueger 的回答：调整大小时不必再次遍历整个数组。创建一个临时变量来存储旧数组的长度并从它开始迭代。

于 2012-11-04T23:33:15.663 回答