## Trending News

# 資料結構英文的小問題= =

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

### 1 Answer

- 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...