最近在一本英文版数据结构书上看到这么一个Queue的实现,感觉有错误

Question

最近在一本英文版数据结构书上看到这么一个Queue的实现(源码在最后),
有两个疑问:
1.enqueue方法中,我感觉有很多错误,不知道是不是作者在跟我开玩笑,特别是两个System.arraycopy的实现和tail的指向问题2.dequeue方法中,我觉得
if (size-- == 0) {
    throw new NoSuchElementException();
}
这句话有问题,我觉得应该这么实现
if (size == 0) {
    throw new NoSuchElementException();
}
size--;因为如果size=0的话,就会抛出异常,但是此时并没有让head+=1,也就是说,Queue对象里并没有减少一个元素
而原来的实现if (size-- == 0),这个时候size却减一了,这不是错了吗?我的问题问完了,如果我错了,请说出我错的理由,如果书上确实是写错了,请给出正确的代码来
这两种情况我都是会给分的.以下是这个类的源码:
package c07;import java.util.NoSuchElementException;public class Queue { protected Object[] data;
protected int size, head, tail; // Postcondition: this Queue object has been initialized.
public Queue() {
final int INITIAL_LENGTH = 100;
data = new Object[INITIAL_LENGTH];
size = 0;
head = 0;
tail = -1;// indicates initially empty queue
} // Postcondition: the number of elements in this Queue object has been
// returned
public int size() {
return size;
} // Postcondition: true has been returned if thie Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {
return size == 0;
} // Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: (a reference to ) the element at the front of
// this Queue object has been returned
public Object front() {
if (size == 0) {
throw new NoSuchElementException();
}
return data[head];
} // Postcondition: element has been inserted at the back of this Queue
// object. The averageTime(n) is constant, and
// worstTime(n) is O(n), but for n consecutive
// enqueues, worstTime (n) is still O(n).
public void enqueue(Object element) { if (size == data.length) {
// double the length of data
Object[] oldData = data;
data = new Object[data.length * 2]; // copy oldData[head...oldData.length-1] to
// data[0...oldData.length-1-head]
System.arraycopy(oldData, head, data, 0, oldData.length - head); if (head > 0) {
// copy oldData[0...tail] to data
// [head+1...oldData.length-1]
System.arraycopy(oldData, 0, data, head + 1, tail + 1);
} tail = (tail + 1) % data.length;
size++;
data[tail] = element;
} } // Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be returned.
// Postcondition: the front element has been removed from this Queue object
public Object dequeue() {
if (size-- == 0) {
throw new NoSuchElementException();
}
Object element = data[head];
head = (head + 1) % data.length;
return element;
}}

Answer 1

我没看源码啊  不过我觉得size--只有在下次参与运算的时候才是减1后的值  也就是说你现在size=0， 在size--之后还是0 而不像--size另外  你如果觉得代码有问题 你可以写一个测试代码  看看是不是边界情况出问题了

Answer 2

if (size-- == 0)
应该是先判断if (size == 0)
然后才size--吧
所以应该没有什么影响

Answer 3

对不起,源代码中enqueue的一个括号放错位置了,但不影响我的那两个问题正确的如下:package c07;import java.util.NoSuchElementException;public class Queue { protected Object[] data;
protected int size, head, tail; // Postcondition: this Queue object has been initialized.
public Queue() {
final int INITIAL_LENGTH = 100;
data = new Object[INITIAL_LENGTH];
size = 0;
head = 0;
tail = -1;// indicates initially empty queue
} // Postcondition: the number of elements in this Queue object has been
// returned
public int size() {
return size;
} // Postcondition: true has been returned if thie Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {
return size == 0;
} // Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: (a reference to ) the element at the front of
// this Queue object has been returned
public Object front() {
if (size == 0) {
throw new NoSuchElementException();
}
return data[head];
} // Postcondition: element has been inserted at the back of this Queue
// object. The averageTime(n) is constant, and
// worstTime(n) is O(n), but for n consecutive
// enqueues, worstTime (n) is still O(n).
public void enqueue(Object element) { if (size == data.length) {
// double the length of data
Object[] oldData = data;
data = new Object[data.length * 2]; // copy oldData[head...oldData.length-1] to
// data[0...oldData.length-1-head]
System.arraycopy(oldData, head, data, 0, oldData.length - head); if (head > 0) {
// copy oldData[0...tail] to data
// [head+1...oldData.length-1]
System.arraycopy(oldData, 0, data, head + 1, tail + 1);
}
}
tail = (tail + 1) % data.length;
size++;
data[tail] = element; } // Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be returned.
// Postcondition: the front element has been removed from this Queue object
public Object dequeue() {
if (size-- == 0) {
throw new NoSuchElementException();
}
Object element = data[head];
head = (head + 1) % data.length;
return element;
} public static void main(String[] args) {
Queue q = new Queue();
try {
q.dequeue();
} catch (NoSuchElementException e) {
System.out.println(e + " : q.size =  " + q.size());
}
q.enqueue("1");
System.out.println(q.size());
}}

