Bild Referenz: https://commons.wikimedia.org/wiki/File:C_language_linked_list.png

Intro

    Hallo, ich bin's @drifter2! Das heutige Thema sind wieder Warteschlangen und Stapel dieses mal aber implementiert mit Listen, die ich euch rate anzusehen. Dieser Artikel ist an zwei meiner englischen Artikel basiert, die ihr bei den Referenzen finden könnt. Da nichts neues in Theorie zu sagen ist und alles nur Code ist, dachte ich mir das eine deutsche Übersetzung der Kommentare und von den Beschreibungen mehr als genug ist. Deswegen mache ich auch einen Artikel für beides gleichzeitig! Also dann fangen wir dann mal an!

---

Verkettete Liste in C-Sprache

    Eine Verkettete Liste ist eine dynamische Datenstruktur die aus Knoten (Nodes auf Englisch) besteht die miteinander verbunden sind. In C-Sprache wird einer solche Knote/Node als struct wie folgend definiert:

typedef struct Node{ 

	int val;

	struct Node *next;

}Node;

Diese Ganzzahlen-Knote wird gleich bei beiden Datenstrukturen benutzt!

---

Warteschlange implementiert mit Verketteter Liste

     Eine Warteschlange arbeitet nach dem FIFO-Prinzip. Wir können Elemente nur von dem Anfang (Front-Index) nehmen und Elemente nur am Ende (Rear-Index) hinzufügen. Mit Feldern-Arrays mussten wir Zeiger auf diese Indexe definieren. Mit Listen definieren zwei Knoten-Zeiger (Node pointers) die wir wieder mal auf NULL initialisieren müssen, so dass wir wissen wann die Warteschlange leer ist. Mit der Verwendung von einer Liste hat eine solche Warteschlange nun eine unendliche Kapazität (so viel wie in die RAM passt). Natürlich können wir auch eine gewisse Kapazität als Strukturelement definieren, die bei manchen Anwendung vielleicht von Nöten ist.

Die neue Struktur (struct) die nun eine Warteschlange definiert ist:

typedef struct Queue{

	Node *front;

	Node *rear;

}Queue;

Wie ihr sehen könnt wurde das Feld und die Indexe mit zwei Zeigern ersetzt!

    Bei den Funktionen werden wir wieder mal eine Zeiger-Struktur-Variable benutzen, so dass die Veränderungen abgespeichert werden. Die eigentliche Variable von der main() Funktion muss aber nicht unbedingt ein solcher Zeiger sein, wir können nämlich auch die Speicheradresse verwenden und diese als Parameter an die Funktionen abgeben..

Einfügen(Enqueue):

    Wenn man eine Kapazität-Variable definiert hat muss man, wie bei der Feld-Implementierung, wieder mal kontrollieren ob die Warteschlange voll ist. Bei unserer Implementierung werden wir das auslassen.

     Wie wir bereits von Listen wissen, müssen wir erstmal ein neues Knoten-Εlement erstellen was wie folgend aussieht:

Node *nn;

nn = (Node*)malloc(sizeof(Node));

nn->val = val;

nn->next = NULL;

    Wenn die Warteschlange leer ist, dann setzen wir den Front- und Rear-Zeiger zu dieser neuen Knote. Bei jedem anderen Fall fügen wir diese neue Knote am Ende der Warteschlange eine, durch die Benutzung eines Derzeitiger Knoten-Zeigers. Die neue Knote wird dann der neue Rear-Zeiger.

Der Code dafür sieht wie folgend aus:

void enqueue(Queue *Q, int val){

	Node *cur, *nn;

	// Neue Knote erstellen

	nn = (Node*)malloc(sizeof(Node));

	nn->val = val;

	nn->next = NULL;

	// Kontrollieren ob Warteschlange leer ist

	if(Q->front == NULL){

		Q->front = Q->rear = nn;

	}

	// Genereller Fall

	else{

		// Jetzige Knote-Zeiger auf "Front" setzen

		cur = Q->front;

		// Letzte Knote finden

		while(cur->next != NULL){

			cur = cur->next;

		}

		// Neue Ende am Ende hinzufuegen

		cur->next = nn;

		Q->rear = nn;	

	}

}

Löschen (Dequeue):

    Beim Entfernen eines Elements müssen wir erstmal kontrollieren ob die Warteschlange leer ist. Wenn diese leer ist werde ich '-1' zurückgeben, was uns sagt das die Warteschlange leer ist (natürlich müssen deswegen die Warteschlangen-Elemente nur positive Werte haben). Vor dem löschen müssen wir den Wert vom Front-Index erstmal temporär abspeichern. Wenn das Element das einzige Element der Warteschlange ist dann setzen wir beide Zeiger auf NULL, sonst wird der Front-Zeiger von seinem Nachfolge-Zeiger (next pointer) ersetzt. Am ende geben wir den Wert zurück.

