所以我有这段代码,我需要分析并从中学习,了解有界队列的工作原理,如下:
class Queue<T> { // bounded
private T[] seq; // the sequence
private int size = 0; // size of sequence
private int head = 0; private int tail = 0; // front and rear
Queue(int n) { // n>0
seq = (T[])(new Object[n]);
}
Queue(){ this(10000);} // = seq=(T[])(new Object[10000]);
boolean isEmpty() { return size==0;}
boolean enq(T t) {
if (size<seq.length) {
seq[tail] = t; tail = (tail+1)%seq.length; size++;
return true;
}
else return false;
}
T deq() {
if (isEmpty()) return null;
else {
T temp = seq[head];
head = (head+1)%seq.length; size--;
return temp;
}
}
}
所以一切都很好,但我不明白为什么在 enq(T t)
方法中会有模数 (%
) 运算和 deq()
方法...
最佳答案
有一个模数运算,以便队列可以用数组表示,其中队列的内容“环绕”数组的末尾到开头。
尺寸为 10 的示例:
[6th] [tail] [empty] [empty] [empty] [head] [2nd] [3rd] [4th] [5th]
这里,head = 5,tail = 1,因为总共添加了 12 项,删除了 5 项。即使数组末尾没有足够的空间,数组开头也有空间来存储更多数据,直到达到数组的容量为止。
模数运算允许 head
和 tail
分别环绕 deq
和 enq
运算,这样 9
就会变成 0
而不是 10
,这会导致 ArrayIndexOutOfBoundsException
。
关于java - 入队和出队方法中的队列模数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20694549/