Von den Grundlagen bis zur Mittelstufe: Warteschlangen, Listen und Bäume (II)
Einleitung
Im vorherigen Artikel „Von den Grundlagen bis zur Mittelstufe: Warteschlangen, Listen und Bäume (I)“ haben wir begonnen, eines der Themen zu behandeln, die viele Anfänger unterschätzen, da sie in den meisten Fällen keine ausreichenden Erklärungen zu konkreten Implementierungen oder Implementierungsmodellen erhalten. Viele Anfänger gehen einfach davon aus, dass man, um das Programmieren zu lernen, nur die Ärmel hochkrempeln und sich in Bücher und Artikel vertiefen muss. Aber in Wahrheit ist das Programmieren an sich gar nicht so schwer, denn alles, was man wissen muss, läuft darauf hinaus, ein paar Befehle und deren Syntax zu lernen.
Das mag zwar stimmen, doch die größte Herausforderung für jeden Anfänger besteht darin, zu erkennen, dass Programmieren im Grunde genommen Mathematik ist. In vielen Fällen wurde diese Mathematik bereits untersucht und in verschiedenen Mechanismen angewendet, die in allgemein zugänglichen Büchern und Artikeln ausführlich behandelt werden. Doch selbst in solchen Fällen ist es für Anfänger oft schwer zu verstehen, warum und wann sie solche Mechanismen einsetzen sollten, und so verbringen sie letztendlich viel Zeit damit, Lösungen neu zu erfinden, die es bereits gibt. Man muss lediglich bestehende Konzepte an das zu analysierende Problem anpassen.
Im vorigen Artikel haben wir begonnen, genau eines dieser Konzepte näher zu betrachten. Dies war jedoch nur der erste Schritt, der in erster Linie darauf abzielte, zu zeigen, wie Warteschlangen, Listen und Bäume mit nur minimalen allgemeinen Kenntnissen über MQL5 implementiert werden können.
Auch wenn FIFO-Warteschlangen und Ringwarteschlangen bereits vorgestellt wurden, sollten wir noch eine weitere Art von Warteschlange besprechen, um die Liste der wichtigsten Typen, die wir implementieren können, zu vervollständigen. Es ist sehr wichtig, dass Sie, lieber Leser, versuchen, die hier vorgestellten Konzepte zu verstehen. Versuchen Sie nicht, sich die Codestruktur einzuprägen, da sie von Fall zu Fall variieren kann. Das hängt natürlich von der Art des Problems ab, das Sie lösen möchten.
Wir werden also das Thema fortsetzen, das wir im vorherigen Artikel aufgegriffen haben. Dazu wenden wir uns nun einem neuen Thema zu. Man sollte bedenken, dass der hier vorgestellte Stoff in engem Zusammenhang mit dem steht, was im vorherigen Artikel behandelt wurde.
Warteschlangen, Listen und Bäume (II)
Nun, wenn Sie gerade erst mit dem Programmieren anfangen, waren Sie vermutlich etwas ratlos, wo und wie Sie das im vorherigen Artikel Behandelte anwenden sollen. Dennoch kann die Fähigkeit, das dort Besprochene und Erklärte anzuwenden, in vielen Situationen eine wichtige Rolle in Ihrer Praxis als Programmierer spielen. Aber Ihnen ist wahrscheinlich schon aufgefallen, dass sowohl eine FIFO-Warteschlange als auch eine Ringwarteschlange eines gemeinsam haben: Die Elemente darin werden immer in der Reihenfolge verarbeitet, in der sie in die Warteschlange eingefügt wurden. Mit anderen Worten: Das älteste Element wird immer zuerst gelesen, und daher wird das neueste Element in der Warteschlange immer zuletzt gelesen. Oft müssen wir diese Reihenfolge jedoch umkehren. Wir möchten also, dass das neueste Element zuerst und das älteste Element in der Warteschlange zuletzt gelesen wird.
Man könnte sogar meinen, dass es hierfür ausreichen würde, die Reihenfolge zu ändern, in der die Elemente einer FIFO-Warteschlange oder einer Ringwarteschlange ausgelesen werden. Tatsächlich ist es in manchen praktischen Situationen genau so. Es gibt jedoch eine Art von Warteschlange, die speziell dafür entwickelt wurde, dies zu ermöglichen, ohne dass bestehender Code geändert werden muss. Diese Art von Warteschlange, die speziell dazu dient, die Reihenfolge der Elemente umzukehren, wird als Stapel bezeichnet.
Ein Stapel ist, ganz wörtlich genommen, genau das, was der Name vermuten lässt. Mit anderen Worten: Wenn wir neue Elemente hinzufügen, können wir ältere Elemente nicht entfernen, ohne zuvor die neuesten zu entfernen. Es gibt sogar ein Spielzeug, das perfekt veranschaulicht, was ein Stapel ist und wo er eingesetzt werden kann. Dieses Spielzeug ist auf der folgenden Abbildung zu sehen.

