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!
Warteschlange als Datenstruktur
Eine Warteschlange (Queue auf Englisch) ist eine sehr nützliche und deshalb häufig benutzte Datenstruktur in Computerprogrammen. Als eine abstrakte Datenstruktur kann eine solche Warteschlange eine beliebige Menge von Objekten aufnehmen. Die zwei wesentlichen Operationen sind wieder mal das Einfügen (Enqueue) eines neuen Objekts und das Löschen (Dequeue) eines Objekts. Dabei arbeiten wir mit dem FIFO-Prinzip (First In First Out auf Englisch das "zuerst hinein zuerst hinaus" bedeutet). Deswegen wird bei 'dequeue' immer das Objekt zurückgegeben das als erstes in die Warteschlange mit 'enqueue' gelegt wurde. Der Stapel von dem wir nächstes mal reden werden, hat ein LIFO-Prinzip, was heißt das das letzt hinzugefügte Objekt als erstes zurückgegeben wird.
Wie ihr vielleicht bereits verstanden habt, handelt es sich bei dieser Datenstruktur wirklich an einer "abstrakten" Darstellung einer Warteschlange, ähnlich wie die Reihe von Kunden an einer Kasse. Natürlich wird der letze der sich an diese Schlange stellt auch als letzter bedient. Derjenige der sich als erstes angestellt hat wird als erster bedient.
Solche Strukturen werden sind bei vielen Anwendungen verwendbar wie z.B:
- Druckerschlangen - die Ausdrucke haben eine gewisse Reihe
- Tastatureingabe - die Eingaben müssen ja in der richtigen Nachfolge sein
- Multitask-Systeme - z. B. bei der Datenübergabe zwischen asynchronen Prozessen
- Breitensuche - eine Graphen-Algorithmus der den Graphen mit Hilfe einer Warteschlange iteriert
Implementation einer Warteschlange mit Feldern in C-Sprache
Ähnlich wie bei Listen und Bäumen wird eine Warteschlange in C wieder als eine Struktur (struct) definiert. Eine statische Warteschlange mit einer gewissen Kapazität kann leicht mit einem statischen Feld-Array von N-Objekten definiert werden. Natürlich muss man auch den Anfangsindex (front index auf Englisch) und Endindex (rear index) der Warteschlange abspeichern.
Damit der Code leichter ist werden wir nur eine Ganzzahl-Warteschlange (Integer-Queue) implementieren. Natürlich könnt ihr dieses Feld leicht mit einem Struktur Feld (struct array) ersetzen.
Der struct sieht wie folgend aus:
typedef struct Queue{ int q[N]; int front; int rear; }Queue;Beim initialisieren einer solchen Warteschlange muss man die front und rear "Zeiger" auf '-1' setzen, das uns zeigen wird ob die Warteschlange leer ist.
Eine solche Queue kann sehr leicht wie folgend definiert werden:
Queue Q; Das heißt das wir jetzt '.' benutzen um auf die Werte zugreifen zu können. Alle Funktionen/Operationen die aber die Warteschlange Q in irgendeiner Weise verändern, müssen aber natürlich die Speicheradresse als Parameter bekommen, was heißt das wir einen Zeiger auf eine Queue als Parameter haben werden und so wieder mal '->' benutzen müssen. Weil wir mit Feldern arbeiten werden natürlich alle Funktionen ganz einfach sein. Man muss ja nur ein neues Objekt beim Rear-Index einfügen und ein Objekt vom Front-Index nehmen.
Einfügen (Enqueue)
Da wir eine gewisse Kapazität haben, müssen wir vor dem Einfügen natürlich erstmal kontrollieren ob die Warteschlange voll ist. Da die Zwei Indexe auf '-1' initialisiert sind, müssen wir auch kontrollieren ob die Warteschlange leer ist, damit wir diese auf '0' setzen und das erste Objekte (den ersten Wert) dort abspeichern. Beim einfachsten Fall (nicht leer und nicht voll) muss man nur den Rear-Index um eins erhöhen und den neuen Wert am Rear-Index abspeichern.
Die Funktion sieht wie folgend in Code aus:
void enqueue(Queue *Q, int val){ // kontrollieren ob voll if( (Q->rear - Q->front + 1) == N){ printf("Queue is Full!\n"); return; } // kontrollieren ob leer else if(Q->front == -1){ Q->front = Q->rear = 0; } // einfachster Fall else{ // Rear-Index um eins erhoehen Q->rear++; } // Objekt am Rear-Index abspeichern Q->q[Q->rear] = val;}Löschen (Dequeue)
Beim Löschen oder Rausnehmen eines Objekts nehmen wir einfach den Wert vom Front-Index und geben diesen Wert zurück. Man muss nicht nach einem Wert suchen, da das Prinzip der Warteschlange bereits das zu löschende Objekt beschreibt. Natürlich muss man wieder erstmal kontrollieren ob die Warteschlange leer ist (geht ganz leicht mit front == '-1') und wenn ja gibt man dann meistens '-1' zurück. Der Spezialfall hier ist wenn nur ein Objekt in der Warteschlange ist, wo man dann beider Zeiger (front und rear) auf '-1' setzen muss. Beim rausnehmen eines Objekts inkrementiert man den front-Index. Das zeigt uns das der front-Index nicht immer 0 sein muss!
Der Code sieht wie folgend aus:
int dequeue(Queue *Q){ int val; // kontrollieren ob leer if(Q->front == -1){ return -1; } // Kontrollieren ob einziges Objekt else if(Q->front == Q->rear){ val = Q->q[Q->front]; Q->front = Q->rear = -1; } // Einfachster Fall else{ val = Q->q[Q->front]; Q->front++; } // Wert zurueckgeben return val; }Ausdrucken (Print)
Das Ausgeben/Ausdrucken der Werte macht nicht so viel Sinn hier, aber kann sehr leicht implementiert werden, falls man es mal braucht. Da man nicht verändert kann man direkt ein Warteschlange-Variable Q benutzen anstatt einen Pointer auf eine solche Struktur.
Das Ausdrucken kann man in zwei Weisen ausführen:
- for-Schleife von rear bis front Index
- dequeue() ausführen so lange diese Funktion nicht '-1' zurückgibt
Es ist wichtig zu verstehen das dequeue() nur die lokale Variable verändern wird und nicht diese von der main() Funktion.
Die erste Vorgehensweise sieht wie folgend aus:
void print(Queue Q){ int i; // kontrollieren ob leer if(Q.front == -1){ printf("Queue is Empty!\n"); return; } // mit for-Schleife iterieren von rear bis front for(i = Q.rear; i>=Q.front ; i--){ printf("%d ", Q.q[i]); } printf("\n"); } Mit dequeue() sieht es wie folgend aus:
void print(Queue Q){ int val; // kontrollieren ob leer if(Q.front == -1){ printf("Queue is Empty!\n"); return; } // dequeue() ausfuehren solange es Objekte gibt while((val= dequeue(&Q)) != -1){ printf("%d ", val); } printf("\n");}Ein komplettes Beispielprogramm
Hier noch ein komplettes Beispielprogramm, wo ich natürlich die Funktionen und Struktur nicht anzeige. Die Symbolische Variable N kann sehr leicht einen Wert bekommen durch:
#define N 15Der main() Funktion Code sieht wie folgend aus:
int main(){ // Warteschlange initialisieren Queue Q; Q.front = Q.rear = -1; print(Q); // 5 hinzufuegen enqueue(&Q, 5); print(Q); // 10 hinzufuegen enqueue(&Q, 10); print(Q); // Objekt-Wert rausnehmen int val; val = dequeue(&Q); if(val == -1){ printf("Queue is Empty!\n"); } else{ printf("%d\n", val); } print(Q); }Referenzen:
- http://www.uni-protokolle.de/Lexikon/Warteschlange_(Datenstruktur).html
- http://www.inf.fu-berlin.de/lehre/SS10/infb/queues.pdf
- https://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Warteschlange
- https://steemit.com/programming/@drifter1/programming-c-queues-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
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Νächstes mal werden wir mit Stapeln (Stacks) weiter machen (erstmals implementiert mit Feldern-Arrays).
Keep on drifting! ;)