Bild Referenz: 
Intro
Hallo, ich bin's @drifter2! Das heutige Thema sind Warteschlangen die wir erstmals mit Feldern implementieren werden und die am englischen Artikel "C Queues using Arrays" basiert sind, der von meinen Hauptaccount @drifter1 ist. Wie immer werde ich nicht nur Übersetzen sondern auch mehr Informationen hinzufügen um den Artikel kompletter zu gestalten. Also dann fangen wir dann mal an!
Stapel als Datenstruktur
Stapel sind bekannt aus dem Alltagsleben als Tellerstapel, Bücherstapel usw. Bei Stapeln hat man (in der Regel) einen direkten Zugriff nur auf das oberste Stapelobjekt (und nimmt also nur das oberste Object weg), legt ein neues Objekt oben auf den Stapel. Das letzt hinzugefügte Stapelelement wird dadurch als erstes wieder weggenommen. Ein Stapel als Datenstruktur arbeitet also nach dem LIFO-Prinzip (Last In, First Out was auf Deutsch "Letzer drinne, erster raus" heißt).
Die typischen Operationen auf solche Stapel sind:
- peek() oder top() -> Lesen des obersten Objekts ohne es zu entfernen
- pop() -> Lesen des obersten Objekts und gleichzeitiges Entfernen
- push(e) ->Einfügen eines neuen Objekts oben auf den Stapel
- search() -> Suche nach einem Objekt und Rückgabe der Position (von oben gezählt - Tiefe)
Das erste könnt ihr ganz leicht von pop() implementieren und das letzte ist für mich nicht so logisch, aber ich werde trotzdem durch die Elemente des Stapels iterieren und diese ausdrucken (print), also könnt ihr diese Funktion dann ein bisschen verändern um eine Suche zu implementieren.
Implementation eines Stapels mit Feldern in C-Sprache
In C kann man diese Datenstruktur wieder sehr leicht mit Hilfe einer Struktur (struct) implementieren. Diese Struktur muss natürlich folgendes enthalten:
- ein statisches Feld-Array das unsere Stapelelemente abspeichert (Ganzzahlen für uns)
- den obersten Index (top index auf Englisch)
[natürlich ist das die Feld Implementierung]
Das sieht in Code wie folgend aus:
typedef struct Stack{ int s[N]; int top;}Stack;Der Top-Index wird auf '-1' initialisiert, so das wir wissen ob der Stapel leer ist!
Da wir diese Struktur verändern werden die pop() und push() Funktionen natürlich einen Zeiger-Parameter haben. Die eigentliche Stapel-Variable muss aber nicht unbedingt auch ein Zeiger sein, da wir die Adresse benutzen können. Beim Ausdrucken der Stapelobjekte können wir wieder mal den Stapel direkt abgeben so das wir die pop() Funktion anwenden können, ohne den eigentlichen Stapel zu verändern!
Also fangen wir dann mal mit den Funktionen an!
Einfügen (Push)
Beim Einfügen müssen wir nur kontrollieren ob der Stapel vielleicht voll ist. Mit der Feld-Implementierung haben wir ja ne gewisse Kapazität! Die eigentliche Operation geht ganz leicht. Man muss nur den Top Index inkrementieren (eins steigern) und dann das neue Objekt oder den neuen Wert bei diesem Index einfügen.
Der Code dieser Funktion sieht wie folgend aus:
void push(Stack *S, int val){ // kontrollieren ob Stapel voll ist if((S->top + 1) == N){ printf("Stack is Full!\n"); return; } // Top-Index inkrementieren S->top++; // Neues Objekt beim Top-Index einfuegen S->s[S->top] = val;}Löschen-Entfernen (Pop)
Beim Löschen-Entfernen eines Objekts muss man natürlich erstmal kontrollieren ob der Stapel leer ist. Das geht ganz leicht da wir ja den Index-Wert '-1' bereits als "leer" bezeichnet haben. Wenn leer werde ich hier z.B. '-1' zurückgeben. Vor dem löschen muss man natürlich das Objekt oder den Wert erstmals bei einer anderen temporären Variable abspeichern. Danach kann muss man einfach den Top-Index dekrementieren und das Objekt oder den Wert zurückgeben.
Der Code sieht wie folgend aus:
int pop(Stack *S){ int val; // Kontrollieren ob Stapel leer ist if(S->top == -1){ return -1; } // Wert/Objekt temporaer abspeichern val = S->s[S->top]; // Top-Index dekrementieren S->top--; // Wert/Objekt zurueckgeben return val; }Für die Funktion peek() oder top() die ich vorher erwähnt habe, muss man einfach nur den Wert zurückgeben, ohne den Top-Index zu dekrementieren.
Ausdrucken (Print)
Zuletzt noch eine Funktion für die Iteration oder das Ausdrucken generell eines Stapels. Wie ich vorhin schon gesagt hatte, kann man hierfür nur die Variable als Parameter abgeben, so das man den eigentlichen Stapel nicht verändert. Dadurch kann man ganz leicht die pop() Funktion wieder und wieder ausführen bis der Stapel leer ist. Natürlich könntet ihr auch direkt eine for-Schleife (loop) definieren die vom 'top' bis zum 0-Index geht.
Das erste sieht in Code wie folgend aus:
void print(Stack S){ int val; // Kontrollieren ob Stapel leer ist if(S.top == -1){ printf("Stack is Empty!\n"); return; } // Pop() ausfuehren solange Stapel nicht leer ist while((val = pop(&S)) != -1){ printf("%d ", val); } printf("\n");}Ein komplettes Beispielprogramm
Damit ihr alles noch besser versteht, hier noch ein komplettes Beispielprogramm. Die Funktionen werde ich wieder auslassen und vergisst nicht die Symbolische Variable N zu definieren mit "#define N Wert"!
int main(){ // Stapel initialiseren Stack S; S.top = -1; print(S); // 3 einfuegen push(&S, 5); print(S); // 7 einfuegen push(&S, 10); print(S); // 2 einfuegen push(&S, 2); print(S); // vom Stapel entfernen int val; val = pop(&S); if(val == -1){ printf("Queue is Empty!\n"); } else{ printf("%d\n", val); } print(S); }Referenzen:
- https://www.inf-schule.de/algorithmen/listen/stapel/konzept_stapel
- http://www.scalingbits.com/java/javakurs2/datenstrukturen/stapel
- https://cg.informatik.uni-freiburg.de/course_notes/info2_08_datenstrukturen.pdf
- https://steemit.com/programming/@drifter1/programming-c-stacks-using-arrays
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
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Νächstes mal werden wir Warteschlangen mit Hilfe von Listen implementieren (so das diese wirklich dynamisch werden)!
Keep on drifting! ;)