Queue ist wie der Stack eine Spezialisierung der Liste. Es basiert auf dem FIFO-Prinzip – First In, First Out, was bedeutet, dass der First In auch der First Out ist. Mit anderen Worten: Die „älteste“ Person in der Warteschlange verlässt die Warteschlange zuerst. Betrachten Sie zum besseren Verständnis eine Bankwarteschlange.
⚠️
Warteschlangenanwendungen: Prozessmanagement in Betriebssystemen; Kommunikation zwischen Aufgaben bei gleichzeitiger Programmierung; Computernetzwerke (Drucken); Antwort auf Anfragen auf einem Webserver
Warteschlangen selbst erlauben nur die direkte Manipulation von Daten am Ende.
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
Es ähnelt dem Verhalten einer gewöhnlichen alltäglichen Warteschlange, aber bedenken Sie nun, dass Sie in der Schlange bei einer Bank stehen und eine Dame in die Warteschlange kommt. Alle lassen ihr den Vortritt, da sie mit zunehmendem Alter eine höhere PRIORITÄT hat.
In der Datenstruktur der Prioritätswarteschlange hat jeder Knoten einen Schlüsselwert. Schlüssel ist der Schlüssel, der seine Priorität speichert, Wert ist der Wert des Knotens. Standardmäßig ist der Schlüssel in Java zunächst numerisch und kann später vom Programmierer geändert werden.
Die Menge aus Schlüssel und Wert wird als Eintrag bezeichnet, daher ändert sich die Schnittstelle dieses E.D. Weitere Details sind: Nachdem der Schlüssel definiert wurde, kann er nicht mehr geändert werden. Wenn zwei Knoten den gleichen Prioritätswert im Schlüssel haben, wählt der Programmierer die Regel.
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
In den nächsten Strukturen verwenden wir die Klassen für Knoten und Eintrag, die Attribute „erste“, „letzte“ und „Größe“ sowie „compareTo“
Die Prioritätswarteschlange ist in zwei Teile unterteilt: die sortierte (Sorted Priority Queue) und die unsortierte (Unorted Priority Queue)
Die geordnete Liste sorgt dafür, dass der Knoten an der richtigen Position eingefügt wird, sodass das Entfernen einfach ist. Entfernen Sie einfach den ersten Knoten (wenn der Programmierer, der die E.D. ausführt, festlegt, dass das Element mit der höchsten Priorität am Anfang stehen soll)
Um herauszufinden, welcher Knoten die höchste Priorität hat, verwenden wir „compareTo“, eine Sammlungsfunktion, durch deren Rückgabe wir entscheidende Ergebnisse für die Ausführung dieses E.D. erhalten können, wenn die Rückgabe ist:
Um teilnehmen zu können, müssen Sie einige Dinge überprüfen
1. Schritt → Neuen Knoten erstellen
Node newNode = new Node(key, value)
2. Schritt → Überprüfen Sie, ob die Warteschlange leer ist. Wenn ja, platzieren Sie den Kopf und den Letzten als neuen Knoten, da dies der einzige sein wird
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
3. Schritt → Wenn es nicht das einzige Element in der Liste ist, müssen Sie prüfen, ob der neue Knoten im Vergleich zum ersten eine höhere Priorität hat oder nicht.
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
3. Schritt → Anschließend mit dem letzten Element in der Liste vergleichen
Node newNode = new Node(key, value)
4. Schritt → Wenn nicht alles andere, bleibt nur noch die Mitte übrig! Dazu müssen wir einen Hilfsknoten vor dem newNode (nN) erstellen und die beiden vergleichen. Der Vergleich endet, wenn der auxNode auf nichts zeigt oder wenn nN größer als der auxNode (also größer) ist steht hinter der Reihe). Diese Zeit wird verwendet, damit der Aux herumgeht und den Wert der beiden Knoten vergleicht. Wenn er ihn findet, platziert er den nN hinter dem AuxNode
if(isEmpty()){
first = newNode;
last = newNode;
}else{
Die Entfernungsmethode in Sorted ist viel einfacher, da die Warteschlange, wie bereits erwähnt, bereits dafür organisiert ist.
1. Schritt → Da jede Remove-Methode das zu entfernende Element zurückgibt, besteht der Schritt darin, einen Eintrag zu erstellen (Warum nicht einen Knoten?)
if(compare(newNode, first)<0){
//Se o nN for menor que o F
//Levando em consideração que a prioridade maior é 0
//Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
newNode.next = first;
first.previous = newNode;
first = newNode;
}
2. Schritt → Da Sie dann bereits dabei sind, den ersten Knoten zu entfernen, zeigen Sie einfach mit „Erster“ auf den Knoten neben „Erster“
}else if(compare(newNode, last)>=0){
//Se o nN for maior que o L
//Significa que o número de nN é maior que L
//Então bota o nN para ultimo
newNode.previous=last;
last.next=newNode;
last = newNode;
}else{
3. Schritt → Überprüfen Sie, ob sich nur ein Element in der Warteschlange befindet, denn wenn ja, ist die Warteschlange leer! Dann müssen Sie F und L auf Null setzen
}else{
//se nao for nada, está no meio
//entao temos que achar entre qual dos meios
Node auxNode = first;
while(compare(newNode, auxNode)>0 && auxNode.next!=null){
//enquanto o newNode tiver prioridade maior que o auxiliar
//e o auxiliar tiver um proximo
auxNode = auxNode.next;
}
newNode.next = auxNode;
newNode.previous = auxNode.previous;
}
}
4. Schritt → Wenn es nicht das einzige Element ist, bedeutet das, dass es noch andere gibt! Wenn Sie also in Schritt 2 das erste Element entfernen, ist das, was zuvor „Erstes“ war, immer noch vorhanden und wird durch das vorherige verbunden. Daher müssen wir Folgendes tun:
Entry<K,V> max = maxPriority();
Methode, die das Element mit der höchsten Priorität in der Liste zurückgibt, und da wir in der richtigen Reihenfolge sind, gibt sie nur das erste zurück.
first = first.next;
| Método | O(_) |
|---|---|
| size | O(1) |
| isEmpty | O(1) |
| insert | O(n) |
| remove | O(1) |
| maxPriority | O(1) |
Die ungeordnete Warteschlange unterscheidet sich stark von der geordneten! Beginnen wir mit seinen Methoden:
Um Unsorted, Like und Disordered hinzuzufügen, müssen Sie sich keine Gedanken darüber machen, wo dieses neue Element sein wird. Fügen Sie es einfach am Ende hinzu!
1. Schritt → Überprüfen Sie, ob die Liste leer ist, denn wenn ja, ist der hinzuzufügende Knoten der erste (First) und der letzte (Last)
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
2. Schritt → Wenn es nicht leer ist, kümmern Sie sich einfach darum, diesen Knoten am Ende hinzuzufügen!
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
Das Entfernen in Unsorted ist viel komplexer als die dürftigen Codezeilen in Sorted…
„Warum?“ Sie fragen, wir sollten eine Methode (die in der anderen Version auch viel einfacher war) namens maxPriority verwenden, deren Ziel es ist, den Knoten mit der höchsten Priorität zu finden. Früher wurde es auf einfache Weise mit nur wenigen Codezeilen beigebracht. Da wir jetzt nicht wissen, wo sich dieser Knoten mit der höchsten Priorität tatsächlich befindet, müssen wir die gesamte Warteschlange auf der Suche nach ihm durchgehen! Bevor wir uns also das Entfernen selbst ansehen, werfen wir einen Blick auf maxPriority.
1. Schritt → Wann immer wir eine Datenstruktur durchlaufen möchten, benötigen wir zwei Knoten: einen Hilfsknoten, um immer voranzukommen, und den Knoten, den wir erreichen möchten (in diesem Fall MaxPriority)
Node newNode = new Node(key, value)
2. Schritt → Diese beiden werden innerhalb eines Knotens ausgeführt, sie enden erst, wenn der Aux Null erreicht (Ende der Warteschlange). Vergleichen Sie diese Knoten. Wenn er negativ ist, bedeutet dies, dass Aux kleiner als Max ist, sodass Max der größte ist. Aktualisieren Sie den Wert des Max-Knotens und lassen Sie Aux dann laufen.
if(isEmpty()){
first = newNode;
last = newNode;
}else{
1. Schritt → Erstellen Sie in allen Emoves eine Variable, die den Knoten speichert, der entfernt werden soll. In diesem Fall wissen Sie bereits, welche entfernt wird, da Sie die Methode maxPriority
aufrufen
if(compare(newNode, first)<0){
//Se o nN for menor que o F
//Levando em consideração que a prioridade maior é 0
//Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
newNode.next = first;
first.previous = newNode;
first = newNode;
}
2. Schritt → Dann prüfen Sie, ob es das einzige Element ist. Wenn ja, sind F und L Nullen!
}else if(compare(newNode, last)>=0){
//Se o nN for maior que o L
//Significa que o número de nN é maior que L
//Então bota o nN para ultimo
newNode.previous=last;
last.next=newNode;
last = newNode;
}else{
3. Schritt → Wenn es nicht der einzige ist, gibt es andere Möglichkeiten: Wenn das Maximum das letzte ist, eliminiere das letzte, wenn es das erste ist, eliminiere das erste, wenn es weder zwei noch zwei ist, ist es drin die Mitte!
}else{
//se nao for nada, está no meio
//entao temos que achar entre qual dos meios
Node auxNode = first;
while(compare(newNode, auxNode)>0 && auxNode.next!=null){
//enquanto o newNode tiver prioridade maior que o auxiliar
//e o auxiliar tiver um proximo
auxNode = auxNode.next;
}
newNode.next = auxNode;
newNode.previous = auxNode.previous;
}
}
4. Schritt → Wenn es sich in der Mitte befindet, muss das Maximum, das sich in der Menge befindet, entfernt werden. Dies geschieht, wenn niemand sonst darauf zeigt.
Entry<K,V> max = maxPriority();
| Método | O(_) |
|---|---|
| size | O(1) |
| isEmpty | O(1) |
| insert | O(1) |
| remove | O(n) |
| maxPriority | O(n) |
Das obige ist der detaillierte Inhalt vonPrioritätswarteschlange! Lassen Sie es uns aufschlüsseln und mehr über diesen Teil der Datenstruktur erfahren.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
