使用数组实现队列 - Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13223996/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implement a queue using an array - Java
提问by salxander
I'm trying to implement a queue ADT using an array for a homework assignment (were it up to me I would be using a linked list, but I guess the professor wants us to learn new things or something XD). Anyway, I'm working on a method to add an element to the end of the queue, this same method should create a new re-sized array if it gets out of bounds, and this is the method I'm struggling with (the enqueue() method). Here is my code:
我正在尝试使用数组为家庭作业实现队列 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 + "]";
}
}
Thanks so much for your time everyone!!!
非常感谢大家的时间！！！
回答by Sajith Janaprasad
If you are going to implement a queue using an array, I think the best way to do it is using a circular array. In that way you don't have to move all elements by one step forward when you dequeue. But since you want to implement a re-sizable (on-bounded) queue, circular array implementation become little bit difficult. Here are some useful links,
如果要使用数组实现队列，我认为最好的方法是使用循环数组。这样，当您使用dequeue. 但是由于您想要实现一个可重新调整大小的（有界）队列，循环数组的实现变得有点困难。这里有一些有用的链接，
If you want an implementation, just Google for it.
如果你想要一个实现，就谷歌一下。
(This may not be an answer for your question, but I cannot comment in your question.)
（这可能不是您问题的答案，但我无法对您的问题发表评论。）
回答by thedayofcondor
Check the array length to detect the outoubounds - exceptions are expensive.
检查数组长度以检测出站 - 异常很昂贵。
To copy the array, create a new array of the proper size and then use System.arrayCopy
要复制数组，请创建一个适当大小的新数组，然后使用 System.arrayCopy
A rule of thumb is not to increase the size by a fixed amount, but to increase by a percentage of the original size (eg 30% larger)
经验法则不是将大小增加固定数量，而是增加原始大小的百分比（例如大30％）
回答by Alan Krueger
Try putting the resizing logic into a private method called ensureSizeor something. Check the desired size there; if it's too small, resize the array and copy the contents over. Call this method from any methods that might need the array size increased.
尝试将调整大小逻辑放入一个称为ensureSize或其他方法的私有方法中。在那里检查所需的尺寸；如果它太小，请调整数组大小并复制内容。从可能需要增加数组大小的任何方法调用此方法。
回答by Don Roby
Your implementation may not be the most efficient way of using an array to implement a queue, but given that you've decided to implement it this way, your enqueue method is a bit more complex than it need be.
您的实现可能不是使用数组实现队列的最有效方式，但鉴于您已决定以这种方式实现它，您的 enqueue 方法比它需要的要复杂一些。
You have a field szthat can be used to determine where the new entry has to be put rather than checking through to find the first non-null. And the search for a non-null won't work properly anyway as the dequeue isn't clearing the last element moved forward.
您有一个字段sz可用于确定必须将新条目放在哪里，而不是通过检查来查找第一个非空条目。并且由于出队没有清除向前移动的最后一个元素，因此搜索非空值无论如何都无法正常工作。
The szfield will also tell you when you need to resize, rather than detecting that need by an exception.
该sz字段还会告诉您何时需要调整大小，而不是通过异常检测该需要。
回答by Paulo Viana
Complementing Alan Krueger's answer: you do not have to iterate through the whole array again when resizing it. Create a temporary variable that stores the old array's length and begin iterating from it.
补充 Alan Krueger 的回答：调整数组大小时不必再次遍历整个数组。创建一个临时变量来存储旧数组的长度并从它开始迭代。
