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

Intro

    Hallo, ich bin's @drifter2! Der heutige Artikel ist wieder mal eine Übungsaufgabe rund um Stapel und Warteschlangen, die dieses mal an meinem englischen Artikel "C Stack-Queue Exercise using Linked Lists" basiert ist. Letztes mal hatten wir was sehr ähnliches mit Dynamischen Feldern implementiert. Natürlich solltet ihr euch erstmal die Artikel rund um Stapel und Warteschlangen anschauen, und vielleicht auch die vorherige Übungsaufgabe. Also dann fangen wir dann mal direkt an!

---

Aufgabenbeschreibung:

    Ähnlich wie beider vorherigen Aufgabe haben wir wieder mal 2 Fähren Boote. Die erste Fähre heißt 'S', weil sie wie eine Stapel (Stack auf Englisch) funktioniert. Die zweite 'Q', weil sie wie eine Warteschlange (Queue auf Englisch) funktioniert. Diese Funktionalität zeigt uns in welcher Reihenfolge Autos in diese Fähren reingesetzt und wieder weggenommen werden können. Jedes Auto wird jetzt aber nicht mehr eine Fähre auswählen, sondern die Autos werden erstmal in Fähre S und dann in Fähre Q eingefügt.

     Der Dateiname ist eine Eingabe des Benutzers des Programms und muss die Auto-ID (Identifikationsnummer oder auch Nummernschild) enthalten. Damit wir die Resultate mit denen vom letztem mal vergleichen können, werden wir wieder in der Datei immer noch eine Boot-Präferenz abspeichern, die bei dieser Aufgabe hier eigentlich unnötig ist. Eine solche Datei die 5 Autos mit dessen Präferenz enthält kann wie folgend aussehen:

 ZZA9896 S

MIN5689 Q

NHI9098 S

KNM4545 Q

IPO8987 Q

Das Programm das ihr implementiert muss folgendes machen:

1. Die Kapazität der Boote und den Namen der Autos-Datei als Eingabe des Benutzers bekommen
2. Die Boote, oder besser gesagt, dessen Datenstrukturen, initialisieren 
3. Von der Autos-Datei lesen und das Segeln beider Boote verwalten, indem man diese füllt bis sie voll sind 
4. Die Autos gehen erstmal in Boot S. Wenn diese Boot voll wird, dann fangen wir mit dem "Segeln" an, welches bedeutet das wir die Auto-ID's in einer Neuen Datei schreiben und das natürlich per Segel, indem wir den Stapel entleeren. Die Namen dieser Dateien sollten in der Form: s0, s1, s2, ... sein
5. Bei dem entleeren von Boot S werden die Autos dann in Boot Q eingefügt und das bis S leer ist (das sollte natürlich vor dem Segeln von S anfangen!). Jedes mal wenn Q voll wird werden wir wieder mal mit dem "Segeln" anfangen, indem wir die Auto-ID's in einer neuen Datei schreiben, mit Namen der Form: qo, q1, q2, ... per Segel.
6. Die Schritte 3-5 werden wiederholt bis kein neues Auto in der Autos-Datei ist (EOF)
7. Danach müssen wir nochmals kontrollieren ob es Autos in den Booten gibt, welches bedeutet das wir auch die "nicht-vollen" Segel ausführen, indem wir auch diese normal in Dateien schreiben. Natürlich sollten wir hier aufpassen das die Autos wiedermal erstmal in S reingehen und danach in Q!

Die eigentliche Veränderung ist also bei Schritt 4 (der jetzt in 4 und 5 eingeteilt wurde)

Die Stapel und Warteschlangen Operationen müssen als Funktionen implementiert werden.

---

Lösung-Implementation in C

Datenstrukturen

    Da wir über Listen reden müssen wir natürlich einen Knoten (Node) definieren welcher eine Auto-ID und einen Zeiger auf den nächsten (next) Knoten enthält. Die Struktur des Knoten sieht also wie folgend aus:

typedef struct Node{

	char car_id[10];

	struct Node *next;

}Node;

    Ich sollte hier vielleicht mal erwähnen das wir von der Autos-Datei wissen das die Auto-ID's aus 7 Zeichen bestehen. Das heißt also das diese als Zeichenkette ein 8er Feld brauchen (\0 am Ende). Wie ihr sehen könnt ist die maximale Länger aber ein wenig höher, so das ich eine "vollere" Nummer habe :P

