Java Queue 的 isFull 方法实现不带 nitems 字段

Question

我正在阅读一本 Java 算法书。实现队列的方法之一是不使用 nitems 字段来检查队列是空还是满。以下是我正在尝试解决的方法。我尝试通过在白板上绘制数组等来理解这一点，但没有明确的理解。

你们中的任何人都可以解释一下下面的代码吗？感谢您花时间查看此内容。

public boolean isFull() // true if queue is full
{
return ( rear+2==front || (front+maxSize-2==rear) );
}

附加说明:

在这种没有 nelem 的队列实现方式中，数组的大小(即“maxSize”)是(queuesize+1)，例如对于 5 个元素的队列大小，maxSize 将为 6。额外的数组元素用于解决队列同时显示为空和满的情况。

其中“rear”字段是数组上的位置，当新元素插入队列时，它会更新，因为队列是 FIFO 的。 “插入新元素时，前面不会更新。

“front”字段是队列中第一个元素的位置，即调用删除方法时将从队列中弹出的元素。

下面是书中的完整算法，以防我的解释不清楚。我想我理解了 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);
}
//--------------------------------------------------------------
} //

谢谢!
拉古

Answer 1

可视化此实现的最佳方法是写下一个测试用例并查看它。假设我们有一个 4 人的队列:

• 前面=0
• 后=-1
• s=4
• 最大尺寸=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() 你会看到条件 front+maxSize-2==rear 为真: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

  这时候我们终于结束了——rear在front后面，队列中有四个元素!现在看到 isFull() 的另一个条件存在:rear+2==front as 0+2==2。

我希望这有助于说明该解决方案如何工作，而无需实际保留元素计数。