So implementieren Sie eine Array-basierte Warteschlange mithilfe der C-Sprache

In der Programmierung ist die Warteschlange eine häufig verwendete Datenstruktur. Viele Programmiersprachen haben ihre eigenen Warteschlangenimplementierungen, wie z. B. Queue in Java und Deque in Python. In der Sprache C gibt es jedoch keine vorgefertigte Warteschlangenimplementierung. Daher müssen wir in der C-Sprache die Warteschlange implementieren, indem wir ein Array definieren und Zeiger und andere Tricks verwenden.

In diesem Artikel stellen wir vor, wie man eine Array-basierte Warteschlange mit der Sprache C implementiert.

1. Definieren Sie eine Warteschlangenstruktur

Wir können Warteschlangenoperationen implementieren, indem wir eine Warteschlangenstruktur definieren. Diese Warteschlangenstruktur umfasst Informationen wie die Größe der Warteschlange, Kopf- und Endzeiger, Elementdaten usw.

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

Im obigen Code definieren wir eine MAX_SIZE-Konstante, um die maximale Größe der Warteschlange darzustellen, und deklarieren eine Warteschlange mit dem Namen Queue, indem wir eine Struktur definieren.

Unter diesen stellt die Größe die Größe der Warteschlange dar, die Vorderseite stellt den Warteschlangenkopfzeiger dar, die Rückseite stellt den Warteschlangenendzeiger dar und Daten sind ein Array zum Speichern von Elementen.

2. Warteschlangeninitialisierungsvorgang

Bei der Implementierung der Warteschlange muss zuerst der Warteschlangeninitialisierungsvorgang durchgeführt werden, um die korrekte Verwendung der Warteschlange sicherzustellen.

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

Im obigen Code definieren wir eine Initialisierungsfunktion init, die den Zeiger q, der auf die Warteschlangenstruktur zeigt, als Parameter akzeptiert und die Größe der Warteschlange auf 0, den Kopfzeiger auf 0 und den Endzeiger auf setzt - 1, was anzeigt, dass die Warteschlange leer ist.

3. Element-Einreihvorgang

Der Einreihvorgang der Warteschlange besteht darin, ein Element am Ende der Warteschlange zu platzieren. Die Implementierung hier besteht darin, das Element am Ende der Array-Daten hinzuzufügen und die Position des hinteren Zeigers zu aktualisieren .

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

Bestimmen Sie im obigen Code zunächst, ob die Warteschlange voll ist, und geben Sie 0 zurück, um anzuzeigen, dass das Einfügen fehlgeschlagen ist. Andernfalls verschieben Sie den hinteren Zeiger um ein Bit zurück und weisen Sie den Elementwert dem Ende der Daten zu Array und Die Warteschlangengröße wird um 1 erhöht und schließlich wird 1 zurückgegeben, um eine erfolgreiche Einfügung anzuzeigen.

4. Vorgang zum Entfernen von Elementen aus der Warteschlange

Der Vorgang zum Entfernen aus der Warteschlange besteht darin, das Element an der Spitze der Warteschlange zu entfernen und die Position des vorderen Zeigers zu aktualisieren. Die hier umgesetzte Idee besteht darin, den Elementwert an der ersten Position in den Daten zurückzugeben, den vorderen Zeiger um ein Bit nach hinten zu verschieben und gleichzeitig die Größe der Warteschlange zu aktualisieren.

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

Bestimmen Sie im obigen Code zunächst, ob die Warteschlange leer ist. Wenn sie leer ist, geben Sie -1 zurück, um anzuzeigen, dass die Warteschlange leer ist. Andernfalls geben Sie den Elementwert an der ersten Position in den Daten zurück und verschieben Sie sie Zeiger um ein Bit zurück. Die Warteschlange verringert die Größe um 1 und gibt den Elementwert zurück.

5. Testen der Implementierung der Warteschlange

Da wir nun verschiedene Operationen der Warteschlange implementiert haben, testen wir sie:

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

Im obigen Testcode definieren wir zunächst eine Warteschlange mit dem Namen myQueue und initialisieren sie mit der Funktion init. Anschließend fügen wir mit der Enqueue-Funktion die Zahlen 1, 2 und 3 in die Warteschlange ein und mit der Dequeue-Funktion entfernen wir Elemente aus der Warteschlange und geben sie auf dem Bildschirm aus.

Die Ausgabe hier sollte wie folgt lauten:

1
2
3

6. Zusammenfassung

In diesem Artikel haben wir gelernt, wie man eine Array-basierte Warteschlange mit der Sprache C implementiert. Durch die Definition einer Warteschlangenstruktur und zugehöriger Betriebsfunktionen können wir Elemente in der Warteschlange einfach hinzufügen, löschen und darauf zugreifen. Obwohl es mühsam ist, Zeiger zum Implementieren von Warteschlangen zu verwenden, kann diese Methode uns helfen, die Prinzipien von Warteschlangen besser zu verstehen, und ist eine große Hilfe beim Erlernen von Datenstrukturen und Algorithmen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine Array-basierte Warteschlange mithilfe der C-Sprache. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!