Datenstrukturen und Algorithmen sind sehr eng miteinander verbunden. Einige Datenstrukturen treten so haeufig in Algorithmen auf, dass man sie als elementar bezeichnen kann. Felder, Stapel und Schlangen oder verkettete Listen sind von wesentlicher Bedeutung fuer die Programmierung. Im Folgenden werden Sie deshalb diese Datenstrukturen naeher kennenlernen.
Eine sehr wichtige Datenstruktur, die in den meisten Programmiersprachen schon als grundlegender Datentyp zur Verfuegung steht sind Felder. Ein Feld ist eine Folge von gleichen Datentypen, die zusammenhaengend gespeichert werden. Die einzelnen Elemente dieses Feldes werden ueber Indizes angesprochen. Das Feld wird haeufig auch als Vektor oder Array bezeichnet. Wir kennen diese Datenstruktur aus dem Kapitel Arrays.
Das Arbeiten mit Feldern soll das folgende Beispiel verdeutlichen. Es wird ein Feld zur Aufnahme von 10 Strings angelegt. Anschliessend werden Zeichenketten in dieses Feld eingelesen. Nachdem das Array gefuellt ist, werden die einzelnen Strings wieder ausgelesen und ausgegeben.
#include#define ZEILENZAHL 10 #define ZEILENLAENGE 80 int main() { char text[10][80]; char (*zeile)[80]; int i; zeile=text; printf("Bitte geben Sie nun %d Zeilen Text ein:\n",ZEILENZAHL); fflush(stdin); for(i=0;i<10;i++){ printf("%d >> ",i); gets(text[i]); } printf("Ihr Text war der folgende:\n"); while(zeile < ( char (*)[80] ) text[ZEILENZAHL]) printf("%s\n",zeile++); printf("Und einmal zurueck\n"); while(zeile > text) printf("%s\n",--zeile); return(0); }
#includeint main() { char s1[80],s2[80],s3[80]; char *array[3]; int i; array[0] = s1; array[1] = s2; array[2] = s3; for(i=0;i<3;i++){ printf("Ein Satz: "); gets(array[i]); } printf("Wenn Sie eine 0 eingeben, endet das Programm! \n"); while((i = getchar() - '0')!=0){ printf("Satz %d : %s\n",i,array[i]); fflush(stdin); } return(0); }
Die Stapel sind eine besondere Form, Daten zu sortieren. Man stelle
sich einen Stapel Blaetter vor, die auf dem Schreibtisch liegen. Um an
das unterste Blatt heranzukommen, muss ich schon alle anderen Blaetter
vorher wegnehmen.-
Der Stapel in der Informationstechnik findet sich z.Bsp. im
Hauptspeicher des Rechners. Z.Bsp. Ruecksprungadressen von
Funktionen werden hier abgelegt und auch der Reihe nach wieder
heruntergenommen. Last in, First out. lifo-Prinzip. Im hier zu
besprechenden Beispiel wollen wir einen mathematischen Ausdruck
berechnen. In normaler Schreibweise (Infix-Notation) wuerde man
sagen:
5*4+3 (5*(4+3))
in der Praefix-Notation, sieht das
folgendermassen aus:
+*543 (*5+43) und in der Postfix-Schreibweise:
543+* (54+3*)
Die Berechnung eines Postfix-Ausdrucks kann leicht mit einem Programm
realisiert werden, das sich eines Stapel-Alogerithmuses bedient.
_________________________________________________________________
| n = 1 |
_________________________________________________________________
| Solange n <= Laenge des Strings Postfix |
| _______________________________________________________________
| | Postfix ist |
| |-------------------------------------------------------------|
| | eine | ein | |
| | Ziffer | Operator | sonstiges |
| |______________________________________________________________
| | Zifferfolge lesen | Operanden A und B | / |
| | und Zahl | vom Stapel holen | / |
| | zusammenfuegen | | / |
| |______________________________________________________________
| | Zahl auf den | Operator auf A | / |
| | Stapel legen | und B anwenden | / |
| | |_______________________| |
| | | Ergebnis auf den | |
| | | Stapel legen | |
|________________________________________________________________
| Ergebnis vom Stapel nehmen |
_________________________________________________________________
_________________________________________________________________
Stapel Postfix-Term Operation
_________________________________________________________________
45*67*+ 4 auf den Stapel legen
4 5*67*+ 5 auf den Stapel legen
5,4 *67*+ Die beiden obersten Werte vom
Stapel nehmen und per *
verknuepfen (4*5) und das Ergebnis
20 auf den Stapel legen.
20 67*+ 6 auf den Stapel legen
6,20 7*+ 7 auf den Stapel legen
7,6,20 *+ Die beiden obersten Werte vom
Stapel nehmen und per * (7*6)
verknuepfen und das Ergebnis 42
auf den Stapel legen.
42,20 + Die beiden obersten Werte vom
Stapel nehmen und per +
verknuepfen und das Ergebnis auf
den Stapel legen.
62 Ergebnis vom Stapel nehmen.
__________________________________________________________________
#include#include char postfix[20],c; // Eine Zeichenkette int n,m,x,tos,stack[20]; //Auf den Stapel werden nur Zahlen gelegt // Umwandeln eines Zeichens in eine int-Zahl (Zeichen - '0') liefert das int atoi(char c) { int i; i= c - '0'; return i; } void init_stack() { tos=0; } void push(x) if(tos == 200) { printf("Stapelueberlauf\n"); } else { //an der Stelle(tos) wird der neue Wert in den Stapel gelegt. stack[tos]=x; //danach wird der Wert von tos um 1 erhoeht, so das ich //einen neuen Wert auf den Stapel ablegen kann. tos = tos +1; } } int pop() if(tos == 0) { printf("Stapelunterlauf\n"); } else { //tos zeigt auf eine freie Stelle im Stapel tos = tos -1; //an dieser Stelle soll der Stapel einen neuen Wert aufnehmen } return(stack[tos]); }
Auswahl: Wenn eine Zahl vorliegt, dann Zahl auf den Stapel legen. Falls
ein Operand gefunden wird, die letzten beiden Operanden vom Stapel
nehmen und mit dem Operator verknuepfen und das Ergebnis auf den
Stapel legen.-
Hauptroutine
int main()
{
printf("Ein Ausdruck: ");
scanf("%s",postfix);
init_stack();
m=strlen(postfix);
n=0;
while(n kleiner m)
{
switch(postfix[n])
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
c=postfix[n];
x=atoi(c);
break;
case '+':
x=pop()+pop();
break;
case '-':
x=pop();
x=pop()-x;
break;
case '*':
x=pop()*pop();
break;
case '/':
x=pop();
x=pop()/x;
break;
} //end switch
push(x);
n++;
} //end while n kleiner m
x=pop(); // Ergebnis vom Stapel nehmen.
printf("Das Ergebnis: %d\n",x);
return(0);
}
Die Stapelroutinen sind als Funktionen realisiert. Dies sind
init_stack fuer die Initialisierung des Stapels, push fuer das Ablegen
eines Wertes und pop fuer das Herunternehmen vom Stapel.
Ausserdem musste ich eine Routine schreiben fuer das Umwandel eines
Strings in Zahlen. Die Funktion atoi(x). Am einfachsten kann char -
'0' dies leisten.-
Ausserdem sollte fuer die Rechenoperation beachtet werden, das der
zweite Operand vor dem ersten im Stapel liegt und daher voruebergehend
in x gespeichert werden muss.
Der Stapel selbst wird als Array stack[] initialisiert, das maximal
200 Elemente aufnehmen kann. Die Variable tos enthaelt immer den Index
der Zelle im Stack, die als naechstes gefuellt werden kann.
init_stack setzt die Variable tos auf null.
Bei den Routinen pop und push ist zu beachten, das der Stapel ueber
oder unterlaufen kann. Daher die Sicherheitsabfrage mit if().
Die Auswahlentscheidung treffen wir mit switch.
Eine sehr interessante und nuetzliche Eigenschaft von abstrakten Datentypen ist, dass sie aufeinander aufbauen koennen und so eine Schichtung mit unterschiedlichen Abstraktionsniveau ermoeglichen. Dies wird uns im naechsten Kapitel, in dem es um die Implementierung binaerer Baeume geht, noch naeher beschaeftigen.
In der Informatik spielen Bäume eine große Rolle. Es handelt sich um zweidimensionale Datenstrukturen, durch die viele Probleme erst effektiv und effizient gelöst werden können.
Wenn wir mit einem relationalen Datenbank-Managment-System (RDBMS), wie dBase, Access, InterBase, Oracle oder ADABAS, arbeiten, finden im Hintergrund - in der Software - viele Operationen über Bäume statt. Durch Bäume werden zum Beispiel dort erst die schnellen Indizierungen in einer Tabelle des RDBMS ermöglicht.
Auch wenn Quelltexte kompiliert werden, finden grammatikalische Untersuchungen durch den Compiler statt, die alle auf Baumstrukturen basieren bzw. zu der Konstruktion von Syntaxbäumen führen.
Kurz gesagt: Bäume sind für viele Bereiche der Informatik wichtig. Sie gehören zum Grundlagenwissen, das uns dieser Kurs nicht vorenthalten will.
Im alltäglichen Leben begegnen sie uns in den unterschiedlichsten Formen. Zum einen den Bäumen in der Natur und zum anderen in vielen unterschiedlichen künstlichen Ausprägungen.
Wenn wir unseren Familienstammbuch durchforsten, werden wir vielleicht den einen oder anderen Stammbaum finden. Wir schlagen den Tunierteil der Zeitung auf und entdecken vielleicht einen Tunierplan, der bei einer breiten Basis beginnt, sich nach oben verjüngt und schließlich im Finale bei zwei Spieler(innen) oder Mannschaften endet.
Wenn wir uns eine größeres Unternehmen anschauen, begegnen uns die Hierarchien des Managments bzw. der Unternehmensleitung. In diesen Hierarchien können wir beispielsweise bei einer Aktiengesellschaft an der Spitze den Vorstandsvorsitzenden sehen. Nach diesem Vorstandsvorsitzenden folgen dann die einzelnen Vorstände, gefolgt von den Hauptabteilungsleitern und Betriebsleitern, Abteilungsleitern, etc. Diese Strukturen können wir als Organigramm darstellen, das nichts anderes als ein Baum ist.
Was haben Bäume im realen Leben gemeinsam? Sie haben Äste bzw. Linien, die einzelne Punkte verbinden. Sie besitzen Blätter bzw. Endpunkte, von denen keine Verzweigungen mehr ausgehen. Exakt diese Eigenschaften kennzeichnen auch die Bäume der bits und bytes.
<--- Wurzel
/____________________ A ____________________________ Ebene 0
H | / \
ö | / \
h |Großeltern-->B___________C_<---Elternknoten __ Ebene 1
e | knoten von G/ / \ von F
| / / \
d |___________D___________E_________F <-- Knoten____ Ebene 2
e | \ / \
s | \ / \
|Enkelknoten-->G___________H_______I_______________ Ebene 3
B | von B \ \ /
a | \ \ /
u | Blatt Geschwister
m \
s
Ein Baum
Die folgende Erläuterung können wir anhand der Abbildung nachvollziehen.
Ein Baum ist eine Menge von Knoten, die durch Linien, die Kanten, miteinander verbunden sind. Knoten, von denen keine weiteren Kanten ausgehen, werden Blätter genannt. Einen Weg durch den Baum von einem Knoten zum anderen über mehrere Kanten und Knoten nennt man Pfad. Der Knoten, auf den alle anderen folgen wird Wurzel genannt. Das korrekte Kriterium für die Definition der Wurzel ist, daß von diesem einen Knoten - der Wurzel - zu jedem anderen Knoten im Baum exakt ein Pfad existiert.
Die Bezeichnung der einzelnen Knoten zueinander ist dem familiären Umfeld (oder dem Stammbaum?!?) entlehnt. Der direkte Vorgänger des Knotens heißt Elternknoten (parent). Die direkten Nachfolger sind die Kinder (children). Diese Ähnlichkeit zur Familie läßt sich weiter ausführen, so dass man Großeltern, Geschwister und Enkel findet.
Die Knoten eines Baumes lassen sich in Ebenen oder Stufen einordnen. Die Ebenen eines Knotens ist dabei die Anzahl der Knoten auf dem Pfad von ihm bis zur Wurzel. Die Wurzel wird allerdings nicht mitgezaehlt. Sie erhält die Ebene 0. Die höchste Ebene, die in einem Baum auftritt, ist dessen Höhe.
Eine besondere Bedeutung kommt den binären Bäumen zu. Ein binärer Baum ist ein Baum, dessen Knoten jeweils nur maximal zwei Kinder haben können. Die beiden Kinder werden dabei als linkes und rechtes Kind bezeichnet. Diese Bezeichnung rührt aus der grafischen Darstellung der binären Bäumen her. Im Computer gibt es schließlich kein rechts und links.
*
/ \
/ \
2 +
/ \
/ \
3 4
In der Abbildung sehen wir einen einfachen binären Baum. Es ist ein Syntaxbaum, wie er bei der grammatikalischen Untersuchung eines Ausdrucks entsteht. Hier wurde der arithmetische Ausdruck 2 * ( 4 + 3) analysiert. Wenn wir von der Wurzel (*) ausgehen, können wir den Ausdruck berechnen. Der Knoten für den Operator * könnte in einem Programm als multipliziere die beiden Kindknoten miteinander interpretiert werden. Der rechte Kindknoten ist allerdings wieder ein Knoten, der besagt: addiere die Kindknoten. Bevor also die Multiplikation erfolgen kann, muß zuerst das Ergebnis des rechten Kindknotens berechnet werden.
Wir können die Situation durchspielen und werden feststellen, daß dieser Baum bei Anwendung der umgangssprachlich formulierten Regeln das korrekte Ergebnis liefert: 14.
Die Knoten eines binären Baumes werden in der Programmierung in der Regel durch einen Strukturtyp dargestellt. Je nachdem, welche Strategie verfolgt wird, können entweder alle Knoten oder nur die Blätter Daten speichern. Im Folgenden gehen wir davon aus, daß jeder Knoten Informationen aufnehmen kann. Neben dem Datenbereich zur Aufnahme der Informationen werden noch Zeiger auf den rechten und linken Kindknoten benötigt. Mit anderen Worten: Ein Baum wird im Computer als verkettete Liste dargestellt, wobei allerdings jedes Listenelement im Falle eines binären Baumes zwei Folgelemente haben kann.
Wenn die zu speichernden Informationen im Baum Strings sind, kann ein Datentyp Node wie folgt definiert werden:
struct Node {
char info;
struct Node *left_child;
struct Node *right_child;
}*nMul, *nAdd, *n2, *n3, *n4;
Die Größe eines Baumes steht selten fest, so daß der Baum selbst in C idealerweise als dynamisch verkettete Liste dargestellt werden kann. Die Deklaration des Baumes erfolgt analog zur verketteten Liste aus dem vorherigen Kapitel:
Die zu definierenden Operationen sind ebenfalls in ähnlicher Weise wie bei einer herkömmlichen verketteten Liste durchzuführen. Es muß lediglich berücksichtigt werden, daß jedes Element zwei Folgeelemente haben kann.
Für die Zwecke des Beispiels benötigen wir lediglich zwei Routinen.
int addLeft(struct Node *y)
{
if(y->left_child != NULL)
return(1);
else
return(0);
}
Die Algorithmen zur Verwaltung des Baumes entsprechen vom Prinzip her denen, für die Implementierung der verketteten Liste. Der Quelltext dürfte also keine Schwierigkeiten bereiten.
struct Node *new_node(char *s)
{
struct Node *ptr;
ptr=malloc(sizeof(*ptr));
ptr->info=*s;
ptr->left_child = NULL;
ptr->right_child = NULL;
return (struct Node *) ptr;
}
void add_node(struct Node *x, struct Node *y)
{
if(y->left_child == NULL)
y->left_child = x;
else
y->right_child = x;
}
In der Regel werden wir keinen konkreten Baum konstruieren, sondern allgemeine Algorithmen verwenden, die je nach Kontext einen entsprechenden Baum erstellen. Ein Compiler beispielsweise würde, wenn er nur einen konkreten (Syntax-)Baum erzeugen könnte, nur in der Lage sein, einen festen Quelltext in Code zu übertragen.
Hier werden wir jedoch zunächst nur mit dem Aufbau eines konkreten Baums konfrontiert. Der Baum aus Abbildung soll nur durch die oben definierten Routinen erzeugt werden. Dies erfolgt der Transparenz halber in zwei Schritten.
Ersteres erledigt der Aufruf von new_node mit den entsprechenden Parametern wie *, +, 2, 3 und 4. Damit erzeugen wir eine Reihe von Knoten, die wir zum Aufbau des Baumes aus der Abbildung benötigen. Die einzelnen Knoten speichern die Informationen am Ende dieses Abschnitts in den Variablen nMul, nAdd, n2, n3 und n4.
Nun liegen also die einzelnen Knoten vor, die jedoch noch in ein Netz aus Kanten eingebunden werden müssen, damit eine Baumstruktur entstehen kann.
Diese Aufgabe erfüllt add_node, die eine Kante zwischen zwei Knoten aufbaut. Über den letzten Parameter wird dabei festgelegt, ob das Kind rechts oder links im Elternknoten eingetragen werden soll. So entsteht eine Struktur im Speicher, wie sie in folgender Abbildung wiedergegeben ist.
nMul *
L | R
/ \
/ \
n2 2 nAdd +
L | R L | R
/ \
/ \
n4 4 n3 3
L | R L | R
Der Quelltext in C
#include#include int main() { nMul = new_node("*"); nAdd = new_node("+"); n2 = new_node("2"); n3 = new_node("3"); n4 = new_node("4"); add_node(n2, nMul); add_node(nAdd, nMul); add_node(n4, nAdd); add_node(n3, nAdd); return(0); }
Wenn wir das Berechnen eines Ausdrucks im Baum durchgespielt haben, werden wir feststellen, das wir zum Berechen des Ausdrucks des Baumes alle seine Knoten bis zu den Blättern besuchen müssen. Besuchen heißt in diesem Fall Auswerten.
Wir arbeiten uns von der Wurzel in Richtung der Blätter fort und wenden die Regel an, die besagt: Wenn der besuchte Knoten ein Operator ist dann verknüpfe die Kinder entsprechend.
Das Besuchen eines Knotens nennt man Traversierung. Die Informatik unterscheidet vier Arten von Traversierungen:
Unter dem Begriff Level-Order versteht man also das systematische Abarbeiten aller Knoten von links nach rechts und von oben nach unten. Die Knoten werden somit je Ebene ausgewertet: Zuerst alle Knoten der Ebenen 0, dann alle Knoten von Ebene 1, dann alle von Ebene 2 und so fort.
Das Prinzip ist recht einfach zu verstehen. Die Frage ist nur, wie es zu programmieren ist. Das zentrale Problem ist hier, daß sich in einem binären Baum die Anzahl der Knoten pro Ebene verdoppeln kann. Nachdem wir alle Knoten abarbeiten wollen, müssen die Knoten, oder besser die Referenzen, an irgendeiner Stelle gespeichert werden.
Wenn wir nämlich von einer Schleife ausgehen, so können wir pro Schleifenzyklus nur einen Knoten betrachten. Dieser Knoten kann jedoch zwei Folgeelemente haben, von denen wir beim nächsten Schleifendurchlauf wieder nur einen betrachten können. Den anderen müssen wir irgendwo speichern, denn der nächste Schleifendurchlauf wirft womöglich wieder zwei weitere Knoten auf. Wir haben dann schon drei Knoten, von denen wir nur einen im folgenden Schleifenzyklus berücksichtigen können.
Wir benötigen also einen Datenbereich, in dem wir die Knoten speichern können. Eine eigene Variable für jeden Knoten können wir vergessen, da wir in der Regel nicht wissen, wieviele Knoten der Baum haben wird. Wir benötigen also eine Datenstruktur, die Elemente einer variablen Anzahl aufnehmen kann.
Wir brauchen also eine Datenstruktur, die Knoten aufnehmen und wieder ausgeben kann. Da wir hier die Knoten je Ebene verarbeiten, muß diese Struktur die Eigenschaft haben, daß sie Knoten einer niedrigeren Ebene (näher an der Wurzel) vor denen einer höheren Ebene verarbeiten kann.
Es liegt in der Natur der Sache, daß die Knoten niedriger Stufen vor denen der höheren Ebenen in die Datenstruktur gelegt werden. Nun müssen diese zuvor gespeicherten auch wieder vor den später abgelegten ausgelesen werden. Die Datenstruktur muß also nach dem FIFO-Prinzip arbeiten. Wir benötigen also eine Schlange, eine Queue.
Bei der Operation über eine Queue resultiert der allgemein gültige Algorithmus aus der folgenden Abbildung. Eine Schleife legt jeweils den linken und rechten Ableger in der Schlange ab und besucht den Elternknoten.
Vor dem Schleifenstart wird lediglich der Wurzelknoten in die Schlange eingereiht. Durch diese Operation wird die Queue mit dem Knoten gefüllt, bei dem alles beginnt. Die Schleife kann mit diesem Knoten anfangen. Da jeder andere Knoten durch einen Pfad von der Wurzel aus erreichbar ist (siehe Eigenschaften von Bäumen), ist durch diese Aktion gewährleistet, daß wirklich jeder Knoten besucht wird.
Wurzel in die Queue einreihen
__________________________________
So lange bis die Queue leer ist
________________________________
| Knoten aus der Queue lesen
|_______________________________
| Knoten besuchen
|_______________________________
|\ Hat der Knoten ein /
| \ linkes Kind? /
| Ja \ | Nein
|______\__________________/_______
| linkes Kind in die |
| Queue einreihen |
|_________________________________
|\ Hat der Knoten ein /
| \ rechtes Kind? /
|____\_____________________/_______
| Ja Nein
|__________________________________
| rechtes Kind in die
| Queue einreihen
|__________________________________
In der Queue entsteht während des Abarbeitens der Schleife eine Kette von Knoten, die nach Ebenen geordnet sind.
Wir Implementieren die Queue in C über eine verkettete Liste. Diese Queue ist ein Paradebeispiel für einen abstrakten Datentyp. Sie baut auf der verketteten Liste auf und implementiert auf dieser Grundlage die Datenstruktur Schlange.
Die verkette Liste in C, die die Queue auf unterer Ebene darstellt, ist eine doppelt verkettete Liste. Die Elemente dieser Liste enthalten also nicht nur eine Referenz auf das folgende Element, sondern auch auf das vorhergehende.
void print_tree(struct Node tree)
{
char s[];
init_queue();
put(tree);
while(!isEmpty_queue)
{
tree = get();
s = tree->info + ' links: ';
if(tree->left_child == NULL)
s = s + 'X';
else
{
put(tree->left_child);
s = s + tree->left_child->info
}
s = s + ' rechts: ';
if(tree->right_child == NULL)
s = s + 'X';
else
{
put(tree->right_child);
s = s + tree->right_child->info;
}
printf("%s \n", s);
}
}
Eine Schlange benötigt im Gegensatz zum Stapel zwei Zeiger. Einen Zeiger zum Schreiben (deque_tail) und einen Zeiger zum Lesen (deque_head). Wenn ein neues Element eingereiht wird, wird dieses neue Element zum deque_tail. Wird ein Element wieder ausgelesen, das als deque_head definiert ist, wird das nächste Element zu deque_head.
Das Problem ist jedoch, wenn wir eine Queue als verkettete Liste darstellen, daß wir bei einer einfach verketteten Liste nur Verweise auf das nächste Element haben, jedoch nicht auf das vorherige. Hier ist es sinnvoll, eine doppelt verkettete Liste zu verwenden. Die Elemente einer solchen Liste verweisen nicht nur auf die Folgeeinträge, sondern auch auf die vorhergehenden.
Die Funktion put reiht ein neues Element in die Schlange ein. Hierzu wird ein neuer Eintrag vom Typ TQueue dynamisch alloziert und mit den entsprechenden Daten gefüllt. Dieses neue Element wird dadurch eingereiht, daß der Zeiger (deque_tail->next) im aktuellen Schluß der Schlange auf dieses neue Element gesetzt wird. Der Zeiger auf den vorherigen des neuen Elements (ptr->prev) wird auf den aktuellen Schluß (deque_tail) gesetzt. Damit sind diese beiden Elemente miteinander doppelt verbunden. Nun kann der neue Eintrag als neuer Schluß festgesetzt werden.
Falls das neue Element der einzige Eintrag in der Queue ist, wird das Element als Schluß und Kopf der Schlange festgelegt. Eine Verbindung zu einem anderen Element entfällt, da keines existiert.
Die Funktion get liest ein Element aus der Queue aus. Hierzu wird der aktuelle Kopf in der Variablen ptr gespeichert. Dieses Element ist es schließlich, das gelesen werden soll. Der Kopf (deque_head) wird danach angepaßt, indem er auf das folgende Element gesetzt wird (deque_head->next). Ist dieser Zeiger ein NULL-Zeiger, ist deque_head schon das letzte Element gewesen und in diesem Fall ist die Queue leer und deque_tail wird ebenfalls auf NULL gesetzt.
Zu beachten ist hier, das get keine Sicherung eingebaut hat. Falls die Schlange leer und deque_head ein NULL-Zeiger ist, kommt es zu einem Laufzeitfehler der das Programm kurzerhand beendet. Bei dem obigen Algorithmus kann dies jedoch nicht geschehen, da vor einem get immer geprüft wird, ob die Queue leer ist.
Der entsprechende Quelltext sieht folgendermaßen aus:
struct Queue {
struct Node the_node;
struct Queue *next;
struct Queue *prev;
}*queue_head, *queue_tail;
void init_queue()
{
queue_head = NULL;
queue_tail = NULL;
}
void put(struct Node x)
{
struct Queue *ptr;
ptr = malloc(sizeof(*ptr));
ptr->the_node = x;
ptr->prev = queue_tail
ptr->next = NULL;
if(queue_tail != NULL)
queue_tail->next = ptr;
queue_tail = ptr;
if(queue_head == NULL)
queue_head = ptr;
}