Die Boot-Strukturen müssen folgendes enthalten:

• eine gewisse Kapazität (capacity auf Englisch) Variable so das wir kontrollieren ob Boot voll ist oder auch leer für Schritt 7
• eine Segel Nummer (sailing number auf Englisch) um die richtige Nummer bei den Dateinamen zu verwenden
• Die Anzahl an Elementen die eingefügt wurden (numElements)
• Top-Zeiger für den Stapel und Front und Rear-Zeiger für die Warteschlange

Die Strukturen (structs) sehen also in Code wie folgend aus:

// Stapel Struktur

typedef struct Stack{

        int sail_num;

	int capacity;

	int numElements;

	Node *Top;

}Stack;

// Warteschlangen Struktur

typedef struct Queue{

        int sail_num;

	int capacity;

	int numElements;

	Node *front;

	Node *rear;		

}Queue;

    Wie ihr sehen könnt ist diese Definition nicht so ganz abweichend von der die wir bei den Artikeln erwähnt haben. Wir haben einfach ein paar Variablen ergänzt die bei der Anwendung hilfreich sind. Fangen wir dann mal mit der Implementierung von den verschiedenen Funktionen und Schritten an...

Benutzer-Eingabe und Lesen der Autos-Datei

    Wie beim letzen mal werden wir die Struktur-Variablen wieder mal "ganz normal" und nicht als Zeiger definieren wie folgend:

Stack S;

Queue Q;

Die Kapazität kann dann sehr leicht wie folgend als Eingabe genommen werden:

printf("Capacity of S: "); 

scanf("%d", &S.capacity);

printf("Capacity of Q: ");

scanf("%d", &Q.capacity);

     Um von einer Datei lesen zu können brauchen wir erstmals einen Datei-Zeiger (file pointer - fp auf Englisch). Zusätzlich werden auch temporäre Lese-Puffer gebraucht für die Auto-ID und die Boot-Präferenz (auch wenn diese nur gebraucht wird um beim Motiv der Datei zu bleiben). Natürlich sollten wir auch nicht vergessen eine Zeichenkette für den eigentlichen Dateinamen zu definieren.

Also brauchen wir:

char input_file[20]; // Dateiname

FILE *fp; // Datei Zeiger

// Lese-Puffer fuer die Datei

char car_id[10];

char ship;

Der Dateiname kann sehr leicht genommen werden:

printf("Input File: ");

scanf("%19s", input_file);

Das öffnen der Datei zum Lesen sieht wie folgend aus:

if(!(fp=fopen(input_file, "r"))){ 

	perror("fopen");

	return 1;

} 

    Wir kontrollieren natürlich auch ob es vielleicht einen Datei-Fehler gab, da sonst die Programmausführung nicht weitergehen kann. Die Datei könnte z.B nicht existieren oder der Zugriff könnte verweigert sein.

Datenstrukturen initialisieren

Um den Stapel zu initialisieren müssen wir folgendes machen:

• Den Top-Zeiger auf NULL initialisieren
• Nummer von Elementen (numElements) auf '0' setzen
• Segelnummer auf '0' setzen

Das ganze sieht in Code wie folgend aus:

S.Top=NULL;

S.numElements=0;

S.sail_num=0;

    Da bei Listen kein Speicher zugewiesen werden muss und das automatisch bei der Ausfuhr passiert, ist die Initialisierung beider Strukturen sehr simple gehalten!

Die Warteschlange wird wie folgend initialisiert:

• Front und Rear-Zeiger auf NULL initialisieren
• Nummer von Elementen (numElements) auf '0' setzen
• Segelnummer auf '0' setzen

Der eigentliche Code sieht wie folgend aus:

Q.front=Q.rear=NULL;

Q.numElements=0;

Q.sail_num=0;

Sehr ähnlich mit der Stapel-Initialisierung.

Datenstruktur-Operationen

    Bevor wir weitermachen sollten wir jetzt die eigentlichen Funktionen für die Verwaltung der Boot-Strukturen implementieren, damit wir diese dann direkt bei der Lesungs-While-Schleife verwenden können...

