C/C++ のプライオリティ キューの概要

優先キューは、割り当てられた優先順位に従って要素が挿入または削除されるキューです。優先順位は 0 ～ 10 の範囲の整数値です。0 は最も高い優先順位を持つ要素を表し、10 は優先順位が最も高い要素を表します。優先度が最も高い要素と優先度が最も低い要素です。優先キューの実装は、次の 2 つのルールに従います。

• 最も高い優先順位を持つデータまたは要素は、最も低い優先順位を持つデータまたは要素よりも前に実行されます。
• 2 つの要素の優先順位が同じ場合、リストに追加された順序で実行されます。

スタック、キュー、リンク リストなど、優先キューの実装に使用できるさまざまなデータ構造が用意されています。今回はキューのデータ構造について解説します。優先キューを実装するために使用できる方法は 2 つあります。たとえば、次のとおりです。

• 単一の配列で複数の優先キューを維持する

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

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

プライオリティキュー挿入動作アルゴリズム

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

以上がC/C++ のプライオリティ キューの概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。