Einführung in die Prioritätswarteschlange in C/C++

Eine Prioritätswarteschlange ist eine Warteschlange, in die Elemente basierend auf der ihnen zugewiesenen Priorität eingefügt oder entfernt werden, wobei Priorität ein ganzzahliger Wert im Bereich von 0 bis 10 ist, wobei 0 das Element mit der höchsten Priorität und 10 das Element mit darstellt Das Element mit der höchsten Priorität hat die niedrigste Priorität. Die Implementierung einer Prioritätswarteschlange folgt zwei Regeln:

• Die Daten oder Elemente mit der höchsten Priorität werden vor den Daten oder Elementen mit der niedrigsten Priorität ausgeführt.
• Wenn zwei Elemente die gleiche Priorität haben, werden sie in der Reihenfolge ausgeführt, in der sie zur Liste hinzugefügt wurden.

Es stehen verschiedene Datenstrukturen zur Verfügung, mit denen Prioritätswarteschlangen wie Stapel, Warteschlangen und verknüpfte Listen implementiert werden können. In diesem Artikel erklären wir die Datenstruktur der Warteschlange. Es gibt beispielsweise zwei Möglichkeiten, eine Prioritätswarteschlange zu implementieren:

• Verwalten Sie Warteschlangen für mehrere Prioritäten in einem einzelnen Array.

  Eine Möglichkeit, eine Prioritätswarteschlange zu implementieren, besteht darin, für jede Priorität eine Warteschlange zu verwalten. Wir können diese mehreren Warteschlangen in einem Array speichern, wobei jede Warteschlange zwei Zeiger hat, „Front“ und „Rear“. In der Warteschlange wird der vordere Zeiger zum Einfügen von Elementen in die Warteschlange verwendet und jedes Mal, wenn ein Element eingefügt wird, um 1 erhöht. Der andere Zeiger ist der hintere Zeiger, der zum Löschen oder Entfernen von Elementen aus der Warteschlange verwendet wird jedes Mal dekrementiert, wenn ein Element aus der Warteschlange entfernt wird. Schließlich können wir aus den Positionen der beiden Zeiger auch die Anzahl der Elemente in der Warteschlange bestimmen.

HINWEIS - Wenn jede Warteschlange die gleiche Größe hat, können wir statt mehrerer eindimensionaler Arrays ein zweidimensionales Array erstellen.

Algorithmus für den Einfügungsvorgang der Prioritätswarteschlange

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

Algorithmus des Einfügungsvorgangs in die Prioritätswarteschlange

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

Das obige ist der detaillierte Inhalt vonEinführung in die Prioritätswarteschlange in C/C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!