1

大学では、教授から循環キューを実装するアルゴリズムを考案するように依頼されました。「remove()」および「insert()」関数のアルゴリズムを作成する必要があります。これは私が何時間も考えた後に思いついたものです。

Declarations: q = circular queue structure that contains 3 elements 
                --> x[MAX] = array of MAX integers
                --> rear = logical pointer used for inserting elements at that particular index
                --> front = logical pointer used for deleting elements at that particular index
Predefined functions:
                --> incr (int y) : special function to set y to 0 once it contains MAX else do y++
                --> decr (int y) : special function to set y to MAX if it contains 0 else do y--

Preconditions : At the initial time of defining the structure set rear and front both at 0

Algorithm REMOVE(q): Returns an int
1.  set a <- q.x[q.front]
2.  incr (q.front) 
3.  if q.front >= q.rear 
    1.  decr (q.front)
    2.  print "Queue Empty"
    else
    1. return a

Algorithm INSERT(q,a) : Returns nothing
1.  incr (q.rear)
2.  if q.rear = q.front
    1.  decr (q.rear)
    2.  print "Queue Full"
    else
    1.  set q.x[q.rear] <- a

このアルゴリズムは、「前」が「後」を決して追い越さないという事実を利用しています。したがって、「前 = 後」がキューが空であることを意味する場合、「前」を増やすと。そして、'rear = front' がキューがいっぱいであることを意味する場合、'rear' を増やします。

しかし、私がこれを教授に見せたところ、彼はこれは解決策ではないと言いました.

このロジックは間違っていますか？もしそうなら、このアルゴリズムの欠陥は何ですか? また、可能であれば改善策を提案してください。

(PS: Google で解決策を調べていないのは、これを自分で実装したいからです。)

4

1 に答える 1

0

キューの初期化後の最初の操作が REMOVE 要求である場合、セットアップは失敗します。この理由は、最初にフロント インデックスをインクリメントしてから、それがリア インデックスと等しいかどうかをチェックして、キューが空か満杯かを検出するためです。ただし、初期化後、キューが空である間は両方のインデックスがすでに等しくなっています。

于 2013-08-24T06:14:05.240 に答える