Die Funktionen-Operationen die wir brauchen sind:

• Auto-ID in Stapel einfügen (push)
• Auto-ID vom Stapel rausnehmen (pop)
• Stapel in Datei einspeichern - Segeln von 'S' ausführen (StackToFile)
• Auto-ID in Warteschlange einfügen (add)
• Auto-ID von der Warteschlange rausnehmen (delete)
• Warteschlange in Datei einspeichern - Segeln von 'Q' ausführen (QueueToFile)

Implementieren wir mal jede alleine...

In Stapel einfügen

    Beim einfügen müssen wir erstmal einen neuen Knoten erstellen. Danach kontrollieren wir erstmal ob der Stapel leer ist. Wenn ja dann wird das neue Element der neue Kopf der Liste, wenn nicht dann wird dieser wieder der neue Kopf der Liste aber zusätzlich die vorherige Liste sein next-Zeiger. Bei beiden Fällen inkrementieren wir auch die Anzahl an Elementen um zu wissen wann der Stapel voll ist. Wir ihr bereites verstehen könnt kontrollieren wir hier nirgends ob der Stapel voll ist, da das bei der main() Funktion bereits kontrolliert wird, so das die Entleerung erst nach dem Segeln von Boot Q stattfindet.

Das sieht in Code wie folgend aus:

void push(Stack *S, char x[]){

        Node *cur, *nn;

        // neuen Knoten erstellen

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

	strcpy(nn->car_id, x);

	nn->next=NULL;

        // wenn leer ist der der neue Kopf

	if(S->Top==NULL){

		S->Top=nn;

		S->numElements++;

		return;

	}

        // wenn bereits Elemente da sind, wird der next-Zeiger

        // von "nn" auf diese zeigen und dann der neue Kopf werden

	if(S->numElements < S->capacity){

		nn->next=S->Top;

		S->Top=nn;

		S->numElements++;

	}

        // Wir koennten beides auch direkt vom Zweiten "if" machen

        // da ja der Top-Zeiger beim ersten mal sowieso NULL waehre!

}

Vom Stapel rausnehmen

    Beim rausnehmen kontrollieren wir erstmal ob der Stapel vielleicht leer ist. Das geht ganz leicht indem wir abchecken ob der Wert vom Top-Zeiger 'NULL' ist. Wenn nicht leer speichern wir den Wert im zweiten Parameter ab und lassen Top-Zeiger auf seinen "next" zeigen, so das wir im Stapel weitergehen!

Das ganze sieht in Code wie folgend aus:

void pop(Stack *S, char *car_id){

        // kontrollieren ob Stapel leer ist (unnoetig)

        if(S->Top==NULL){

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

	}

        // Wert in Parameter speichern und dann Top-Zeiger

        // auf den naechsten (next) Knoten zeigen lassen

	 else{

		strcpy(car_id, S->Top->car_id);

		S->Top=S->Top->next;

	}

}

Stapel Segeln ausführen

     Beim Segeln müssen wir natürlich erstmal den Dateinamen "erschaffen". Das kann leicht mit Hilfe von den Funktionen:

• itoa(), welche eine Funktion ist die Ganzzahlen in Zeichenketten konvertiert
• strcpy(), welche eine Funktion ist die eine Zeichenkette kopiert (copy)
• strcat(), welche eine Funktion ist die Zeichenketten "verkettet" (concatenate)

gemacht werden.

    Natürlich werden wir dann eine Datei zum schreiben öffnen die diesen Namen hat und dann mit einer While-Schleifen so lange von dem Stapel rausnehmen mit pop() und schreiben bis der Top-Zeiger einen Wert von "NULL" hat. Wie ihr sehen könnt kann man damit sehr leicht kontrollieren ob der Stapel voll ist, etwas das hier sonst nicht ging, da wir nicht den Wert zurückgeben, da dieser ja keine Nummer ist. Man könnte eine gewisse Auto-ID als "Leer-Zeichen" benutzen aber ich glaub das ist hier eh unnötig. Damit die Daten vom Stapel nicht verloren gehen und dann von der Warteschlange benutzbar sind geben wir die Struktur diesem mal als Variable und nicht als Zeiger ein! Die erneute Initialisierung wir erst später von der main() Funktion kontrolliert!

