C /C++での優先キューの紹介

優先度キューは、割り当てられた優先度に従って要素が挿入または削除されるタイプのキューです。優先度は0〜10の範囲の整数値であり、0は最も優先度の高い要素を示し、10は次の要素を示します。最も低い優先度。優先キューを実装するために従うべき2つのルールがあります-

• 優先度が最も高いデータまたは要素は、優先度が最も低いデータまたは要素の前に実行されます。
• 2つの要素の優先度が、順番に実行される要素と同じである場合、それらはリストに追加されます。

スタック、キュー、リンクリストなどの優先キューを実装するために使用できる複数のデータ構造があります。この記事では、キューのデータ構造について説明します。 -

• 単一のアレイで複数の優先度のキューを維持する

  優先キューを実装する1つの方法は、各優先度のキューを維持することです。これらの複数のキューを単一の配列に格納できます。各キューには、フロントとリアの2つのポインターがあります。キューでは、フロントポインタは要素をキューに挿入するために使用され、要素が挿入されるたびに1ずつインクリメントされ、別のポインタは、要素がキューから削除または削除されるたびに1ずつデクリメントされるキューから要素を削除するために使用されます。キューから削除されます。最後に、2つのポインターの位置から、キュー内の要素の数を判別することもできます。

• このタイプの表現では、新しい要素を挿入するためのスペースを作るためにポインターをシフトする必要があります。これにより、時間とスペースの両方の点で複雑になります。
• 単一のアレイで各優先度のキューを維持する

  このタイプのメソッドでは、要素ごとに個別の矢印を作成します。すべてのキューは循環配列として実装され、2つのポインタ変数があります。フロントとリア。優先度番号を指定した要素は、対応するキューに挿入されます。同様に、キューから要素を削除する場合は、最も優先度の高いキューの要素である必要があります。最も低い優先度の整数は、最も高い優先度（0）を示します。

注- 各キューのサイズが同じである場合、複数の1次元配列を作成する代わりに、単一の2次元配列を作成できます。

優先キューへの挿入操作のアルゴリズム

insert(queue, data, priority)
   If(queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] +1 =queue->Front[priority])
      Print Overflow
   End
   IF queue->Rear[priority - 1] = MAX-1
      Set queue->Rear[priority - 1] = 0
   Else
      Set queue->Rear[priority] = queue->Rear[priority - 1] +1
   End
      Set queue->CQueue[priority - 1] [queue->Rear[priority - 1] = data
   IF queue->Front[priority - 1] = -1
      Set queue->Front[priority - 1] = 0
End

優先キューへの挿入操作のアルゴリズム

delete(queue)
   Set flag = 0, priority = 0
      While priority <= MAX-1
         IF NOT queue->Front[priority] = -1
            Set flag = 1
            Set value = queue->CQueue[priority][queue->Front[priority]]
            IF queue->Front[priority] = queue->Rear[priority]
               Set queue->Front[priority] = queue->Rear[priority] = -1
            Else
            IF queue->Front[priority] = MAX-1
               Set queue->Front[priority] = 0
            Else
               Set queue->Front[priority] = queue->Front[priority] + 1
            End
         End
      Break
   End
   Set priority = priority +
End
If flag = 0
   Print underflow
Else
   Return value
End