Prioritätswarteschlange
Wenn wir jedem Element eine Nummer zuweisen, um seine Priorität zu markieren, können wir genauso gut kleinere Zahlen erstellen, damit wir in einer Sammlung und Suchen auf das Element mit höchster Priorität zugreifen und es löschen können. Auf diese Weise stellen wir eine Datenstruktur wie die Prioritätswarteschlange ein. Eine vorrangige Warteschlange ist eine Sammlung von 0 oder mehr Elementen, jedes Element hat eine Priorität. Die in der Prioritätswarteschlange durchgeführten Vorgänge umfassen (1) Suchen (2) ein neues Element (3) Löschung einfügen. Im Allgemeinen wird der Suchvorgang verwendet, um das Element mit größter Priorität zu suchen, und der Löschvorgang wird zum Löschen des Elements verwendet. Für Elemente mit der gleichen Priorität können sie in erstmaliger Reihenfolge oder in einer beliebigen Priorität verarbeitet werden.
Java Array -Simulationswarteschlange
Eine Warteschlange ist eine spezielle lineare Tabelle, die nur Löschvorgänge am vorderen Ende der Tabelle und den Einfügen von Vorgängen am hinteren Ende der Tabelle ermöglicht. Das Ende, das den Einfügungsvorgang durchführt, wird als Schwanz des Teams bezeichnet, und das Ende, das den Löschvorgang durchführt, wird als Leiter des Teams bezeichnet. Dies ist das erste Prinzip (FIFO), das wir häufig verwenden. Die Liste in Java kann als Warteschlange verwendet werden. Wenn Sie am Ende der Warteschlange Elemente hinzufügen, verwenden Sie die Liste der Liste.
Java Array -Simulation Priority Warteschlangenstruktur Beispiel:
Paketdatastruktur; Import Java.util.Arrays; Java.util.comParator importieren; / *** Verwenden Sie Arrays, um die Linear-Tabellenstruktur der ersten Rang und die erste Aus-Outline-Tabelle mit hoher Priorität zu simulieren.* Ähnlich wie bei Treeset und Treemap unter Verwendung des Vergleichs*/ öffentliche Klasse SimulatePriorityQueue {public static void main (String [] args) {SimulatePriorityqueue = New SimulatePriorityQueue (4); // Simulatequeue Queue = new Simulatequeue (); // system.out.println ("das Element herausholen:" + queue.remove ()); Queue.insert (1); Queue.insert (3); Queue.insert (2); Queue.insert (5); Queue.insert (4); System.out.println ("Größe:" + queue.size ()); System.out.println ("peek:" + queue.peek ()); System.out.println ("Element ausführen:" + queue.peek ()); System.out.println ("Element ausführen:" + queue.remove ()); System.out.println ("Element ausführen:" + queue.remove ()); System.out.println ("Element extrahieren:" + queue.remove ()); // system.out.println ("Element extrahieren:" + queue.remove ()); System.out.println ("Größe:" + queue.size ()); System.out.println (); } private int msize = 3; // Größe privat int [] Marray; // Array Private int mnextItem; // nächste Position kann auch als aktuelle Anzahl der Elemente angesehen werden, die public simulatePriorityQueue () {marray = new int [msize]; mnextItem = 0; } public SimulatePriorityQueue (int Größe) {this.mize = size; marray = new int [msize]; mnextItem = 0; } / *** Element einfügen* @param item* / public void Insert (int itel) {if (! IsFling ()) {marray [mNextItem ++] = item; für (int i = 0; i <mnextItem; i ++) {// bubblestone für (int j = 0; j <mnextItem - 1; j ++) {if (marray [j]> marray [j + 1]) {marray [j] = marray [j + 1] + 0 * (marray [j + 1] = marray [j]; System.out.println (arrays.tostring (marray)); }} System.out.println (arrays.toString (marray)); } else {System.out.println ("----------------"); }} / *** Element First-In First-Out* @return* / public int remove () {if (! Isempty ()) {return marray [-mnextItem]; } else {werfen neuer illegalArgumentException ("Kein Element kann herausgenommen werden"); }} / *** Überprüfen Sie das vorherige Element* @return* / public int peek () {return marray [mnextItem - 1]; } / *** Ist es leer* @return* / public boolean isEmpty () {return mnextItem == 0; } / *** Ist es voll* @return* / public boolean isfifl () {return mnextItem == msize; } / ** * Größe * @return * / public int size () {return mnextItem; }} Ausgangsergebnis:
[1, 0, 0, 0] [1, 3, 0, 0] [1, 2, 3, 0] [1, 2, 3, 0] [1, 2, 3, 5] ----------------------------------------------------------------------------------------------------------