Zirkuläre Warteschlange in C: Wie implementieren?

Die Daten werden in einer kreisförmigen Warteschlange in einem kreisförmigen Muster angeordnet, wobei das letzte Element mit dem ersten Element verbunden ist. Im Gegensatz zur linearen Warteschlange, in der die Aufgaben nach FIFO (First In First Out) ausgeführt werden, kann sich die Reihenfolge der Aufgabenausführung in der kreisförmigen Warteschlange ändern. Einfüge- und Löschvorgänge können an jeder Position ausgeführt werden.

Die kreisförmige Warteschlange ist effizienter als die lineare Warteschlange. In der grafischen Darstellung einer kreisförmigen Warteschlange können Sie beobachten, dass die vordere und die hintere Position verbunden sind, was es zu einem Kreis macht, in dem die Operationen immer auf FIFO-Basis ausgeführt werden. Jedes neue Element wird am hinteren Ende hinzugefügt und am vorderen Ende gelöscht. Eine kreisförmige Warteschlange hat eine bessere Auslastung und eine Zeitkomplexität von O(1).

Quelle

Anwendungen einer kreisförmigen Warteschlange

• CPU-Scheduling: Zirkuläre Warteschlangen nutzen die leeren Speicherplätze, die in den linearen Warteschlangen gefunden werden.
• Verkehrssystem: Im Verkehrssystem werden mit Hilfe der kreisförmigen Warteschlangen Ampeln im festgelegten Zeitintervall betrieben.
• Speicherverwaltung: Betriebssysteme unterhalten häufig eine Reihe von Prozessen, die zur Ausführung bereit sind oder auf das Eintreten eines bestimmten Ereignisses warten.

Lernen: C-Programm für Bubble Sorting: Bubble Sort in C

Beispielcode mit Erklärung

Zeile 1: // (1) Präprozessoren

Zeile 2: // Warteschlangenlimit auf 5 Elemente setzen

Zeile 3: #include<stdio.h>

Zeile 4: #define LIM 5

Zeile 5: // (2) Queue-Datentyp-Deklarationen

Zeile 6: // data enthält Daten; delPos, Position, an der gelöscht werden soll; Länge, nein. von

Zeile 7: // Elemente, die derzeit in der Warteschlange vorhanden sind

Zeile 8: typedef struct queue {

Zeile 9: int data[LIM], delPos, length;

Zeile 10: } Q;

Zeile 11: // (3) Globale Erklärungen

Zeile 12: // Funktionen & globale Variable q vom Typ struct queue

Zeile 13: Qq;

Zeile 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();

Zeile 15: // (4) Ruft die UI-Funktion nach der Initialisierung auf

Zeile 16: int main()

Zeile 17: {

Zeile 18: initQ();

Zeile 19: ui_Q_Ops();

Zeile 20: Rückgabe 0;

Zeile 21: }

Zeile 22: // (5) Warteschlange initialisieren

Zeile 23: void initQ()

Zeile 24: {

Zeile 25: q.Länge = 0;

Zeile 26: q.delPos = 0;

Zeile 27: }

Zeile 28: // (6) Menügesteuerte Schleife ruft korrekte Funktionen auf

Zeile 29: void ui_Q_Ops()

Zeile 30: {

Zeile 31: int choice=0;

Zeile 32: char input[16];

Zeile 33: while(choice!=4){

Zeile 34: printf(” \n ———————-\n “);

Zeile 35: printf(” 1. In Warteschlange einfügen \n “);

Zeile 36: printf(” 2. Aus Warteschlange löschen \n “);

Zeile 37: printf(” 3. Warteschlangenelemente anzeigen \n “);

Zeile 38: printf(” 4. Programm beenden \n “);

Zeile 39: printf(” Enter choice : “);

Zeile 40: if (fgets(input, 15, stdin) != NULL){

Zeile 41: if (sscanf(input, „%d“, &choice) == 1){

Zeile 42: switch(choice){

Zeile 43: Fall 1: insertQel();

Zeile 44: Pause;

Zeile 45: Fall 2: deleteQel();

Zeile 46: Pause;

Zeile 47: Fall 3: displayQels();

Zeile 48: Pause;

Zeile 49: Fall 4: Rückkehr;

Zeile 50: default: printf(“Ungültige Auswahl\n “);

Zeile 51: fortfahren;

Zeile 52: }

Zeile 53: } Sonst

Zeile 54: printf(” Ungültige Auswahl \n “);

Zeile 55: }

Zeile 56: }

Zeile 57: }

