? asked in 電腦與網際網路程式設計 · 1 decade ago

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

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

Rating
  • Leslie
    Lv 7
    1 decade ago
    Favorite 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...

Still have questions? Get your answers by asking now.