In the 2.2.2 sequential allocation section, TAOCP volume 1 , Donald Knuth mentions that F = R = 0 is for the two cases (4) and (5) of the circular queue,
but if we use (6a) and (7a), we should set F = R = 1, otherwise "overflow will not be detected when F = 0".
If I change (6a) and (7a) as follows, can the initial values of F and R also be 0?
func enqueue(X, Y) {
if R == M {
R = 0 // <- rewind to 0
} else {
R = R + 1
}
if R == F {
return error("OVERFLOW")
}
X[R] = Y
}
func dequeue(X, &Y) {
if F == R {
return error("UNDERFLOW")
}
if F == M {
F = 0 // rewind to 0
} else {
F = F + 1
}
Y = X[F]
}
It seemed that this implementation only detects whether the queue is full(OVERFLOW) or empty(UNDERFLOW) when enqueue() and dequeue() are called, so there is no need to waste the 0th element and force X[1] to be adjacent to X[M] logically, skipping X[0].
On the other hand, there is indeed a trick to reserve an element purposely to implement a circular queue. Reserving additional elements means that a circular queue with a capacity of M can only store M-1 elements; in other words, to store M elements, it is required to allocate M+1 space. The advantage of this approach is that we can determine whether the queue is full or empty without calling enqueue() and dequeue(). When F = R, the queue is empty and when F = (R+1) mod M the queue is full.
It looks like Donald Knuth didn't use this approach here, and I think there are no differences between F = R = 1 and F = R = 0, if we modify (6a) and (7a) appropriately.
