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

Intro

Hallo, ich bin's @drifter2! Der heutige Artikel ist eine kleine Übungsaufgabe rund um Stapel und Warteschlangen, die ich von meinem englischen Artikel "C Stack-Queue Exercise using Dynamic Arrays" übersetzen werde. Bei dieser Aufgabe werden diese Datenstrukturen mit Dynamischen Feldern implementiert. Nächstes mal werden wir eine sehr ähnliche Aufgabe mit Verketteten Listen implementieren. Natürlich solltet ihr euch erstmal die Artikel rund um Stapel und Warteschlangen anschauen, denn ich werde nur auf die eigentliche Lösung des Problems zutiefst eingehen. Also dann fangen wir dann mal direkt an!

Aufgabenbeschreibung:

Sagen wir mal wir haben 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 muss sich zwischen einer der zwei Fähren entscheiden (wird also nur auf eine "einsteigen"), etwas das wir von einer Datei lesen werden.

Der Dateiname ist eine Eingabe des Benutzers des Programms und muss die Auto-ID (Identifikationsnummer oder auch Nummernschild) und Bootpräferenz enthalten. 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:

Die Kapazität der Boote und den Namen der Autos-Datei als Eingabe des Benutzers bekommen
Die Boote, oder besser gesagt, dessen Datenstrukturen, initialisieren
Von der Autos-Datei lesen und das Segeln beider Boote verwalten, indem man diese füllt bis sie voll sind
Wenn ein 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 per Segel, indem wir den Stapel oder die Warteschlange entleeren. Die Namen dieser Dateien sollten in der Form: s0, s1, s2, ... beim Stapel und q0, q1, q2, ... bei der Warteschlange sein.
Die Schritte 3 und 4 werden wiederholt bis kein neues Auto in der Autos-Datei ist (EOF)
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

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

Lösung-Implementation in C

Datenstrukturen

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 6
eine Segel Nummer (sailing number auf Englisch) um die richtige Nummer bei den Dateinamen zu verwenden
ein Dynamisches Auto-ID Feld-Array
Top-Index für den Stapel und Front und Rear-Index 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 top;

	char **car_id;

}Stack;

// Warteschlangen Struktur

typedef struct Queue{

	int sail_num;

	int capacity;

	int front;

	int rear;

	char **car_id;

}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 wir bereits wissen können wir die Stapel und Warteschlangen Variablen ganz normal als Struktur-Variablen definieren, aber auch als Zeiger. Bei dem heutigen Problem werden wir die Variablen ganz normal definieren und nicht als Zeiger, obwohl hier kein "Lese-Trick" gebraucht wird (wo wir die Variable ohne Adresse abgeben so das diese nur temporär in der Funktion verändert wird, um das Iterieren der Struktur zu verleichtern).

Also werden die Variablen wie folgend definiert:

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. 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:

Speicher an das dynamische Auto-ID Feld zuweisen
Top-Index auf '-1' setzen
Segelnummer auf '0' setzen

Das ganze sieht in Code wie folgend aus:

S.car_id=(char**)malloc(S.capacity*sizeof(char*)); // lines

