GAMBAS BOOK 3.14

The Stack class implements a stack of elements. This class uses the data type Variant for its elements.

A stack is a data structure that functions according to the LIFO principle. The principle “Last in, first out” describes abstractly what can be imagined, for example, as a stack of paper in a box. If you want to add a sheet of paper to the stack, you have to place it on top of the stack. The effort to lift parts of the stack to place the paper anywhere is simply too great. For this reason, it is also possible to remove only the topmost sheet of paper from the pile. The last added element is the first removed element (LIFO). In this sense, the stack is a data structure opposite the queue. The last element of a stack is also referred to as its topmost element. It is characteristic for the stack that it is only possible to operate at the top of the data structure - add and remove elements.

The properties of a stack are shown in the following table:

Table 7.3.2.1.1: Properties of the class stack

With these 4 methods, a stack can be used as a data structure according to the LIFO principle:

Table 7.3.2.2.2.1: Methods of the class stack

The Gambas interpreter also manages a stack on which all function calls are logged. This information can prove invaluable in the event of a bug in the IDE, for example in case of a program crash, to identify and fix the bug. You can better understand how the error occurred.

The stack of the Stack class in the project stores all functions that were called in the current code path. A code path is a chain of function calls. The associated stack is also called a “Call trace” or “Backtrace”. A backtrace is created using the following simple algorithm:

• First, when entering a function, an entry for this function is pushed onto the backtrace stack? push (vElement),
• then the function is executed and
• finally the information has to be removed from the stack when leaving the function? pop ().

A function that calls another function gets the stack back in the state it was before the function call. However, if a program error occurs in a nested function, the backtrace stack can be examined. Then all functions can be identified that were called in the error-creating code path because their stack elements could not yet be removed. The most recently called function, which causes the error directly, is therefore always the topmost element of the backtrace stack.

A backtrace is a classic example of a stack. In the project for the stack class, such a backtrace is created:

Figure 7.3.2.3.1: Backtrace of the application program (blue) and the interpreter (red) in case of a runtime error

In addition to backtraces, stacks are also used for the implementation of parsers:? http://de.wikipedia.org/wiki/Umgekehrte_Polish_notation

Die Klasse Stack implementiert einen Stapel von Elementen. Diese Klasse verwendet den Datentyp Variant für seine Elemente.

Ein Stack oder Stapel ist eine Datenstruktur, die nach dem LIFO-Prinzip funktioniert. Das Prinzip “Last in, first out” beschreibt abstrakt, was man sich bildhaft zum Beispiel als Papierstapel in einer Box vorstellen kann. Wenn man dem Stapel ein Blatt Papier hinzufügen möchte, so muss man es oben auf den Stapel legen. Der Aufwand, Teile des Stapels hoch zu heben, um das Papier an eine beliebige Stelle zu legen, ist einfach zu groß. Aus diesem Grund kann man auch nur das oberste Blatt Papier des Stapels wieder entfernen. Das letzte hinzugefügte Element ist also das zuerst wieder entfernte (LIFO). In diesem Sinne ist der Stack eine der Queue entgegengesetzte Datenstruktur. Das letzte Element eines Stacks wird auch als dessen oberstes Element bezeichnet. Für den Stack ist es charakteristisch, dass man nur am oberen Ende der Datenstruktur operieren kann – Elemente hinzufügen und wieder entfernen.

Die Eigenschaften eines Stapels werden in der folgenden Tabelle angegeben:

Tabelle 7.3.2.1.1: Eigenschaften der Klasse Stack

Mit diesen 4 Methoden kommt ein Stack als Datenstruktur nach dem LIFO-Prinzip aus:

Tabelle 7.3.2.2.1: Methoden der Klasse Stack

Der Gambas-Interpreter verwaltet ebenfalls einen Stack, auf dem u.a. alle Funktionsaufrufe protokolliert werden. Diese Informationen können sich im Fehlerfall in der IDE, zum Beispiel bei einem Programmabsturz, als unschätzbar wichtig zur Identifikation und Beseitigung des Programmfehlers herausstellen. Sie können besser nachvollziehen, wie es zu dem Fehler kam.

Auf dem Stapel der Klasse Stack im Projekt werden alle Funktionen gespeichert, die im aktuellen Code-Pfad aufgerufen wurden. Ein Code-Pfad ist eine Verkettung von Funktionsaufrufen. Der zugehörige Stack wird auch als “Call trace” oder “Backtrace” bezeichnet. Ein Backtrace wird über den folgenden einfachen Algorithmus erstellt:

• Zuerst wird beim Eintritt in eine Funktion ein Eintrag für diese Funktion auf den Backtrace-Stack geschoben → Push(vElement),
• dann wird die Funktion ausgeführt und
• abschließend müssen die Informationen beim Austritt aus der Funktion wieder vom Stack entfernt werden → Pop().

Eine Funktion, die eine andere Funktion aufruft, bekommt den Stack in dem Zustand zurück, wie er vor dem Funktionsaufruf war. Sollte allerdings in einer verschachtelten Funktion ein Programmfehler auftreten, so kann der Backtrace-Stack untersucht werden. Dann können alle Funktionen identifiziert werden, die im Fehler erzeugenden Code-Pfad aufgerufen wurden, da ihre Stack-Elemente noch nicht wieder entfernt werden konnten. Die zuletzt aufgerufene, den Fehler direkt verursachende Funktion, ist somit immer das oberste Element des Backtrace-Stacks.

Ein Backtrace ist ein klassisches Beispiel für einen Stack. Im Projekt für die Stack-Klasse wird ein solcher Backtrace erzeugt:

Abbildung 7.3.2.3.1: Backtrace des Anwendungsprogramms (blau) und des Interpreters (rot) bei einem Laufzeitfehler

Neben Backtraces finden Stacks auch Anwendung bei der Implementierung von Parsern: → http://de.wikipedia.org/wiki/Umgekehrte_Polnische_Notation