Answer 4

注意我在类里加了个main方法,证明我的第二个疑问中,确实是书里面写错了,我现在已经给他改进了现在只剩下第一个问题了,希望大家能给我一个正确的写法,你只要把enqueue方法贴出来就行

Answer 5

或许人家的queue有头结点和/或尾结点，很多这种原因导致边界变动1

Answer 6

public void enqueue(Object element) { if (size == data.length) { 
// double the length of data 
Object[] oldData = data; 
data = new Object[data.length * 2]; // copy oldData[head...oldData.length-1] to 
// data[0...oldData.length-1-head] 
System.arraycopy(oldData, head, data, 0, oldData.length - head); if (head > 0) { 
// copy oldData[0...tail] to data 
// [head+1...oldData.length-1] 
System.arraycopy(oldData, 0, data, head + 1, tail + 1); 
} 
} 
tail = (tail + 1) % data.length; 
size++; 
data[tail] = element; } 下次你這樣貼代碼吧,看得人都暈了...
它的思路是這樣的
1.如果隊列滿了
  1).加長一倍
  2).由head開始到length那段數據複制至新數組
  3).若head不為0,接2)把head之前的數據複至新數組
2.將新元素放於隊尾

Answer 7

再補充一下吧,很基本的你忽略了,這個是循環隊列,若head不為0而隊又滿了,即tail的值位於head之前,所以head之前還有數據的,不過初學還是學下會滿的隊列好一點

Answer 8

我刚才debug跟踪了一下,当head=0的时候,没有错,当head不是0的时候,添加一个元素进去的时候,tail有错确实和我想象的一样,这本书确实有错误呵呵

Answer 9

现在我再把问题整理一下,第一个问题是我自己的错,我竟然漏看了两句话
原书是这样的:
public void enqueue(Object element) { if (size == data.length) {
// double the length of data
Object[] oldData = data;
data = new Object[data.length * 2]; // copy oldData[head...oldData.length-1] to
// data[0...oldData.length-1-head]
System.arraycopy(oldData, head, data, 0, oldData.length - head); if (head > 0) {
// copy oldData[0...tail] to data
// [head+1...oldData.length-1]
System.arraycopy(oldData, 0, data, head + 1, tail + 1);
}
head = 0;
tail = oldData.length - 1;
}
tail = (tail + 1) % data.length;
size++;
data[tail] = element; }我少看了这两句话:
head = 0;
tail = oldData.length - 1;其实这个方法是一点问题也没有,呵呵
现在就剩第二个问题,在dequeue()方法中的
public Object dequeue() {
if (size-- == 0) {
throw new NoSuchElementException();
}
Object element = data[head];
head = (head + 1) % data.length;
return element;
}
如果我执行下面的代码的话,Queue里明明有一个元素的,可是size打印出来却是0
public static void main(String[] args) { 
Queue q = new Queue(); 
try { 
q.dequeue(); 
} catch (NoSuchElementException e) { 
System.out.println(e + " : q.size =  " + q.size()); 
} 
q.enqueue("1"); 
System.out.println(q.size()); 
} 

Answer 10

是啊,我也觉得size--不妥

Answer 11

你发现了个小bug 应该按你的方法写