Abbildung 01
Für diejenigen, die dieses Spielzeug nicht kennen: Es ist unter dem Namen „Türme von Hanoi“ bekannt. Glauben Sie mir, dieses Spielzeug wurde in der Vergangenheit bereits zur Analyse und zum Vergleich von Prozessoren verwendet. Das liegt daran, dass es Möglichkeiten gibt, damit eine gute Schätzung der Verarbeitungsgeschwindigkeit zu erhalten. Da jedoch viele Prozessoren zunehmend darauf optimiert wurden, den Algorithmus selbst zu beschleunigen, anstatt die tatsächliche Rechengeschwindigkeit der CPU widerzuspiegeln, wurde dieses Vergleichsmodell später aufgegeben. Wenn Sie versuchen möchten, das Rätsel „Türme von Hanoi“ in der Praxis zu lösen, können Sie die Website von Somatemática besuchen.
Aber was hat das mit uns zu tun? Nun, lieber Leser, wenn Sie verstehen, wie das Rätsel „Türme von Hanoi“ funktioniert, hilft Ihnen das, die Logik hinter der Implementierung eines Stapels zu begreifen. Der Stapel selbst lässt sich sehr einfach implementieren. Wo und wann man einen Stapel einsetzt, werden Sie jedoch erst durch Übung schneller und ohne Zögern erkennen. Um dies besser verständlich zu machen, nehmen wir den Code der FIFO-Warteschlange, der im vorherigen Artikel vorgestellt und erläutert wurde, als Ausgangspunkt. Der gleiche Code ist im Folgenden wiedergegeben.
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. template <typename T> struct stFIFO 05. { 06. private: 07. //+----------------+ 08. T value[]; 09. //+----------------+ 10. public: 11. //+----------------+ 12. T Restore(void) 13. { 14. T local = NULL; 15. 16. if (value.Size() > 0) 17. { 18. local = value[0]; 19. ArrayRemove(value, 0, 1); 20. }; 21. return local; 22. }; 23. //+----------------+ 24. void Stock(T arg) 25. { 26. T local[1]; 27. local[0] = arg; 28. ArrayInsert(value, local, value.Size()); 29. } 30. //+----------------+ 31. }; 32. //+------------------------------------------------------------------+ 33. void OnStart(void) 34. { 35. stFIFO <char> fifo; 36. 37. fifo.Stock(10); 38. fifo.Stock(84); 39. fifo.Stock(-6); 40. 41. Print(fifo.Restore()); 42. Print(fifo.Restore()); 43. Print(fifo.Restore()); 44. Print(fifo.Restore()); 45. } 46. //+------------------------------------------------------------------+
Code 01
Wenn Code 01 ausgeführt wird, liefert er ein Ergebnis, das wir bereits kennen und das in der folgenden Abbildung zu sehen ist:

Abbildung 02
Beachten Sie bitte: Die Namen von Funktionen und Prozeduren können Sie beliebig wählen. Bei der Implementierung eines Stapels verwenden Programmierer jedoch in der Regel bestimmte Bezeichnungen dafür. Als Erstes müssen Sie also Code 01 in die unten gezeigte Version ändern:
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. template <typename T> struct stStack 05. { 06. private: 07. //+----------------+ 08. T value[]; 09. //+----------------+ 10. public: 11. //+----------------+ 12. bool Pop(T &arg) 13. { 14. arg = NULL; 15. 16. if (value.Size() == 0) 17. return false; 18. arg = value[0]; 19. ArrayRemove(value, 0, 1); 20. return true; 21. }; 22. //+----------------+ 23. void Push(T arg) 24. { 25. T local[1]; 26. local[0] = arg; 27. ArrayInsert(value, local, value.Size()); 28. } 29. //+----------------+ 30. }; 31. //+------------------------------------------------------------------+ 32. void OnStart(void) 33. { 34. stStack <char> my; 35. 36. my.Push(10); 37. my.Push(84); 38. my.Push(-6); 39. 40. for (char info; my.Pop(info);) 41. Print(info); 42. } 43. //+------------------------------------------------------------------+
Code 02
Beachten Sie nun, dass wir von Code 01 zu Code 02 einige Änderungen vorgenommen haben. Allerdings verwenden wir auch in Code 02 weiterhin eine FIFO-Warteschlange. Wenn Sie den Code jedoch ausführen, fällt das Ergebnis etwas anders aus, wie Sie unten in Abbildung 03 sehen können:

Abbildung 03
Nun zum interessanten Teil: Beachten Sie, dass sich die Reihenfolge, in der Elemente zur Warteschlange hinzugefügt werden, nicht ändert. Wir möchten jedoch, dass die Elemente am Ende der Warteschlange – also die neuesten Elemente – zuerst gelesen und aus der Warteschlange entfernt werden, sodass die Elemente vom neuesten zum ältesten gelesen werden. Dazu müssen wir lediglich den Code in den Zeilen 18 und 19 von Code 02 ändern. Auf diese Weise wandeln wir die FIFO-Warteschlange in einen Stapel um. Beachten Sie, wie einfach sich diese Änderung vornehmen lässt. Da die Änderung, die wir vornehmen müssen, an einer ganz bestimmten Stelle erfolgt, können wir den Rest des Codes außer Acht lassen und uns ausschließlich auf diesen einen Punkt konzentrieren. Die erforderlichen Änderungen sind daher im folgenden Codeausschnitt dargestellt:
. . . 11. //+----------------+ 12. bool Pop(T &arg) 13. { 14. arg = NULL; 15. 16. if (value.Size() == 0) 17. return false; 18. arg = value[value.Size() - 1]; 19. ArrayRemove(value, value.Size() - 1, 1); 20. return true; 21. }; 22. //+----------------+ . . .
Codeausschnitt 01
„Das ist alles? Das glaube ich nicht. Ich muss sehen, was bei der Ausführung dieses Codes herauskommt.“ Nun, lieber Leser, davon können Sie sich selbst überzeugen: Die folgende Abbildung zeigt das Ergebnis im MetaTrader 5-Terminal.

Abbildung 04
Beachten Sie, dass in Abbildung 04 die Elemente in umgekehrter Reihenfolge im Vergleich zu Abbildung 03 gelesen werden. Und da wir nur die Zeilen 18 und 19 ändern und den restlichen Code unverändert lassen, bedeutet dies, dass wir die Elemente vom zuletzt zur Warteschlange hinzugefügten bis zum ältesten Element auslesen. Mit anderen Worten: Es funktioniert; das Ergebnis ist ein Stapel.
Diese Technik ist nicht auf Sonderfälle beschränkt. Der Prozessor selbst verwendet beim Aufruf von Prozeduren oder Funktionen etwas sehr Ähnliches. In diesem Fall nutzt die CPU einen reservierten Speicherbereich als Stapel. Wenn Sie nach Informationen darüber suchen, wie Anwendungen auf Prozessorebene ausgeführt werden, werden Sie auf das stoßen, was wir gerade besprochen haben. Das könnte Sie interessieren, wenn Sie besser verstehen möchten, wie ein Computer funktioniert.
„Aber jetzt habe ich eine Frage. Gibt es eine solche Implementierung, und wenn ja, wo kann sie eingesetzt werden? Verwendet eine davon das Konzept eines Stapels in einer Ringwarteschlange?“ Nun, mein lieber Leser, das ist durchaus möglich; nichts spricht dagegen. Die entscheidende Frage ist, welchen Zweck eine solche Umsetzung hätte. Denn letztendlich werden bei einer Ringwarteschlange die ältesten Elemente verworfen. Je nach dem konkreten Anwendungsfall kann es jedoch sinnvoll sein, das Konzept eines Stapels in einer Ringwarteschlange anzuwenden. Das hängt jedoch vom jeweiligen Einzelfall ab. Und da es sich hierbei um eine sehr spezielle Angelegenheit handelt, sehe ich keinen Grund, hier zu zeigen, wie man das umsetzt. Aber ich glaube nicht, dass Sie damit Probleme haben werden, gerade wegen der Ähnlichkeit zwischen einer FIFO-Warteschlange und einer Ringwarteschlange. Dies wurde im vorherigen Artikel dargelegt.
Nachdem wir nun die grundlegenden Arten von Warteschlangen besprochen haben, ist es an der Zeit, diese Warteschlangen zu etwas Komplexerem weiterzuentwickeln. Und daraus ergibt sich ein neues Konzept: Listen. Um zu verstehen, was eine Liste ist und warum sie eine Weiterentwicklung von Warteschlangen darstellt, muss man zunächst eine Sache verstehen, die einem natürlich bereits aufgefallen sein dürfte. Bei der Arbeit mit Warteschlangen können wir die Position, an der ein bestimmtes Element in der Warteschlange platziert werden soll, NICHT ändern – oder, genauer gesagt, festlegen. Eine solche Operation ist schlichtweg UNMÖGLICH. Wir können der Warteschlange lediglich ein Element oder Daten hinzufügen, ohne deren genaue Position festlegen zu können.
Hören Sie gut zu – das ist sehr wichtig. Eine Warteschlange kann als Abstraktion eines Arrays betrachtet werden, eine Liste hingegen als Weiterentwicklung dieses Konzepts. Wichtig ist jedoch Folgendes: Bei der Arbeit mit Listen geben wir nicht unbedingt einen Index an, um ein Element in die Warteschlange einzufügen, wie wir es bei der Verwendung eines Arrays tun würden. Stattdessen – das heißt, anstatt den Index anzugeben, an dem das Element in die Warteschlange eingefügt werden soll – gehen wir etwas anders vor. Und genau hier wird es kompliziert, denn vielen Anfängern fällt es schwer zu verstehen, warum wir bestimmte Dinge tun. Das Konzept bleibt zwar dasselbe, doch die konkrete Umsetzung variiert von Fall zu Fall erheblich, was letztendlich bei vielen Menschen für Verwirrung sorgt. Das gilt insbesondere, wenn wir uns das Konzept eines Baumes vor Augen führen. Aber gehen wir es langsam an. Schritt für Schritt.
Schauen wir uns zunächst einmal an, wie wir die bisher besprochenen Warteschlangen-Implementierungen so anpassen können, dass eine Liste entsteht. Mit einer Einschränkung: Es gibt zwei Arten von Listen. Eine einfach verkettete Liste und eine doppelt verkettete Liste. Der Unterschied zwischen ihnen besteht darin, wie wir die Liste durchlaufen können. Außerdem gibt es natürlich einige Unterschiede bei der Umsetzung des Codes. Aber darüber erfahren wir später mehr.
Bevor ich konkret auf Listen eingehe, muss ich noch kurz etwas anderes erläutern. Ich werde diese Erklärung sehr kurz halten, damit Sie verstehen, was wir tun werden. Wir werden uns später näher mit diesem Thema befassen. Tatsache ist, dass MQL5 DIE VERWENDUNG VON ZEIGERN AUF STRUKTUREN NICHT ERLAUBT. „Ich verstehe das nicht. Warum ist das ein Problem für uns?“ Nun, lieber Leser, das Problem ist, dass wir Zeiger verwenden müssen, um Listen korrekt zu erstellen. Und was auch immer der Grund dafür sein mag: In MQL5 ist dies mithilfe von Strukturen nicht möglich.
Das können wir jedoch mithilfe von Klassen erreichen. Allgemein gesprochen und sehr vereinfacht ausgedrückt ist eine Klasse nichts anderes als eine Struktur. Ich sage es noch einmal: Das ist nicht die beste Art, das Konzept der Klassen zu definieren oder vorzustellen. Klassen sind wesentlich komplexere Konstrukte als Strukturen. Da ich jedoch noch nicht näher auf Klassen eingehen möchte, können Sie sich Klassen vorerst – und ausschließlich für die Zwecke unserer aktuellen Implementierung – als Strukturen vorstellen. Beachten Sie jedoch, dass wir uns in Kürze genauer damit befassen werden, was eine Klasse ist.
Wenn Ihnen das klar ist, können wir mit der Liste beginnen. Um die Erklärung so einfach wie möglich zu gestalten und gleichzeitig anschaulicher zu machen, beginnen wir mit einer stark vereinfachten Umsetzung. Den entsprechenden Code finden Sie unten.
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. class stList 05. { 06. private: 07. //+----------------+ 08. int info; 09. //+----------------+ 10. public: 11. //+----------------+ 12. void Set(int arg) 13. { 14. info = arg; 15. } 16. //+----------------+ 17. int Get(void) 18. { 19. return info; 20. } 21. //+----------------+ 22. }; 23. //+------------------------------------------------------------------+ 24. void OnStart(void) 25. { 26. stList list; 27. 28. list.Set(512); 29. Print(list.Get()); 30. }; 31. //+------------------------------------------------------------------+
Code 03
Wie Sie in Code 03 sehen können, handelt es sich hierbei noch NICHT um eine Liste. Aber ich möchte, dass Sie darauf achten, was in Zeile 04 steht. Hier ersetzt das Schlüsselwort „class“ das reservierte Wort „struct“. Bis wir das Konzept einer Klasse erläutert haben, sollten Sie diesen Code daher so betrachten, als würde er eine Struktur und keine Klasse erstellen. Da das Ergebnis der Ausführung dieses Codes sehr einfach ist, werde ich nicht näher darauf eingehen. Wenn wir ihn jedoch leicht abändern, können wir einen Stapel erstellen. Ich fange lieber so an; dann verstehen Sie, worauf ich hinauswill. Okay, um Code 03 in einen Stapel umzuwandeln, müssen wir ihn wie unten gezeigt ändern:
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. template <typename T> class stList 05. { 06. private: 07. //+----------------+ 08. T info[]; 09. //+----------------+ 10. public: 11. //+----------------+ 12. void Push(T arg) 13. { 14. T loc[1]; 15. loc[0] = arg; 16. ArrayInsert(info, loc, info.Size()); 17. } 18. //+----------------+ 19. bool Pop(T &arg) 20. { 21. arg = NULL; 22. if (info.Size() == 0) 23. return false; 24. arg = value[value.Size() - 1]; 25. ArrayRemove(value, value.Size() - 1, 1); 26. 27. return true; 28. } 29. //+----------------+ 30. }; 31. //+------------------------------------------------------------------+ 32. void OnStart(void) 33. { 34. stList <char> list; 35. 36. list.Push(10); 37. list.Push(84); 38. list.Push(-6); 39. 40. for (char info; list.Pop(info);) 41. Print(info); 42. 43. }; 44. //+------------------------------------------------------------------+
Code 04
Bei der Ausführung liefert Code 04 dasselbe Ergebnis wie in Abbildung 04, da wir hier mithilfe von Codeausschnitt 01, der in diesem Artikel bereits behandelt wurde, etwas erstellt haben, das Code 02 sehr ähnlich ist. Bitte beachten Sie: Wir haben noch keine Liste erstellt, da wir in Zeile 08 weiterhin ein Array verwenden. Nun möchte ich, dass Sie bei Code 04 besonders auf eine Sache achten. Beachten Sie, was wir in den Zeilen 16 und 25 tun. In diesen Zeilen fügen wir dem Array Elemente hinzu und entfernen außerdem ein Element daraus.
Aber hier wird es erst richtig interessant: Was passiert, wenn wir das Array aus dem System entfernen? In diesem Fall sind die Zeilen 16 und 25 nicht mehr gültig, da wir nicht mehr mit dem Array arbeiten werden. Wenn wir jedoch Zeile 08 von Code 04 so ändern, dass wir einen skalaren Wert verwenden, kehren wir zu der Situation aus Code 03 zurück: Wir konnten keine Folge von Werten im Speicher ablegen und anschließend wieder abrufen. Sie haben wahrscheinlich nicht verstanden, was ich gerade gesagt habe. Also, lassen Sie uns diese Worte in Code umsetzen. Dies ist im Folgenden dargestellt:
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. template <typename T> class stList 05. { 06. private: 07. //+----------------+ 08. T info; 09. //+----------------+ 10. public: 11. //+----------------+ 12. void Push(T arg) 13. { 14. info = arg; 15. } 16. //+----------------+ 17. bool Pop(T &arg) 18. { 19. arg = info; 20. 21. return true; 22. } 23. //+----------------+ 24. }; 25. //+------------------------------------------------------------------+ 26. void OnStart(void) 27. { 28. stList <char> list; 29. 30. list.Push(10); 31. list.Push(84); 32. list.Push(-6); 33. 34. for (char info, c = 0; list.Pop(info) && c < 4; c++) 35. Print(info); 36. 37. }; 38. //+------------------------------------------------------------------+
Code 05
Wenn wir nun Code 05 ausführen, erhalten wir das in der folgenden Abbildung gezeigte Ergebnis:

Abbildung 05
In diesem Fall musste Zeile 34 in Code 05 geändert werden, um eine Endlosschleife zu vermeiden. Aber sehen Sie sich einmal an, was mit Code 05 passiert ist. In diesem Fall haben wir es mit Code zu tun, der die in den Zeilen 30 bis 32 übergebenen Werte nicht mehr speichern kann, sodass nur der letzte Wert zurückgegeben wird. Sie könnten natürlich vermuten, dass dies daran liegt, dass in Zeile 08 von Code 05 ein skalarer Wert anstelle eines Arrays verwendet wird. Und genau hier liegt der Haken – und genau hier wird der Einsatz einer Liste sinnvoll.
Wir müssen hier einen Mechanismus schaffen, der es der Variablen in Zeile 08 irgendwie ermöglicht, ihren Wert beizubehalten. Dies sollte mithilfe von Zugriffsmethoden erfolgen. Dieser Mechanismus DARF JEDOCH KEIN ARRAY VERWENDEN. Wie können wir das also anstellen? Die Antwort ist im folgenden Code zu sehen:
01. //+------------------------------------------------------------------+ 02. #property copyright "Daniel Jose" 03. //+------------------------------------------------------------------+ 04. template <typename T> class stList 05. { 06. private: 07. //+----------------+ 08. T info; 09. stList <T> *prev; 10. //+----------------+ 11. public: 12. //+----------------+ 13. stList(void) 14. :prev(NULL) 15. {} 16. //+----------------+ 17. void Push(T arg) 18. { 19. stList <T> *loc; 20. 21. loc = new stList <T>; 22. (*loc).info = arg; 23. (*loc).prev = prev; 24. prev = loc; 25. } 26. //+----------------+ 27. bool Pop(T &arg) 28. { 29. stList <T> *loc; 30. 31. if (prev == NULL) 32. return false; 33. 34. loc = prev; 35. arg = (*loc).info; 36. prev = (*loc).prev; 37. 38. delete loc; 39. 40. return true; 41. } 42. //+----------------+ 43. }; 44. //+------------------------------------------------------------------+ 45. void OnStart(void) 46. { 47. stList <char> list; 48. 49. list.Push(10); 50. list.Push(84); 51. list.Push(-6); 52. 53. for (char info; list.Pop(info);) 54. Print(info); 55. }; 56. //+------------------------------------------------------------------+
Code 06
Was Sie in Code 06 sehen, ist etwas sehr, sehr Bemerkenswertes. Gleichzeitig ist das sehr interessant, denn wenn Sie Code 06 ausführen, erhalten Sie dasselbe Ergebnis wie in Abbildung 04. Bitte beachten Sie, dass wir hier kein Array verwenden. Aber wie ist das möglich? Die Antwort lautet: Mit Code 06 wird eine sogenannte einfach verkettete Liste erstellt. Diese Liste wird jedoch nicht in vollem Umfang genutzt. Sie ist lediglich so gestaltet, dass Sie verstehen können, was wir hier tun. In diesem Artikel geht es im Wesentlichen um einen Stapel. Und da ein Stapel eine Art einfache Warteschlange ist, haben wir gewissermaßen eine einfache Liste erstellt, die jedoch dieselben Funktionen bietet wie ein implementierter Stapel.
Nun möchte ich Sie auf folgende Tatsache aufmerksam machen. Code 06 liefert dasselbe Ergebnis wie Code 04. Oder auch Code 02, allerdings mit eingebundenem Codeausschnitt 01. In diesem Fall wird der vollständige Code im Anhang zu finden sein, ebenso wie Code 06.
Aber ich möchte, dass Sie verstehen (und das könnte für Ihre Zukunft als Programmierer eine entscheidende Rolle spielen): Es spielt überhaupt keine Rolle, wie der Code intern genau umgesetzt wurde. Entscheidend ist die Schnittstelle, über die andere auf das zugreifen, was Sie programmiert haben. Dies hat enorme Auswirkungen sowohl darauf, wie Ihr Code verwendet wird, als auch darauf, welche Ergebnisse Sie erwarten können. Bitte beachten Sie, dass das Endergebnis auch dann genau dasselbe ist wie zuvor, wenn Sie einen anderen Ansatz zur Erstellung des Stapels verwenden.
Mit anderen Worten: Sie können intern eine Lösung implementieren, die auf eine bestimmte Weise funktioniert, während der Nutzer Ihres Codes gar nicht genau weiß, welchen Mechanismus Sie dabei verwenden. Das ist das Schöne am Programmieren. Sie können Dinge auf eine Weise erschaffen, die viele Menschen als absurd empfinden könnten – sei es wegen ihrer Komplexität oder wegen ihrer extremen Einfachheit. Das spielt keine Rolle; was zählt, ist das Endergebnis.
„Okay, ich glaube, ich verstehe das. Könnten Sie mir aber bitte erklären, wie Code 06 funktioniert? Ich verstehe nicht, wie Werte wie hier gezeigt gespeichert und anschließend wiederhergestellt werden können.“ Kein Problem, lieber Leser. Ich denke, Ihnen ist klar, wie die Prozedur OnStart in Zeile 45 funktioniert. Ihre Hauptfrage ist wahrscheinlich, wie genau wir es schaffen, Werte auf dem Stapel abzulegen, ohne ein Array zu verwenden, und sie später trotzdem wieder vom Stapel zu entnehmen. Um das zu verstehen, müssen Sie ein weiteres Thema verstehen, das ich hier bereits angesprochen habe, oder schon damit vertraut sein.
Hier geht es um Rekursion. Dieses Thema wurde im Artikel „Von den Grundlagen bis zur Mittelstufe: Rekursion“ behandelt. Warum ist es gerade hier wichtig, dieses Thema zu verstehen? Der Grund dafür ist, dass wir beim Erstellen einer Liste oder ihrer Basis, wie in Code 06 gezeigt, einen rekursiven Mechanismus schaffen. Dieser Mechanismus unterscheidet sich jedoch etwas von dem, der in dem oben genannten Artikel behandelt wird. Passen Sie also gut auf, damit Sie verstehen, was hier vor sich geht. Vielleicht fällt Ihnen auf, dass wir in Zeile 04 von Code 06 eine Klassenvorlage deklarieren. Vergessen Sie jetzt einmal, dass wir eine Klasse verwenden; stellen Sie sich das Ganze einfach als Struktur vor. Nun, innerhalb einer Datenstruktur können wir verschiedene Arten von Daten logisch gruppieren. In der Regel beschränken sich diese Daten auf Werte, die Sie als Programmierer bearbeiten und deklarieren können. Das ist das Grundprinzip.
Daher haben wir in Zeile 08 einen Wert, den wir als Programmierer so bearbeiten können, wie es für uns am zweckmäßigsten ist. Aber – und hier beginnt der Zauber – wir können der Datenstruktur auch noch ein weiteres Element hinzufügen. Oder mehrere Elemente, je nach Einzelfall. In unserem Fall ist dieses zusätzliche Element genau das in Zeile 09 deklarierte Element. Diese Zeile ist so etwas wie eine „magische Zeile“, und wenn Sie sie sich ansehen, werden Sie feststellen, dass wir einen Zeiger deklariert haben. Aber worauf zeigt der Zeiger? Dieser Zeiger verweist auf eine Kopie der in Zeile 04 deklarierten Struktur. „Wow, jetzt ist die Sache wirklich viel komplizierter geworden. Wie ist das möglich? Befinden wir uns in einer Struktur, die auf sich selbst verweist? Das ergibt nicht wirklich Sinn. Zumindest kommt es mir so vor.“ In gewisser Weise muss ich Ihnen zustimmen, lieber Leser. Als ich gerade erst begonnen hatte, Programmieren zu lernen, fiel es mir nicht leicht, das zu verstehen, was ich Ihnen hier zu erklären versuche.
Der springende Punkt ist, dass wir mit dem in Zeile 09 innerhalb der Struktur deklarierten Zeiger eine Rekursion innerhalb der Struktur erzeugen können, ohne die Struktur selbst zu beeinflussen. Da Sie das wahrscheinlich zum ersten Mal sehen, ergibt es für Sie vielleicht noch keinen ganz klaren Sinn. Das wird jedoch deutlich, sobald wir die Funktionalität von Code 06 erweitern, um eine verkettete Liste zu erstellen. Bevor wir das jedoch tun, müssen Sie die Konzepte verstehen, die hier erläutert werden. Andernfalls werden Sie sich nicht das nötige Wissen aneignen können, um Ihren eigenen Code zu schreiben.
Na gut, kommen wir wieder zur Erklärung zurück. Wenn wir die Prozedur in Zeile 17 verwenden, um ein Element auf dem Stapel abzulegen, beachten Sie, dass wir in Zeile 19 als Erstes etwas deklarieren, das dem in Zeile 9 Gezeigten sehr ähnlich ist. Mit anderen Worten: ein Zeiger. Hier in Zeile 19 ist dieser Zeiger jedoch lokal und temporär. Achten Sie besonders auf diesen Punkt, denn er ist wichtig. In Zeile 21 reservieren wir Speicher für den Strukturtyp, der von den in den Zeilen 09 und 19 deklarierten Zeigern verwendet wird.
Nun kommen wir zu dem Punkt, an dem viele beim Versuch, diese Listen zu verstehen, den Überblick verlieren. SPEICHERN SIE DAS NEUE ELEMENT NICHT IN DER IN ZEILE 08 DEKLARIERTEN VARIABLEN. Wir müssen das neue Element in dem von uns reservierten Speicherbereich ablegen. Denken Sie daran, dass dieser Speicherbereich genau dem entspricht, was in der Struktur deklariert ist, für die wir Speicher reserviert haben. Somit kann die Variable in Zeile 08 nun zum Speichern des neuen Elements verwendet werden. Das Wichtigste ist jedoch, was in Zeile 23 passiert. Genau in diesem Moment stellen wir eine Verbindung zwischen der aktuellen Position und der neuen Position her und bilden so eine verkettete Struktur, die in gewisser Weise einem Array ähnelt, wie später noch gezeigt wird.
Da der Zeiger nun auf das neue Element zeigt, aktualisieren wir in Zeile 24 die Struktur und stellen so sicher, dass die Elemente weiterhin miteinander verknüpft bleiben. Das ist ein wichtiges Detail. Durch Zeile 14 entfällt die Notwendigkeit, der Struktur selbst eine zusätzliche Variable hinzuzufügen. Da wir hier eine Klasse verwenden, können wir diesen Ansatz nutzen, um die Datenstruktur zu vereinfachen. Wenn wir also die Struktur initialisieren, erhalten wir das, was in der folgenden Abbildung zu sehen ist:

Abbildung 06
Hier zeigt der grüne Bereich den Inhalt an, der in der Variablen in Zeile 08 gespeichert ist. Im Gegensatz dazu zeigt der rote Bereich den Wert des in Zeile 09 deklarierten Zeigers an. Okay, das passiert, wenn Zeile 47 ausgeführt wird. Wenn nun Zeile 49 ausgeführt wird, wird die Prozedur „Push“ aufgerufen, die Sie in Zeile 17 sehen können und deren Funktionsweise ich soeben kurz beschrieben habe. Um jedoch die Funktionsweise der Prozedur „Push“ noch verständlicher zu machen, verwenden wir eine neue Abbildung. Sie ist im Folgenden zu sehen:

Abbildung 07
„Hmm, das verstehe ich nicht. Was zeigt Abbildung 07?“ Sie veranschaulicht die Bildung einer rekursiven Datenstruktur. Bitte beachten Sie, dass der Wert 10 nun im Speicher abgelegt ist, der Wert der Variablen in Zeile 09 jedoch auf den vorherigen Speicherbereich verweist. Dies wird durch den gelben Pfeil angezeigt. Nach der Ausführung von Zeile 51 erhalten wir das in der folgenden Abbildung gezeigte Ergebnis:

Abbildung 08
Bitte beachten Sie, dass der Wert, der in die Variable in Zeile 09 geschrieben wird, stets auf den zuvor reservierten Speicherbereich verweist. Dadurch entsteht eine Kette von Werten. Wenn also die Schleife in Zeile 53 beginnt, durchlaufen wir diese Struktur, die in Abbildung 08 dargestellt ist, allerdings in umgekehrter Reihenfolge. Beachten Sie, dass die Bedingung, die das Beenden der Schleife in Zeile 53 bewirkt, genau in Zeile 31 erfüllt ist. Ist diese Bedingung erfüllt, bedeutet dies, dass wir das Ende der Liste erreicht haben. Auf diese Weise können wir Daten ganz einfach vom Stapel entnehmen; dazu müssen wir lediglich den Vorgang umkehren, mit dem wir Daten auf dem Stapel ablegen.
In diesem speziellen Fall haben wir in Zeile 34 auf den Speicherbereich zugegriffen, der in Zeile 21 reserviert wurde. Das vereinfacht den Code, da wir dem Compiler auch auf andere Weise mitteilen könnten, was er tun soll. Da es hier jedoch um die Vermittlung der Grundlagen geht, habe ich beschlossen, den Code so zu belassen. Da wir nun auf den reservierten Speicherbereich zeigen, können wir in Zeile 35 auf den Wert in diesem Bereich zugreifen. In Zeile 36 aktualisieren wir den aktuellen Zeiger, sodass wir schließlich in Zeile 38 den zuvor reservierten Speicher freigeben können und damit die Schleife abschließen.
Abschließende Gedanken
Es lohnt sich, diesen Artikel eingehend zu studieren, da ich bisher nur das grundlegende Konzept vorgestellt habe, das wir zum Erstellen einer Liste benötigen. Da der Prozess der Erstellung einer Liste für Anfänger jedoch recht schwer zu verstehen sein kann, habe ich versucht, diesen Artikel so zu verfassen, dass er Ihnen eine erste Grundlage für das weitere Studium bietet. Dazu habe ich zunächst mithilfe einer Warteschlange einen Stapel erstellt und anschließend die Basis der Liste gebildet, ebenfalls unter Verwendung des Stapels. Dadurch lassen sich die grundlegenden Konzepte, die der Erstellung und Umsetzung von verketteten Listen zugrunde liegen, viel leichter verstehen, da diese in der Praxis relativ einfach zu implementieren sind. Um jedoch die Theorie und die richtige Vorgehensweise bei ihrer Erstellung zu verstehen, muss man die in diesem Artikel erläuterten Inhalte nachvollziehen können.
Ich habe versucht, alles so informativ wie möglich darzustellen, und ich glaube, dass mir das gelungen ist. Auf jeden Fall sollten Sie, lieber Leser, diese Code-Beispiele sorgfältig durcharbeiten, denn im nächsten Artikel werden wir uns etwas eingehender mit dem Thema Listen befassen. Ohne ein Verständnis dessen, was hier vorgestellt und erläutert wurde, wird es jedoch sehr schwierig sein, den Stoff zu verstehen, der im nächsten Artikel behandelt wird. Also lernen Sie fleißig, und bis zum nächsten Artikel!
| Datei | Beschreibung |
|---|---|
| Code 01 | Einfache Warteschlange |
| Code 02 | Einfache Warteschlange |
Übersetzt aus dem Portugiesischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/pt/articles/16558
Warnung: Alle Rechte sind von MetaQuotes Ltd. vorbehalten. Kopieren oder Vervielfältigen untersagt.
Dieser Artikel wurde von einem Nutzer der Website verfasst und gibt dessen persönliche Meinung wieder. MetaQuotes Ltd übernimmt keine Verantwortung für die Richtigkeit der dargestellten Informationen oder für Folgen, die sich aus der Anwendung der beschriebenen Lösungen, Strategien oder Empfehlungen ergeben.