Stapel und Warteschlange in C++

Einführung in Stapel und Warteschlangen in C++

Stacks und Warteschlangen sind häufig verwendete Datenstrukturen in C++ und werden häufig in Programmen verwendet. In diesem Artikel werden die Konzepte, Verwendungs- und Anwendungsszenarien von Stapeln und Warteschlangen ausführlich vorgestellt.

1. Das Konzept von Stack

Stack (Stack) ist eine lineare Datenstruktur mit den Merkmalen „First in, last out“. Im Stapel befinden sich die in den Stapel verschobenen Daten näher am unteren Ende des Stapels; die später in den Stapel verschobenen Daten befinden sich näher am oberen Ende des Stapels.

Die Hauptoperationen des Stapels sind Push und Pop. Beim Pushen werden Daten zum Stapel hinzugefügt, beim Poppen werden Daten aus dem Stapel gelöscht. Der Stapel verfügt außerdem über zwei wichtige Spezialoperationen: Anzeigen des obersten Elements des Stapels (oben) und Bestimmen, ob der Stapel leer ist (leer).

Die Anwendungsszenarien des Stapels sind sehr breit, beispielsweise ist die Verwendung des Stapels an Funktionsaufrufen beteiligt. Wenn eine Funktion aufgerufen wird, werden ihre Parameter, lokalen Variablen und andere Informationen auf den Stapel gelegt. Wenn die Funktionsausführung endet, werden diese Informationen vom Stapel entfernt und in den Zustand vor dem Funktionsaufruf zurückversetzt.

2. Das Konzept der Warteschlange

Queue (Warteschlange) ist ebenfalls eine lineare Datenstruktur mit den Merkmalen „First In, First Out“. In der Warteschlange befinden sich die Daten, die früher in die Warteschlange gestellt werden, näher am Anfang der Warteschlange; die Daten, die später in die Warteschlange gestellt werden, befinden sich näher am Ende der Warteschlange.

Die Hauptoperationen der Warteschlange sind das Einreihen und Entfernen aus der Warteschlange. Das Betreten der Warteschlange bedeutet das Hinzufügen von Daten am Ende der Warteschlange, während das Entfernen aus der Warteschlange das Löschen von Daten am Anfang der Warteschlange bedeutet. Die Warteschlange verfügt außerdem über zwei wichtige Sonderoperationen: Anzeigen des Kopfelements (vorne) und Bestimmen, ob die Warteschlange leer ist (leer).

Warteschlangen werden beispielsweise auch häufig bei der Prozessplanung im Betriebssystem verwendet, um auf die Ausführung wartende Prozesse zu speichern. Wenn Systemressourcen frei sind, wird ein Prozess vom Anfang der Warteschlange genommen und ausgeführt, bis alle Aufgaben abgeschlossen sind.

3. Anwendungsbeispiele für Stapel und Warteschlangen

1. Klammer-Matching

Bei der Programmierung ist es oft notwendig, festzustellen, ob die Klammern in einer Zeichenfolge übereinstimmen. Wenn Sie beispielsweise beim Schreiben eines Python-Programms überprüfen müssen, ob der Codeblock korrekt eingerückt ist, können Sie dies mithilfe des Stapels erreichen.

Die spezifische Implementierungsmethode besteht darin, jedes Zeichen in der Zeichenfolge zu durchlaufen und es auf den Stapel zu verschieben, wenn eine linke Klammer auftritt. Wenn eine rechte Klammer angetroffen wird, wird das oberste Element des Stapels zum Abgleich entfernt. Wenn die Übereinstimmung erfolgreich ist, fahren Sie mit der Durchquerung fort; andernfalls wird eine Fehlermeldung zurückgegeben.

2. Prozessplanung

Im Betriebssystem ist es notwendig, eine einheitliche Planung und Koordination von Prozessen zu erreichen. Zu diesem Zeitpunkt kann eine Warteschlange zum Speichern von Prozessen verwendet werden, die auf ihre Ausführung warten, und das Betriebssystem bestimmt die Priorität und Ausführungsreihenfolge.

Die spezifische Implementierungsmethode besteht darin, jeden Prozess in eine Datenstruktur zu abstrahieren, einschließlich Prozessnummer, Priorität und anderen Informationen. Stellen Sie diese Prozesse in eine Warteschlange und führen Sie dann die Prozesse in der Warteschlange nacheinander aus. Wenn ein Prozess seine Aufgabe abschließt, wird er aus der Warteschlange entfernt, bis die Warteschlange leer ist.

4. Implementierung von Stacks und Warteschlangen in C++

In C++ können Sie die von der Standardbibliothek bereitgestellten Containerklassen verwenden, um Stacks und Warteschlangen zu implementieren.

1. Implementierung des Stacks

Der Stack kann mit der Containerklasse std::stack implementiert werden.

std::stack ist eine Vorlagenklasse, die die Angabe des Elementtyps und des zugrunde liegenden Containertyps erfordert. Wenn der zugrunde liegende Containertyp nicht angegeben ist, wird standardmäßig std::deque als zugrunde liegender Container verwendet.

Das Folgende ist ein Beispiel für eine einfache Stack-Implementierung:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top() << std::endl; // 输出3

    s.pop();

    std::cout << s.top() << std::endl; // 输出2

    while (!s.empty()) {
        s.pop();
    }

    return 0;
}

2. Queue-Implementierung

Queue kann mithilfe der Containerklasse std::queue implementiert werden.

std::queue ist ebenfalls eine Vorlagenklasse und muss den Elementtyp und den zugrunde liegenden Containertyp angeben. Wenn der zugrunde liegende Containertyp nicht angegeben ist, wird standardmäßig std::deque als zugrunde liegender Container verwendet.

Das Folgende ist ein einfaches Beispiel für die Implementierung einer Warteschlange:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << q.front() << std::endl; // 输出1

    q.pop();

    std::cout << q.front() << std::endl; // 输出2

    while (!q.empty()) {
        q.pop();
    }

    return 0;
}

Zusammenfassung

Wie aus der obigen Einführung ersichtlich ist, sind Stapel und Warteschlangen sehr praktische Datenstrukturen, die uns bei der Lösung vieler praktischer Probleme helfen können. Bei der Programmierung kann die Beherrschung der Nutzungs- und Implementierungsprinzipien dieser beiden Datenstrukturen die Effizienz und Zuverlässigkeit des Programms verbessern.

Das obige ist der detaillierte Inhalt vonStapel und Warteschlange in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!