Zeile 58: // (7) In Warteschlange einfügen

Zeile 59: // Wenn die Länge gleich MAX Limit ist, ist die Warteschlange voll, andernfalls einfügen

Zeile 60: // kreisförmig mit Summenlänge und delPos-Modul von MAX Limit erreicht

Zeile 61: // und Länge erhöhen

Zeile 62: void insertQel()

Zeile 63: {

Zeile 64: int el, inspos;

Zeile 65: char input[16];

Zeile 66: if (q.length == LIM){

Zeile 67: printf(”Warteschlange ist voll \n “);

Zeile 68: zurück;

Zeile 69: }

Zeile 70: inspos = (q.delPos + q.length) % LIM;

Zeile 71: printf(” Einzufügendes Element eingeben: “);

Zeile 72: if (fgets(input, 15, stdin) != NULL){

Zeile 73: if (sscanf(input, „%d“, &el)){

Zeile 74: q.data[inspos] = el;

Zeile 75: q.length++;

Zeile 76: } Sonst

Zeile 77: printf(” Ungültige Eingabe \n “);

Zeile 78: }

Zeile 79: }

Zeile 80: // (8) Aus Warteschlange löschen

Zeile 81: // Wenn Length 0 ist, ist die Warteschlange leer, ansonsten bei delPos löschen

Zeile 82: // und dekrementiere die Länge

Zeile 83: void deleteQel()

Zeile 84: {

Zeile 85: if (q.length == 0){

Zeile 86: printf(”Warteschlange ist leer \n “);

Zeile 87: } sonst {

Zeile 88: printf(” Gelöschtes Element %d \n “, q.data[q.delPos]);

Zeile 89: q.delPos = (q.delPos + 1) % LIM;

Zeile 90: q.Länge–;

Zeile 91: }

Zeile 92: }

Zeile 93: // (9) Queue-Elemente anzeigen

Zeile 94: // Zeigen Sie kreisförmig an, indem Sie eine Schleife ausführen, die bei delPos beginnt

Zeile 95: // und Hinzufügen von Iterator und Modulus durch Max Limit

Zeile 96: void displayQels()

Zeile 97: {

Zeile 98: int i;

Zeile 99: if (q.length == 0){

Zeile 100: printf(”Warteschlange ist leer \n “);

Zeile 101: } sonst {

Zeile 102: printf(” Elemente der Warteschlange sind: “);

Zeile 103: for(i = 0; i < q.length; i++){

Zeile 104: printf(“%d “, q.data[(q.delPos+i)%LIM]);

Zeile 105: }

Zeile 106: printf(” \n “);

Zeile 107: }

Zeile 108: }

Zeile 109:

Ausgänge:

Operationen in einer kreisförmigen Warteschlange

1. insertQel() – Einfügen eines Elements in die Circular Queue

In einer zirkulären Warteschlange wird die Funktion enQueue() verwendet, um ein Element in die zirkuläre Warteschlange einzufügen. In einer kreisförmigen Warteschlange wird das neue Feature immer an der hinteren Position eingefügt. Die Funktion enQueue() nimmt einen ganzzahligen Wert als Parameter und fügt ihn in die kreisförmige Warteschlange ein. Die folgenden Schritte werden implementiert, um ein Element in die kreisförmige Warteschlange einzufügen:

Schritt 1 – Überprüfen Sie, ob die Länge der MAX-Grenze entspricht. Wenn wahr, bedeutet dies, dass die Warteschlange VOLL ist. Wenn sie VOLL ist, dann zeige „Warteschlange ist voll“ an und beende die Funktion.

Schritt 2 – Wenn es NICHT VOLL ist, dann fügen Sie den Wert ein, der kreisförmig mit der Summenlänge und dem delPos-Modul durch MAX Limit erreicht wird, und erhöhen Sie die Länge

2. deleteQel() – Löschen eines Elements aus der Circular Queue

In einer zirkulären Warteschlange ist deQueue() eine Funktion, die verwendet wird, um ein Element aus der zirkulären Warteschlange zu löschen. In einer kreisförmigen Warteschlange wird das Element immer an der vorderen Position gelöscht. Die deQueue()-Funktion nimmt keinen Wert als Parameter. Die folgenden Schritte werden implementiert, um ein Element aus der kreisförmigen Warteschlange zu löschen…