Der Code sieht wie folgend aus:

void StacktoFile(Stack S){

        FILE *fp;

	Node *cur;

	char output_file[10];

	char buffer[2];

	char car_id[10];

	itoa(S.sail_num, buffer, 10);

	strcpy(output_file, "s");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	fp=fopen(output_file, "w");

	while(S.Top!=NULL){

			pop(&S, car_id);

			fprintf(fp, "%s\n", car_id);

	}

	fclose(fp);

}

     Das einzige neue ist also eigentlich nur das wir den Top-Zeiger nun mit  NULL anstatt '-1' vergleichen, etwas das beim Top-Index verwendet wurden.

In Warteschlange einfügen

   Um eine Auto-ID in die Warteschlange einzufügen müssen wir erstmal wieder mal einen neuen Knoten erstellen. Danach gibt es 3 gewisse Fälle die wir kontrollieren sollten. Wenn Liste/Warteschlange leer ist dann werden beider Zeiger (Front und Rear) mit "nn" gleichgesetzt. Wenn bereits Elemente da sind, iterieren wir durch die Liste mit einen Jetzige-Knote-Zeiger (cur pointer) und fügen das neue Element (den neuen Knoten) am Ende ein. Bei beiden Fällen sollten wir die Nummer von Elementen inkrementieren. Der letzte Fall den wir kontrollieren sollten ist ob die Warteschlange voll ist. Wenn voll führen wir das Segeln aus, im Gegensatz zum "darf" man das hier machen, da ja die Warteschlange von keinem "folgenden" Boot benutzt wird.

Der Code ist wie folgend:

void add(Queue *Q, char x[]){

        Node *cur, *nn;

        // neuen Knoten erstellen

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

	strcpy(nn->car_id, x);

	nn->next=NULL;

        // wenn leer ist wird "nn" neuer Front- und Rear-Zeiger

	if(Q->front == NULL){

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

		Q->numElements++;

	}

        // wenn Elemente da wird "nn" am Ende eingefuegt

	if(Q->numElements<Q->capacity){

		cur=Q->front;

		while(cur->next!=NULL){

			cur=cur->next;

		}

		cur->next=nn;

		Q->rear=nn;

		Q->numElements++;

	}

        // wenn voll dann wird Segeln ausgefuehrt

	else{

		QueuetoFile(Q);

	}

}

Von der Warteschlange rausnehmen

    Beim rausnehmen können wir wieder mal kontrollieren ob die Warteschlange vielleicht leer ist, etwas das aber wieder mal von dem Segeln kontrolliert werden kann. Danach gibt es zwei Fälle: das zulöschende Element ist das einzige Element oder es gibt mehrere. Beim ersten Fall müssen wir beide Zeiger auf 'NULL' initialisieren. Beim zweiten nur Front-Zeiger zum seinen nächsten Knoten zeigen lassen. Bei beiden sollten wir den Wert wieder mal beim zweiten Parameter abspeichern.

Der Code dafür ist:

void delete(Queue *Q, char *car_id){

        // kontrollieren ob leer ist (unnoetig)

        if(Q->front==NULL){

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

	}

	else{

                // einziges Element - beides wird 'NULL'

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

			strcpy(car_id, Q->front->car_id);

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

			Q->numElements=0;

		}

                // es gibt noch andere Elemente - Front Zeiger -> next

		else{

			strcpy(car_id, Q->front->car_id);

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

			Q->numElements--;

		}

	}

}

Warteschlange Segeln ausführen

    Ähnlich wie beim Stapel müssen wir erstmal den Dateinamen "erschaffen". Danach können wir ganz normal eine Datei mit diesen Dateinamen zum schreiben öffnen und mit einer While-Schleife ganz normal die Auto-ID's rausnehmen und schreiben, solange die Warteschlange nicht leer ist. Zuletzt sollten wir die Warteschlange erneut initialisieren, indem wir erstmals die Segelnummer inkrementieren und die Nummer der Elemente auf '0' setzen.

Der Code ist also:

