If a circular queue is impleemented by an array q of size m,emplain why the array q is permitted to hold an most m-1 elements
- LeslieLv 71 decade agoFavorite Answer
Let the array size be m, with index 0 to m-1.
Suppose F points to the position before the first element, and
R points to the last element.
When adding an element, R becomes R+1 (mod m).
When deleting an element, F becomes F+1 (mode m).
The problem is: when F=R, the queue may be either
full (R catches F) or empty (F catches R), and so
testing either full or empty (we need the test when
adding or deleting an element) may fail.
The solution is to make the full condition as:
R+1 (mod m) = F, and in this case the number of elements
is m-1. (The empty condition is still F=R).
其實, 這題目並不好, 我們只要利用多一個變數, 就可讓此 queue 可含 m 個元素, 也避開 "滿或空" 的問題. (見 http://en.wikipedia.org/wiki/Circular_queue#Diffic...