我正在浏览Java算法书籍。实现队列的一种方法之一是使用NITEMS字段，以检查队列是空还是完整。以下是我试图缠绕头的方法。我试图通过在白板上绘制阵列等来理解这一点。
你们中的任何一个都可以在下面的代码上阐明一些启示吗？感谢您抽出宝贵的时间来看看这个。
public boolean isFull() // true if queue is full
{
return ( rear+2==front || (front+maxSize-2==rear) );
}
其他注释：
在具有带有nelems的队列的这种实现方式中，数组的大小，即" maxsize"是（排队 1），例如。对于5个元素的队列尺寸，最大尺寸为6。其他数组元素用于解析队列似乎是空的，同时又满了。
其中"后方"字段是阵列上的位置，并且在队列为FIFO时将新元素插入队列时会更新。"插入新元素时不会更新前面。
" front"字段是队列中第一个元素的位置，即在调用remove方法时会弹出的元素。
以下是本书中的完整算法，以防我的解释不清楚。我认为我了解ISEMPTY方法，但是Isfull方法对我来说并不清楚。
class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
//--------------------------------------------------------------
public Queue(int s) // constructor
{
maxSize = s+1; // array is 1 cell larger
queArray = new long[maxSize]; // than requested
front = 0;
rear = -1;
}
//--------------------------------------------------------------
public void insert(long j) // put item at rear of queue
{
if(rear == maxSize-1)
rear = -1;
queArray[++rear] = j;
}
//--------------------------------------------------------------
public long remove() // take item from front of queue
{
long temp = queArray[front++];
if(front == maxSize)
front = 0;
return temp;
}
//--------------------------------------------------------------
public long peek() // peek at front of queue
{
return queArray[front];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return ( rear+1==front || (front+maxSize-1==rear) );
}
//--------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return ( rear+2==front || (front+maxSize-2==rear) );
}
//--------------------------------------------------------------
public int size() // (assumes queue not empty)
{
if(rear >= front) // contiguous sequence
return rear-front+1;
else // broken sequence
return (maxSize-front) + (rear+1);
}
//--------------------------------------------------------------
} //
谢谢！
raghu
可视化此实现的最佳方法是写下测试用例并查看它。假设我们的队列为4：
- 前= 0
- 后= -1
- s = 4
- maxsize = 5
- Quearray是一个带有索引0到4的数组。
由于此实现是阵列的包裹，因此您可以在后方或前方前方的索引中进行后方。这就是为什么Isempty（）和Isfull（）都有两个案例的原因。我将以两个示例进行演示 - 一个我们用4个插入物填充数组，另一个插入2个插入物，1个删除，3个插入物，1个删除和1个插入物。令q为quearray，r为后方，f是前面：
-
q = [0,0,0,0,0] f = 0 r = -1
这是起始位置。在这一点上，在插入之前，队列为空 - 您可以使用ISEMPTY（）和后部 1 ==前部有效，因为-1 1 ==0。
-
q = [5,0,0,0,0] f = 0 r = 0
第一个插入物将后部最大为0。
-
q = [5,4,0,0,0] f = 0 r = 1
第二插入将后部带到1。
-
q = [5,4,3,0,0] f = 0 r = 2
- q = [5,4,3,2,0] f = 0 r = 3
请注意，在这一点上，队列已满 - 它包含4个元素。呼叫isfull（）您会看到条件前 maxsize-2 ==后方是正确的：0 5-2 == 3。
现在，让我们尝试包裹的方法，后部到达前后的索引。让我们从第二个插件开始：
-
q = [5,4,0,0,0] f = 0 r = 1
-
q = [0,4,0,0,0] f = 1 r = 1
第一个删除。为了示例，我实际上将" 5"从数组中删除到" 0" - 实际上并未在此实现中发生，" 5"在那里，但会在需要时被覆盖。但是为了可视化是有效的。
-
q = [0,4,3,0,0] f = 1 r = 2
- q = [0,4,3,2,0] f = 1 r = 3
- q = [0,4,3,2,1] f = 1 r = 4
- q = [0,0,3,2,1] f = 2 r = 4
-
q = [5,0,3,2,1] f = 2 r = 0
此刻我们终于包裹了 - 后方在前后，我们在队列中有四个元素！现在查看Isfull（）的另一个条件是：后 2 ==正面为0 2 == 2。
我希望这有助于说明解决方案的工作原理，而无需实际计算元素。