User Tools

Site Tools


k7:k7.3:k7.3.2:start

7.3.2 Class Stack (gb. data)

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.

7.3.2.1 Properties

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

Property Data typeDescription
.SizeInteger (ReadOnly)Number of elements of the Stack
.IsEmptyBoolean (ReadOnly)True if there are no elements in the stack, otherwise false

Table 7.3.2.1.1: Properties of the class stack

7.3.2.2.2 Methods of a stack object

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

MethodDescription
Clear ()Remove all elements from the stack (Stack)
Push (vElement)Place an element (top) on the stack
Pop ()Remove and return the topmost element from the stack
Peek () Return of the topmost element from the stack - without removing it

Table 7.3.2.2.2.1: Methods of the class stack

7.3.2.3 Project for using 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:

Anwendung

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

Download

7.3.2 Klasse Stack (gb.data)

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.

7.3.2.1 Eigenschaften

Die Eigenschaften eines Stapels werden in der folgenden Tabelle angegeben:

Eigenschaft DatentypBeschreibung
.SizeInteger (ReadOnly)Anzahl der Elemente des Stacks
.IsEmptyBoolean (ReadOnly)Wahr, wenn keine Elemente im Stack sind, sonst falsch

Tabelle 7.3.2.1.1: Eigenschaften der Klasse Stack

7.3.2.2 Methoden eines Stack-Objektes

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

MethodeBeschreibung
Clear()Entfernen aller Elemente vom Stapel (Stack)
Push(vElement)Ein Element (oben) auf den Stack legen
Pop()Entfernen und Zurückgeben des obersten Elements vom Stapel
Peek() Rückgabe des obersten Elements vom Stapel - ohne es zu entfernen

Tabelle 7.3.2.2.1: Methoden der Klasse Stack

7.3.2.3 Projekt zum Einsatzes 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:

Anwendung

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

Download

The website uses a temporary session cookie. This technically necessary cookie is deleted when the browser is closed. You can find information on cookies in our privacy policy.
k7/k7.3/k7.3.2/start.txt · Last modified: 02.07.2018 (external edit)

Page Tools