Der Code sieht wie folgend aus:

int dequeue(Queue *Q){

	int val;

	// Kontrollieren ob Warteschlange leer ist

	if(Q->front == NULL){

		return -1;

	}

	// Wert von Front abspeichern

	val = Q->front->val;

	// Kontrollieren ob es sich um das einzige Element handelt

	if(Q->front == Q->rear){

		Q->front = Q->rear = NULL;

	}

	// Einfachster Fall

	else{

		// Front-Zeiger zeigt nun auf seinen Nachfolger

		Q->front = Q->front->>next;

	}

	// Wert zurueckgeben

	return val;	

}

Ausdrucken (Print):

   Wie bei der Implementierung mit Feldern, ist der leichteste Weg um durch die Ganze Warteschlange zu iterieren die Verwendung der dequeue() Funktion solange es Elemente in der Warteschlange gibt! Natürlich könnten wir die Liste auch normal durchlaufen, wie wir bereits von Listen können. Damit wir die Informationen nicht verlieren werden wir nur die Variable verwenden und keinen Zeiger, so dass die Warteschlange nur Lokal (in der Funktion) verändert wird.

Der Code sieht wie folgend aus:

void print(Queue Q){

	int val;

	// Kontrollieren ob Warteschlange leer ist

	if(Q.front == NULL){

		printf("Queue is Empty!\n");

		return;

	}

	// dequeue() ausfuehren solange es Elemente gibt

	while((val= dequeue(&Q)) != -1){

		printf("%d ", val);

	}	

	printf("\n");

}

Komplettes Beispielprogramm:

Zuletzt hier noch ein komplettes Beispielprogramm:

int main(){

	// Warteschlange initialisieren

	Queue Q;

	Q.front = Q.rear = NULL;

	print(Q);

	// 5 einfuegen

	enqueue(&Q, 5);

	print(Q);

	// 10 einfuegen

	enqueue(&Q, 10);

	print(Q);

	// Elemente rausnehmen

	int val;

	val = dequeue(&Q);

	if(val == -1){

		printf("Queue is Empty!\n");

	}

	else{

		printf("%d\n", val);

	}

	print(Q);		

}

---

Stapel implementiert mit Verketteter Liste

    Ein Stapel arbeitet nach dem LIFO-Prinzip. Was also zuletzt hinzugefügt wird, wird als erstes wieder weggenommen. Man hat also nur Zugriff auf das oberste (top) Stapelobjekt. Ähnlich wie bei der Implementation mit Feldern-Arrays wo wir diesen Top-Index abspeichern mussten, werden wir hier einen Top-Zeiger haben, der auch das einzige Element der Struktur sein wird! Durch die Verwendung von einer Liste haben wir nun einen Stapel der unendlich viele Elemente abspeichern kann. Wenn eine Anwendung eine gewisse Kapazität benötigt dann können wir zusätzlich auch eine Kapazität-Variabel deklarieren.

Ohne diese zusätzliche Info sieht der struct des Stapels wie folgend aus:

typedef struct Stack{

	Node *top;

}Stack;

    Der Top-Zeiger muss natürlich auf NULL initialisiert werden (ähnlich wir top-Index auf -1 gesetzt wurde), so dass wir wissen ob der Stapel leer ist.

    Bei den Funktionen werden wir wieder mal eine Zeiger-Struktur-Variable verwenden. Die eigentliche Struktur kann auch als normal Struktur-Variable definiert werden, da wir ja auch die Speicheradresse als Parameter abgeben können.

Einfügen (Push):

   Beim hinzufügen eines neuen Elements müssen wir erstmal kontrollieren ob der Stapel voll ist. Das ist natürlich nur von Nöten wenn man eine gewisse Stapel-Kapazität definiert hat.

    Zuerst, erstellen wir eine neue Knote, wie vorhin bei der Warteschlange (deswegen lasse ich das mal aus). Der spezial Fall hier ist wieder mal der leere Stapel, wo wir den Top-Zeiger durch den neuen Knoten-Zeiger ersetzen (Top-Zeiger auf Knoten-Zeiger setzen). Wenn es bereits Elemente gibt dann wird der Nachfolger-Zeiger der neuen Knote zu dem jetzigen Top-Zeiger gesetzt und die neue Knote der neue Top-Zeiger.

All das sieht mit Code wie folgend aus:

void push(Stack *S, int val){

	Node *nn;

	// Neue Knote erstellen

	nn = (Node*)malloc(sizeof(Node));

	nn->val = val;

	nn->next = NULL;	

	// Wenn Stapel nicht leer ist

	if(S->top != NULL){

		// make nn's next point to top

		nn->next = S->top;

	}

        // sonst wird nn->next NULL bleiben!

	// Neue Knote wird neuer Top-Zeiger

	S->top = nn;		

}

Löschen-Entfernen (Pop):

    Beim Löschen müssen wir kontrollieren ob der Stapel leer ist, wo wir wieder mal '-1' zurückgeben werden. Vor dem entfernen müssen wir den Wert vom Top erstmal temporär abspeichern. Danach wir dieser Zeiger einfach durch seinen Nachfolger-Zeiger (next pointer) ersetzt.

Der Code dafür ist:

int pop(Stack *S){

	int val;

	// Kontrollieren ob Stapel leer ist

	if(S->top == NULL){

		return -1;

	}

	// Wert von Top abspeichern

	val = S->top->val;

	// Top auf seinen Nachfolger zeigen lassen

	S->top = S->top->next;

	// Wert zurueckgeben

	return val;	

}

Ausdrucken (Print):

    Ähnlich wie bei der Feld-Implementierung, werden wir wieder mal die pop() Funktion ausführen solange der Stapel nicht leer ist. Damit wir den Stapel nicht verändern werden wir nun eine "normale" Struktur-Variable verwenden und nicht die eigentliche Adresse.

Das sieht in Code wie folgend aus:

void print(Stack S){

	int val;

	// Kontrollieren ob Stapel leer ist

	if(S.top == NULL){

		printf("Stack is Empty!\n");

		return;

	}

	// pop() solange es Elemente im Stapel gibt

	while((val = pop(&S)) != -1){

		printf("%d ", val);

	}	

	printf("\n");

}

Komplettes Beispielprogramm:

Zuletzt hier noch ein Beispielprogramm:

int main(){

	// Stapel initialisieren

	Stack S;

	S.top = NULL;

	print(S);

	// 3 hinzufuegen

	push(&S, 5);

	print(S);

	// 7 hinzufuegen

	push(&S, 10);

	print(S);

	// 2 hinzufuegen

	push(&S, 2);

	print(S);

	// Element vom Stapel entfernen

	int val;

	val = pop(&S);

	if(val == -1){

		printf("Queue is Empty!\n");

	}

	else{

		printf("%d\n", val);

	}

	print(S);	

}

Notiz:

    Ihr habt vielleicht bemerkt das beide Beispielprogramme die gleichen sind die wir auch bei den "Feld-Artikeln" hatten. Das einzige das sich geändert hat ist die Initialisierung der Strukturen, da wir jetzt die Zeiger (front, rear und top) auf NULL setzen müssen. Bei Feldern wurden die Indexe ja auf '-1' initialisiert!

---

Referenzen:

1. https://steemit.com/programming/@drifter1/programming-c-queues-using-linked-lists
2. https://steemit.com/programming/@drifter1/programming-c-stacks-using-linked-lists

---

Vorherige Artikel

Grundlagen 

Einführung -> Programmiersprachen, die Sprache C, Anfänger Programme

Felder ->  Felder, Felder in C, Erweiterung des Anfänger Programms

Zeiger, Zeichenketten und Dateien -> Zeiger, Zeichenketten, Dateiverarbeitung, Beispielprogramm

Dynamische Speicherzuordnung -> Dynamischer Speicher, Speicherzuweisung in C, Beispielprogramm 

Strukturen und Switch Case -> Switch Case Anweisung, Strukturen, Beispielprogramm

Funktionen und Variable-Gueltigkeitsbereich -> Funktionen, Variable Gueltigkeitsbereich

Datenstrukturen

Rekursive Algorithmen -> Rekursion, Rekursion in C, Algorithmen Beispiele

Verkettete Listen -> Datenstrukturen generell Verkettete Liste, Implementation in C (mit Operationen/Funktionen), komplettes Beispielprogramm

Binäre Suchbäume -> Baum Datenstruktur generell, Binärer Baum, Binärer Suchbaum, Implementation in C-Sprache (mit Operationen/Funktionen), komplettes Beispielprogramm

Warteschlangen implementiert mit Feldern -> Warteschlange als Datenstruktur, Implementation einer Warteschlange mit Feldern in C-Sprache, komplettes Beispielprogramm

Stapel implementiert mit Feldern -> Stapel als Datenstruktur,  Implementation eines Stapels mit Feldern in C-Sprache, komplettes Beispielprogramm

---

Schlusswort

    Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Νächstes mal werden wir über fortgeschrittene Listen und Warteschlangen reden!

Keep on drifting! ;)