void QueuetoFile(Queue *Q){

	 Node *cur;

	FILE*fp;

	int i;

	char output_file[10];

	char buffer[2];

	char car_id[10];

	itoa(Q->sail_num, buffer, 10);

	strcpy(output_file, "q");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	fp=fopen(output_file, "w");

	while(Q->front!=NULL){

		delete(Q, car_id);

		fprintf(fp, "%s\n", car_id);

	}

	Q->sail_num++;

	Q->numElements=0;

	fclose(fp);

}

Lese-Schleife

    Das Lesen geht mit einer While-Schleife, welche aufhört wenn es in der Datei keine Elemente (Auto-ID's) mehr gibt, also solange mann nicht das Ende der Datei (EOF) erreicht hat. Bei dieser Kontrolle lesen wir natürlich auch immer die Auto-ID und die Boot-Präferenz, auch wenn die zweite hier nicht gebraucht wird und nur benutzt wir um die gleiche Datei verwenden zu können. Danach fügen wir die jetzige Auto-ID bei Boot 'S' ein. Dabei kontrollieren wir ob das Boot voll ist. Wenn voll führen wir erstmal das Segeln aus, womit aber die Daten des Stapel nie verloren gehen, da wir ja nur die Struktur-Daten abgeben und nie die eigentliche Adresse dieser Daten! Danach iterieren wir durch den Stapel und fügen die Auto-ID's in der Warteschlange ein, solange wir nicht das Ende des Stapels erreicht haben. Jedes mal wo die Warteschlange voll wird müssen wir ein Segeln von Boot Q ausführen. Nachdem alle Elemente von dem Stapel durch-iteriert wurden inkrementieren wir die Segelnummer vom Stapel und setzen diesen zurück, indem wir Top-Zeiger wieder auf 'NULL' initialisieren und die Nummer der Elemente auf '0' setzen (indem wir also alles was nicht bei der Funktion StacktoFile() ausgeführt wurde nun ausführen).

Der Code sieht wie folgend aus:

// solange wir nicht das Ende der Datei (EOF) erreicht haben

while(fscanf(fp, "%9s %c", car_id, &ship)!=EOF){

        // Auto-ID in Stapel einfuegen 

	push(&S, car_id);

	// wenn Stapel voll wird in Datei schreiben

	if(S.numElements==S.capacity){

		StacktoFile(S);

		// in naechste Faehre (Q) einfuegen

		cur=S.Top;

		while(cur!=NULL){

                        // Auto-ID in Warteschlange einfuegen 

			add(&Q, cur->car_id);

			// wenn voll in Datei schreiben 

			if(Q.numElements==Q.capacity){

				QueuetoFile(&Q);

			}

			cur=cur->next;

		}

		// Stapel zuruecksetzen

		S.sail_num++;

		S.Top=NULL;

		S.numElements=0;

	}		

}

Kontrollieren ob Boote (wirklich) leer sind

     Nach dieser Schleife sollten wir nochmal kontrollieren ob es noch Autos (oder Auto-ID's) in den Booten gibt, da unser Code ja nur einschreibt wenn die maximale Kapazität erreicht wurde. Das kann man sehr leicht machen indem man sich die "numElements" Variablen anschaut. Wenn diese nicht '0' sind dann heißt "Mann über Bord"! Wir sollten dabei natürlich aufpassen das wir S entleeren und dabei Q füllen. Nachdem S fertig ist kann es natürlich immer noch sein das Boot Q immernoch Autos enthält, also kontrollieren wir danach auch noch Boot Q alleine! Danach noch die Datei schließen und das war's...

Der Code ist:

// kontrollieren ob S noch Autos hat

if(S.numElements!=0){

	StacktoFile(S);

	// in naechste Faehre (Q) einfuegen

	cur=S.Top;

	while(cur!=NULL){

		add(&Q,cur->car_id);

		// wenn voll Q in Datei schreiben

		if(Q.numElements!=0){

			QueuetoFile(&Q);

		}

		cur=cur->next;

	}

}

// kontrollieren ob Q noch Autos hat

if(Q.numElements!=0) QueuetoFile(&Q);

fclose(fp);

return 0;	

---

Das vollständige Programm:

Hier noch mal das komplette Programm...

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// Knoten Struktur fuer die Listen

typedef struct Node{

	char car_id[10];

	struct Node *next;

}Node;

// Stapel Struktur 

typedef struct Stack{

	int sail_num;

	int capacity;

	int numElements;

	Node *Top;

}Stack;

// Warteschlangen Struktur 

typedef struct Queue{

	int sail_num;

	int capacity;

	int numElements;

	Node *front;

	Node *rear;		

}Queue;

// Funktionen Deklarieren 

void push(Stack *S, char *x);

void pop(Stack *S, char *car_id); 

void StacktoFile(Stack S);

void add(Queue *Q, char *x);

void delete(Queue *Q, char *car_id);

void QueuetoFile(Queue *Q);

int main(){

	// Boot Variablen 

	Stack S;

	Queue Q;

	// Hilfs-Variablen

	Node *cur;

	char input_file[20];

	int i;

	FILE *fp;

	// Temporaere Datei-Puffer 

	char car_id[10];

	char ship;

	//  Kapazitaet Eingabe 

	printf("Capacity of S: ");

	scanf("%d", &S.capacity);

	printf("Capacity of Q: ");

	scanf("%d", &Q.capacity);

	// Dateinamen Eingabe 

	printf("Input File: ");

	scanf("%19s", input_file);

	// Datei zum lesen oeffnen 

	if(!(fp=fopen(input_file, "r"))){ 

		perror("fopen");

		return 1;

	} 

	// Stapel initialisieren 

	S.Top=NULL;

	S.numElements=0;

	S.sail_num=0;

	// Warteschlange initialisieren 

	Q.front=Q.rear=NULL;

	Q.numElements=0;

	Q.sail_num=0;

	// solange wir nicht das Ende der Datei (EOF) erreicht haben 

	while(fscanf(fp, "%9s %c", car_id, &ship)!=EOF){

                // Auto-ID in S einfuegen 

		push(&S, car_id);

		//  wenn voll in Datei schreiben 

		if(S.numElements==S.capacity){

			StacktoFile(S);

			// in naechste Faehre (Q) einfuegen

			cur=S.Top;

			while(cur!=NULL){

                                // Auto-ID in Q einfuegen 

				add(&Q, cur->car_id);

				//  wenn voll in Datei schreiben 

				if(Q.numElements==Q.capacity){

					QueuetoFile(&Q);

				}

				cur=cur->next;

			}

			// Stapel zuruecksetzen

			S.sail_num++;

			S.Top=NULL;

			S.numElements=0;

		}		

	}

	// kontrollieren ob S noch Autos hat

        if(S.numElements!=0){

	      StacktoFile(S);

	      // in naechste Faehre (Q) einfuegen

              cur=S.Top;

	      while(cur!=NULL){

		    add(&Q,cur->car_id);

		    // wenn voll Q in Datei schreiben

		    if(Q.numElements!=0){

		    	  QueuetoFile(&Q);

		    }

		    cur=cur->next;

	      }

        }

       // kontrollieren ob Q noch Autos hat

        if(Q.numElements!=0) QueuetoFile(&Q);

        fclose(fp);

        return 0;	

}

// Stapel Funktionen 

void push(Stack *S, char x[]){

	Node *cur, *nn;

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

	strcpy(nn->car_id, x);

	nn->next=NULL;

	if(S->Top==NULL){

		S->Top=nn;

		S->numElements++;

		return;

	}

	if(S->numElements < S->capacity){

		nn->next=S->Top;

		S->Top=nn;

		S->numElements++;

	}

}

void pop(Stack *S, char *car_id){

	if(S->Top==NULL){

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

	}

	else{

		strcpy(car_id, S->Top->car_id);

		S->Top=S->Top->next;

	}

}

void StacktoFile(Stack S){

	FILE *fp;

	Node *cur;

	char output_file[10];

	char buffer[2];

	char car_id[10];

	itoa(S.sail_num, buffer, 10);

	strcpy(output_file, "s");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	fp=fopen(output_file, "w");

	while(S.Top!=NULL){

			pop(&S, car_id);

			fprintf(fp, "%s\n", car_id);

	}

	fclose(fp);

}

// Warteschlangen Funktionen 

void add(Queue *Q, char x[]){

	Node *cur, *nn;

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

	strcpy(nn->car_id, x);

	nn->next=NULL;

	if(Q->front == NULL){

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

		Q->numElements++;

	}

	if(Q->numElements<Q->capacity){

		cur=Q->front;

		while(cur->next!=NULL){

			cur=cur->next;

		}

		cur->next=nn;

		Q->rear=nn;

		Q->numElements++;

	}

	else{

		QueuetoFile(Q);

	}

}

void delete(Queue *Q, char *car_id){

	if(Q->front==NULL){

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

	}

	else{

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

			strcpy(car_id, Q->front->car_id);

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

			Q->numElements=0;

		}

		else{

			strcpy(car_id, Q->front->car_id);

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

			Q->numElements--;

		}

	}

}

void QueuetoFile(Queue *Q){

	Node *cur;

	FILE*fp;

	int i;

	char output_file[10];

	char buffer[2];

	char car_id[10];

	itoa(Q->sail_num, buffer, 10);

	strcpy(output_file, "q");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	fp=fopen(output_file, "w");

	while(Q->front!=NULL){

		delete(Q, car_id);

		fprintf(fp, "%s\n", car_id);

	}

	Q->sail_num++;

	Q->numElements=0;

	fclose(fp);

}

Ausführungsbeispiel

Sagen wir mal wir geben (wieder) folgendes ein:

• Kapazität für S : 2
• Kapazität für Q : 1
• Autos-Datei mit namen "cars.txt" und den vorherigen 5 AutoID-Präferenz Paaren

Diese Ausführung würde folgende Dateien erzeugen:

s0.txt

MIN5689

ZZA9896

      q0.txt

      MIN5689

      q1.txt

      ZZA9896

s1.txt

KNM4545

NHI9098

      q2.txt

      KNM4545

      q3.txt

      NHI9098

s2.txt

IPO8987

      q4.txt

      IPO8987

    Damit ihr besser versteht was hier abgeht habe ich die Segel mit s-q Paaren geschrieben. Ihr könnt damit sehen wie S voll wird und dann seine Daten in Q eingeschrieben werden. Beim letzten mal reichen die Auto-ID's der Datei ja nicht aus um den Stapel voll zu machen, also sieht man wieso die Kontrolle nach der eigentlichen Lese-Schleife so wichtig ist! Die Kontrolle von Boot Q wird hier nicht verwendet da das Boot ja bereits bei dem Segeln von S voll wurde und somit ein Segeln ausgeführt wird. Diese letzte Kontrolle ist also nur von Nöten wenn S kleiner ist als Q (in Kapazität). Damit ihr die eigentliche Ausführungsreihenfolge besser versteht, solltet ihr diesen Code vielleicht auch selber mal ausführen! Aber ich glaub ich hab alles generell sehr gut und sehr präzise erklärt!

---

Referenzen:

1. https://steemit.com/programming/@drifter1/programming-c-stack-queue-exercise-using-linked-lists

     Ja nur dieser "kleine" Englische Artikel...aber ich habe trotzdem versucht alles viel kompletter gestaltet als davor, da ich dort ja nur eine Beschreibung und dann den kompletten Code gegeben hatte!

---

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

Warteschlangen und Stapel implementiert mit Verketteten Listen -> Liste, Warteschlange und Stapel mit Liste implementieren in C-Sprache.

Fortgeschrittene Listen und Warteschlangen -> Doppelt verkettete Listen (mit Implementation), Zirkuläre Listen, Vorrangwarteschlange (mit Implementation)

Fortgeschrittene Bäume -> Βinärer Suchbaum (Zusammenfassung),  AVL-Baum (mit Implementation), Rot-Schwarz (ohne Code) und 2-3-4 Bäume (ohne Code)

Stapel-Warteschlangen Übungsaufgabe mit Dynamischen Feldern -> Aufgabenbeschreibung, Lösung-Implementation in C (zutiefst) und Vollständiges Programm mit Ausführungsbeispiel

---

Schlusswort

    Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Der nächste Artikel der Serie wird über die Vergleichung von Funktionen reden, wo wir dazu die Ausführungszeit und auch Iteration-Schritte verwenden werden. Das wird euch sehr dabei helfen die effizienteste Lösung zu finden wenn ihr einen Algorithmus oder generell die Implementation in Code optimieren wollt.

Keep on drifting! ;)