In der Informatik ist eine Warteschlange eine lineare Datenstruktur, bei der die Komponenten nach dem FIFO-Prinzip (First In, First Out) an einem Ende platziert und am anderen Ende entfernt werden. Diese Datenstruktur kann zum Steuern eines Aktionsablaufs oder zum Speichern von Daten verwendet werden. C ist eine Computersprache mit Warteschlangenfunktionen, die in Form von Arrays oder verknüpften Listen integriert sind.
Eigenschaften:
- Eine Warteschlange ist eine Art lineare Datenstruktur, die aus einem Array oder einer verknüpften Liste erstellt werden kann.
- Elemente werden nach hinten in die Warteschlange verschoben, während sie nach vorne entfernt werden.
- Enqueue (ein Element nach hinten hinzufügen) und Dequeue (ein Element nach vorne entfernen) sind zwei Warteschlangenoperationen.
- Wenn Elemente häufig hinzugefügt und entfernt werden, kann eine Warteschlange als kreisförmige Warteschlange aufgebaut werden, um eine Speicherverschwendung zu vermeiden.
Array verwenden:
Um eine Warteschlange in C mithilfe eines Arrays zu implementieren, definieren Sie zunächst die maximale Größe der Warteschlange und deklarieren Sie ein Array dieser Größe. Die vorderen und hinteren Ganzzahlen wurden jeweils auf 1 gesetzt. Die vordere Variable repräsentiert das vordere Element der Warteschlange und die hintere Variable repräsentiert das hintere Element.
Bevor wir das neue Element an die endgültige Position der Warteschlange verschieben, müssen wir die Variable back um 1 erhöhen. Die Warteschlange ist jetzt voll und es können keine weiteren zusätzlichen Elemente hinzugefügt werden, wenn die hintere Position die maximale Kapazität der Warteschlange erreicht. Wir fügen ein Element am Anfang der Warteschlange hinzu und erhöhen die vordere Variable um eins, nur um ein Element aus der Warteschlange zu entfernen. Wenn die vordere und hintere Position gleich sind und keine Komponenten mehr gelöscht werden können, können wir sagen, dass die Warteschlange leer ist.
Unten sehen Sie eine Instanz einer in C geschriebenen Warteschlange, die ein Array verwendet:
Liste auf Java
Programmiersprache C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Die Ausgabe des Codes wird sein:
Ausgabe:
10 20 30 Queue is empty-1
Erläuterung:
- Zuerst stellen wir die drei Elemente 10, 20 und 30 in die Warteschlange.
- Dann entfernen wir das vordere Element der Warteschlange, das 10 ist, aus der Warteschlange und drucken es aus.
- Als nächstes entfernen wir das vordere Element der Warteschlange, nämlich 20, und drucken es erneut aus.
- Dann entfernen wir das vordere Element der Warteschlange, also 30, aus der Warteschlange und drucken es erneut aus.
- Schließlich führen wir aus einer leeren Warteschlange einen Dequeue-Vorgang durch, der „Warteschlange ist leer“ ausgibt und -1 zurückgibt.
Verwenden einer verknüpften Liste:
Ein weiterer alternativer Ansatz zum Aufbau einer Warteschlange in der Programmiersprache C ist die Verwendung einer verknüpften Liste. Jeder der Knoten in der Warteschlange wird mit dieser Methode durch einen Knoten ausgedrückt, der den Elementwert und einen Zeiger auf den folgenden Knoten in der Warteschlange enthält. Um den Überblick über den ersten bzw. letzten Knoten in der Warteschlange zu behalten, werden vordere und hintere Zeiger verwendet.
Java-Array zum Auflisten
Wir erstellen einen neuen Knoten mit dem Elementwert und setzen seinen nächsten Zeiger auf NULL, um ein Element zur Warteschlange hinzuzufügen. Auf den neuen Knoten setzen wir die vorderen und hinteren Zeiger, wenn die Warteschlange leer ist. Wenn nicht, aktualisieren wir den hinteren Zeiger und setzen den nächsten Zeiger des alten hinteren Knotens so, dass er auf den neuen Knoten zeigt.
Beim Löschen eines Knotens aus einer Warteschlange wird zuerst der vorhergehende Knoten gelöscht, dann wird der vordere Zeiger auf den nachfolgenden Knoten in der Warteschlange aktualisiert und schließlich wird der Speicher freigegeben, den der entfernte Knoten belegt hat. Wenn der Frontzeiger nach dem Entfernen NULL ist, ist die Warteschlange leer.
Hier ist ein Beispiel für eine in C implementierte Warteschlange mithilfe einer verknüpften Liste:
Programmiersprache C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Die Ausgabe des Codes wird sein:
Ausgabe:
10 20 30 Queue is empty-1
Erläuterung:
- Zuerst stellen wir die drei Elemente 10, 20 und 30 in die Warteschlange.
- Dann entfernen wir das vordere Element der Warteschlange, das 10 ist, aus der Warteschlange und drucken es aus.
- Als nächstes entfernen wir das vordere Element der Warteschlange, nämlich 20, und drucken es erneut aus.
- Dann entfernen wir das vordere Element der Warteschlange, also 30, aus der Warteschlange und drucken es erneut aus.
- Schließlich versuchen wir, aus der leeren Warteschlange auszusteigen, was die Meldung „Warteschlange ist leer“ ausgibt und -1 zurückgibt.
Vorteile:
- Warteschlangen sind besonders nützlich für die Implementierung von Algorithmen, die die Verarbeitung von Elementen in einer präzisen Reihenfolge erfordern, wie z. B. Breitensuche und Aufgabenplanung.
- Da Warteschlangenoperationen eine Zeitkomplexität von O(1) haben, können sie selbst bei großen Warteschlangen schnell ausgeführt werden.
- Warteschlangen sind besonders flexibel, da sie einfach über ein Array oder eine verknüpfte Liste implementiert werden können.
Nachteile:
- Eine Warteschlange kann im Gegensatz zu einem Stapel nicht mit einem einzelnen Zeiger erstellt werden, wodurch die Warteschlangenimplementierung etwas aufwändiger wird.
- Wenn die Warteschlange als Array aufgebaut ist, könnte sie sich schnell füllen, wenn zu viele Elemente hinzugefügt werden, was zu Leistungsproblemen oder möglicherweise zu einem Absturz führen kann.
- Bei Verwendung einer verknüpften Liste zur Implementierung der Warteschlange kann der Speicheraufwand jedes Knotens erheblich sein, insbesondere bei kleinen Elementen.
Abschluss:
Zu den Anwendungen, die Warteschlangen, eine wichtige Datenstruktur, verwenden, gehören unter anderem Betriebssysteme, Netzwerke und Spiele. Sie eignen sich ideal für Algorithmen, die Elemente in einer bestimmten Reihenfolge verarbeiten müssen, da sie mithilfe eines Arrays oder einer verknüpften Liste einfach zu erstellen sind. Allerdings haben Warteschlangen Nachteile, die bei der Auswahl einer Datenstruktur für eine bestimmte Anwendung berücksichtigt werden müssen, wie z. B. Speicherverbrauch und Implementierungskomplexität.