Schritt 1 – Überprüfen Sie, ob die Warteschlange LEER ist. (vorne == -1 && hinten == -1)

Schritt 2 – Wenn es LEER ist, dann zeigen Sie „Warteschlange ist leer“ an und beenden Sie die Funktion.

Schritt 3 – Wenn es NICHT LEER ist, dann zeigen Sie gelöschte Elemente entsprechend den Positionen an. Nachdem jedes Element hinzugefügt wurde, fahren Sie mit dem nächsten Positions-Mod-Warteschlangenlimit fort.

3. displayQels() – Zeigt die Queue-Elemente an, die in der Circular Queue vorhanden sind. Die folgenden Schritte werden implementiert, um die Elemente einer kreisförmigen Warteschlange anzuzeigen:

Schritt 1 – Überprüfen Sie, ob die Warteschlange LEER ist.

Schritt 2 – Wenn die Länge 0 ist, ist sie LEER, dann „Warteschlange ist leer“ anzeigen und die Funktion beenden.

Schritt 3 – Wenn es NICHT LEER ist, definieren Sie eine Integer-Variable „i“.

Schritt 4 – Setzen Sie i auf 0.

Schritt 5 – Wieder Elemente nach Position anzeigen und Wert um eins erhöhen (i++). Wiederholen Sie dasselbe, bis 'i <q.length' FALSCH wird.

Circular Queue kann auch mit der verknüpften Liste implementiert werden. Die folgenden Algorithmen sind:

• Algorithmus für Enqueue:

if (FRONT == NULL) // Einfügen in eine leere Warteschlange

FRONT = HINTEN = neuer Knoten

Ende wenn

anders

REAR -> next = newNode // Einfügen nach dem letzten Element

REAR = neuer Knoten

sonst enden

HINTEN -> weiter = VORNE

Enqueue beenden

• Algorithmus für Dequeue:

if(FRONT == NULL) // Bedingung für Unterlauf

„Warteschlangenunterlauf“ drucken

Warteschlange beenden

Ende wenn

else if(FRONT == REAR) // Die Warteschlange enthält nur einen Knoten

temp = FRONT -> Daten

kostenlos (zeitlich)

FRONT = FRONT -> weiter

HINTEN -> weiter = VORNE

Ende wenn

else if (FRONT == N – 1) // Wenn FRONT der letzte Knoten ist

front = 0 // FRONT zum ersten Knoten machen

Ende wenn

Warteschlange beenden

Lesen Sie auch: Python Vs C: Vollständiger Side-by-Side-Vergleich

Fazit

Datenstrukturen und Algorithmen sind nicht nur in der C-Programmierung, sondern auch in anderen Sprachen von großer Bedeutung. Sein Wert ist beispiellos, und für Themen von solcher Bedeutung ist es besser, in Kurse zu investieren, die von Experten entwickelt und betreut werden, die eine hervorragende Ergänzung Ihres Portfolios darstellen. upGrad bietet eine große Auswahl an leistungsstarken Kursen, die nicht nur Ihre Fähigkeiten verbessern, sondern auch starke Grundpfeiler bilden.

Es wurde vom hoch angesehenen IIIT-B entwickelt, das nicht nur Inhalte in Premiumqualität bereitstellt, sondern Sie auch zu einem Teil eines starken Netzwerks macht, in dem Sie sich mit Menschen verbinden, die sich auf demselben Karriereweg entwickeln, sowie mit Branchenexperten lösen Sie Ihre Zweifel und unterstützen Sie jedes Mal.

Es würde Ihnen helfen, ihre Mentalität und ihren Denkprozess kennenzulernen. Und eines der einzigartigen Dinge, die Sie bei upGrad bekommen, ist, dass Sie sich für EMI-Optionen entscheiden und Ihre Taschen schonen können.

Wir hoffen, dass Sie eine ausgezeichnete Gelegenheit zum Lernen bei der Durchführung dieser C-Projekte haben werden. Wenn Sie daran interessiert sind, mehr zu erfahren und Mentoring von Branchenexperten benötigen, sehen Sie sich das PG-Diplom in Full-Stack-Softwareentwicklung von upGrad & IIIT Banglore an.