for(i=0;i<S.capacity;i++){

	S.car_id[i]=(char*)malloc(10*sizeof(char)); // rows

S.top=-1;

S.sail_num=0;

Wie ihr sehen könnt hat jede Auto-ID eine maximale Länge von 10 (9 wenn man \0 dazuzählt), welches für unsere Autodatei ausreicht. Bei einer anderen Datei könnte das anders sein. Da könnte man z. B. auch die maximale Länge der Auto-ID am Anfang der Datei hinzufügen. Das selbe wird gleich auch bei der Warteschlange der Fall sein.

Die Warteschlange wird wie folgend initialisiert:

Speicher an das dynamische Auto-ID Feld zuweisen
Front und Rear Index auf '-1' setzen
Segelnummer auf '0' setzen

Der eigentliche Code sieht wie folgend aus:

Q.car_id=(char**)malloc(Q.capacity*sizeof(char*)); // lines

for(i=0;i<Q.capacity;i++){

	Q.car_id[i]=(char*)malloc(10*sizeof(char)); // rows

Q.front=Q.rear=-1;

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 kontrollieren wir erstmal ob der Stapel voll ist. Wenn ja dann führen wir das Segeln aus. WEnn nicht dann inkrementieren wir den Top-Index und fügen das neue Element ein.

Das sieht in Code wie folgend aus:

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

        // wenn nicht voll einfuegen

	if(S->top < (S->capacity - 1)){

		S->top++;

		strcpy(S->car_id[S->top], x);

	// wenn voll in Datei schreiben

	else{

		StacktoFile(S);

Vom Stapel rausnehmen

Beim rausnehmen sollten wir kontrollieren ob der Stapel leer ist, etwas das aber ein wenig unnötig ist da wir das auch vor der ausführen kontrollieren können. Werde ich aber trotzdem wie üblich kontrollieren. Bei dieser Implementation geben ich nicht direkt einen Wert zurück, sonder mache das direkt durch einen Parameter der Funktion, was heißt das ich den Wert dort abspeichere und das den Top-Index dekrementiere.

Das ganze sieht in Code wie folgend aus:

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

        // kontrollieren ob Stapel leer ist (unnoetig)

        if(S->top==-1){

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

        // Wert in Parameter speichern und dann Top-Index dekrementieren

	else{

		strcpy(car_id, S->car_id[S->top]);

		S->top--;

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 und schreiben bis der Top-Index einen Wert von "-1" 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. Nachdem das Segeln fertig ist sollten wir auch nicht vergessen die Segelnummer zu inkrementieren...

Der Code sieht wie folgend aus:

void StacktoFile(Stack *S){

	FILE*fp;

	int i;

	char output_file[10];

	char buffer[2];

	char car_id[10];

        // Dateinamen "erschaffen"

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

	strcpy(output_file, "s");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	// in Datei schreiben

	fp=fopen(output_file, "w");

	while(S->top>-1){ // solange nicht leer ist

			pop(S, car_id);

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

       // Segelnummer inkrementieren

	S->sail_num++;

	fclose(fp);

In Warteschlange einfügen

Um eine Auto-ID in die Warteschlange einzufügen müssen wir 3 gewisse Fälle kontrollieren. Erstmal, wenn voll wird dann direkt das Segeln ausgeführt. Wenn ganz leer müssen beide Indexes auf '0' initialisiert werden, sonst nur der Rear-Index inkrementiert werden. Nach dieser Initialisierung oder Inkrementierung fügt man dan bei dem Rear-Index das neue Element ein.

Der Code ist wie folgend:

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

	// wenn voll in Datei schreiben

	if(Q->rear == Q->capacity -1){

		QueuetoFile(Q);

		return;

       // wenn leer beide Indexe initialisieren

	else if(Q->front == -1){

		Q->front=Q->rear=0;

       // wenn nicht leer und nicht voll Rear++

	else{

		Q->rear++;

        // Einfuegung der neuen Auto-ID

	strcpy(Q->car_id[Q->rear], x);

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 Indexe auf '-1' initialisieren. Beim zweiten nur Front-Index inkrementieren. 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==-1){

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

	else{

                // einziges Element - beides '-1'

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

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

			Q->front=Q->rear=-1;

                // es gibt noch andere Elemente - Front++

		else{

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

			Q->front++;

Warteschlange Segeln ausführen

Ähnlich wie beim Stapel werden 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 auch die Segelnummer inkrementieren.

Der Code ist also:

void QueuetoFile(Queue *Q){

	FILE*fp;

	int i;

	char output_file[10];

	char buffer[2];

	char car_id[20];

        // Dateinamen "erschaffen"

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

	strcpy(output_file, "q");

	strcat(output_file, buffer);

	strcat(output_file, ".txt");

	// In Datei schreiben

	fp=fopen(output_file, "w");

	while(Q->front!=-1){

		delete(Q, car_id);

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

        // Segelnummer inkrementieren

	Q->sail_num++;

	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. Danach werden die jetzige Auto-ID immer in das richtige Boot je nach Präferenz einsortieren. Nach dem einfügen kontrollieren wir auch ob das Boot vielleicht schon voll ist.

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){

	// Boot-Praefernz ist 'S'

	if(ship=='S'){

                // Auto-ID einfuegen

		push(&S, car_id);

		// wenn voll in Datei schreiben

		if(S.top == S.capacity - 1){

			StacktoFile(&S);

	// Boot-Praefernz ist 'Q'

	else{

                // Auto-ID einfuegen

		add(&Q, car_id);

		// wenn voll in Datei schreiben

		if(Q.rear == Q.capacity -1){

			QueuetoFile(&Q);

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 Top und Front Index Werte "anschaut". Wenn '-1' ist bereits leer, wenn nicht dann sollte man ein Segeln ausführen. Danach noch die Datei schließen und das war's...

Der Code ist:

if(S.top!=-1) StacktoFile(&S);

if(Q.front!=-1) 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>

// Stapel Struktur

typedef struct Stack{

	int sail_num;

	int capacity;

	int top;

	char **car_id;

}Stack;

// Warteschlangen Struktur

typedef struct Queue{

	int sail_num;

	int capacity;

	int front;

	int rear;

	char **car_id;

}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;

	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.car_id=(char**)malloc(S.capacity*sizeof(char*)); // lines

	for(i=0;i<S.capacity;i++){

		S.car_id[i]=(char*)malloc(10*sizeof(char)); // rows

	S.top=-1;

	S.sail_num=0;

	// Warteschlange initialisieren

	Q.car_id=(char**)malloc(Q.capacity*sizeof(char*)); // lines

	for(i=0;i<Q.capacity;i++){

		Q.car_id[i]=(char*)malloc(10*sizeof(char)); // rows

	Q.front=Q.rear=-1;

	Q.sail_num=0;

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

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

		// Boot-Praefernz ist 'S'

		if(ship=='S'){

                        // Auto-ID einfuegen

			push(&S, car_id);

			// wenn voll in Datei schreiben

			if(S.top == S.capacity - 1){

				StacktoFile(&S);

		// Boot-Praefernz ist 'Q'

		else{

                        // Auto-ID einfuegen

			add(&Q, car_id);

			// wenn voll in Datei schreiben

			if(Q.rear == Q.capacity -1){

				QueuetoFile(&Q);

	// Kontrollieren ob Boote (wirklich) leer sind

	if(S.top!=-1) StacktoFile(&S);

	if(Q.front!=-1) QueuetoFile(&Q);

	fclose(fp);

	return 0;

// Stapel Funktionen

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

	if(S->top < (S->capacity - 1)){

		S->top++;

		strcpy(S->car_id[S->top], x);

	else{

		StacktoFile(S);

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

	if(S->top==-1){

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

	else{

		strcpy(car_id, S->car_id[S->top]);

		S->top--;

void StacktoFile(Stack *S){

	FILE*fp;

	int i;

	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>-1){

			pop(S, car_id);

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

	S->sail_num++;

	fclose(fp);

// Warteschlangen Funktionen

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

	if(Q->rear == Q->capacity -1){

		QueuetoFile(Q);

		return;

	else if(Q->front == -1){

		Q->front=Q->rear=0;

	else{

		Q->rear++;

	strcpy(Q->car_id[Q->rear], x);

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

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

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

	else{

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

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

			Q->front=Q->rear=-1;

		else{

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

			Q->front++;

void QueuetoFile(Queue *Q){

	FILE*fp;

	int i;

	char output_file[10];

	char buffer[2];

	char car_id[20];

	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!=-1){

		delete(Q, car_id);

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

	Q->sail_num++;

	fclose(fp);

Ausführungsbeispiel

Sagen wir mal wir geben 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

NHI9098

ZZA9896

q0.txt

MIN5689

q1.txt

KNM45454

q2.txt

IPO8987

Wie ihr sehen könnt sind die zwei Autos vom Stapel in der inversen Reihenfolge wieder raus gekommen. Bei der Warteschlange ist es immer nur 1 Auto, also sind diese nur in der Reihenfolge in der sie in der Datei drin waren wieder raus gekommen.

Referenzen:

https://steemit.com/programming/@drifter1/programming-c-stack-queue-exercise-using-dynamic-arrays

Ja nur dieser "kleine" Englische Artikel...aber ich habe trotzdem alles viel kompletter gestaltet als davor, da ich ja alles viel analytischer erklärt habe!

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)

Schlusswort

Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Wie bereits bei dem Intro erwähnt wurde werden wir nächstes mal in eine ähnliche Aufgabe rund um Stapel und Warteschlangen eingehen, bei der wir dann Verkettete Listen für die Implementierung der Datenstrukturen verwenden werden.

Keep on drifting! ;)