Question

java中，实现一个循环队列，其中的边界条件有些弄不明白，请看我的代码：

循环队列：当遇到内部的数组结尾时，get和put索引将会自动返回到起点，这样，任何数目的元素都能够存储在一个循环队列中。
class CircularQueue implements ICharQ {
private char q[];
private int putloc,getloc;
public CircularQueue(int size) {
q=new char[size+1];//注意：这里数组长度加 1。
putloc=getloc=0;
}
public void put(char ch) {
if(putloc+1==getloc | ((putloc==q.length-1) & (getloc==0))) { //第一个边界条件想不清楚，为什么putloc+1==getloc 就能判断队列是满的，第二个边界条件也帮我解释一下，谢谢啦。
System.out.println("--Queue is full.");
return;
}
putloc++;
if(putloc==q.length) putloc=0;
q[putloc]=ch;
}
public char get() {
if(getloc==putloc) {
System.out.println("--Queue is empty.");
return (char)0;
}
getloc++;
if(getloc==q.length) getloc=0;
return q[getloc];
}
}

Answer 1

//我做了一个测试类，你运行一下试试吧
//问题的关键在于这个类的设计似乎是，假设size是3，但是数组的size是4
//putloc是0,但是put的位置在数组中是1
//总觉得这个类的设计很怪，既然size是3，底层实现也做成3就好了。

import java.util.Arrays;

public class CircularQueue {
private char q[];
private int putloc, getloc;

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue(3);
circularQueue.put('1');
circularQueue.put('1');
circularQueue.put('1');
circularQueue.put('1');
}

private void paint(String s) {
System.out.println(s + ": putloc=" + putloc + " getloc=" + getloc + " "
+ Arrays.toString(q));
}

public CircularQueue(int size) {
q = new char[size + 1];// 注意：这里数组长度加 1。
putloc = getloc = 0;
paint("create!");
System.out.println();
}

public void put(char ch) {
paint("before put");
if (putloc + 1 == getloc | ((putloc == q.length - 1) & (getloc == 0))) { // 第一个边界条件想不清楚，为什么putloc+1==getloc
System.out.println("--Queue is full.");
return;
}
putloc++;
if (putloc == q.length)
putloc = 0;
q[putloc] = ch;
paint("after put");
System.out.println();
}

public char get() {
paint("before get");
if (getloc == putloc) {
System.out.println("--Queue is empty.");
return (char) 0;
}
getloc++;
if (getloc == q.length)
getloc = 0;
paint("after get");
System.out.println();
return q[getloc];
}
}

追问

由这个代码： putloc++；q[putloc]=ch;
因为putloc已经自加1了，那q[putloc]就是q[1]开始了，没有用q[0]，循环之后，就是一直到q[9]，只有9个数了，我知道自己理解错了，但想不清楚。谢谢你啦。

追答

//我也稍微写了一下程序，发现确实用size+1，可以省下一个变量。不过如果加一个num变量表示现在队列中有几个数据，然后用num判断是否可写可读会更明了。

public class CircularQueue {

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue(3);
circularQueue.put('1');
circularQueue.put('2');
circularQueue.put('3');
circularQueue.put('4');
System.out.println(circularQueue.get());
System.out.println(circularQueue.get());
System.out.println(circularQueue.get());
System.out.println(circularQueue.get());
circularQueue.put('5');
System.out.println(circularQueue.get());
}

private char[] chars;
private int putIndex;
private int getIndex;
private int num;
private int size;

public CircularQueue(int size) {
this.chars = new char[size];
this.putIndex = 0;
this.getIndex = 0;
this.num = 0;
this.size = size;
}

public void put(char c) {
if (num 0) {
c = chars[getIndex];
getIndex++;
if (getIndex == chars.length) {
getIndex = 0;
}
num--;
} else {
System.out.println("can't get");
}
return c;
}

}

Answer 2

putloc算是起点,getloc算是终点.如果起点不断的自加也就是向后移,直到下一个元素就要与终点重合了,那么是不是就算是满了呢?也就是putloc+1==getloc.就像你往杯子里倒水,你马上要倒满了,此时你脑袋里面判断,我再倒一点就会满了.
第二个条件是与的关系.当你的起点跟你的数组长度减少1相同的时候并且你的终点回0了,也算是满.这里要解释一下数组的下标都是从0开始的,而这是循环队列.也就是说如果终点到了队列末尾,那么起点可以一直向末尾进发,如果终点到了0,那么起点也会经过末尾回到0.此时判断的方法就不再是putloc+1==getloc了,因为终点已经回0了,起点再+1就是超出数组长度的而不是开始的那个0了.这个其实跟第一个的道理是一样的.所以说先判断putloc==q.length-1也就是起点是否是数组的末尾,我也说过了数组下标从0开始,因此10个元素的数组下标只到9也就是q.length-1.后面就是判断终点是否回0了也就是getloc==0.
这就是把一个数组首尾相接看成一个圆,只不过到了末尾跟开始连接的地方算数要改变,毕竟下标不能看成圆,是多少还是多少的.

追问

由这个代码： putloc++；q[putloc]=ch;
因为putloc已经自加1了，那q[putloc]就是q[1]开始了，没有用q[0]，循环之后，就是一直到q[9]，只有9个数了，我知道自己理解错了，但想不清楚。谢谢你啦。

追答

没错,在进方法的时候,putloc跟getloc都是0.而0似乎是这个数组保留的一个下标.q=new char[size+1];//注意：这里数组长度加 1。在这一步的时候把数组的长度+1了.而你后面所做的就是把0这个数带进方法来判断,然后再从1开始放.如果到了末尾,又会回0,然后又用0来判断,又会+1来放.0这个下标在数组中应该不是用来放数据的,只是作为一个起点来衔接首尾的.