Verwendung von std::stack, std::queue und std::priority_queue in C++

Die C++-Standardbibliothek stellt stack, queue und priority_queue bereit, um verschiedene lineare Datenstrukturen komfortabel nutzen zu können. Diese Strukturen folgen den klassischen Modellen: LIFO (Last-In First-Out), FIFO (First-In First-Out) und prioritätsbasierter Verarbeitung. Dieser Artikel erklärt die Funktionsweise, Einsatzgebiete und demonstriert Beispielimplementierungen.

1) Was ist stack? (LIFO-Struktur)

std::stack arbeitet nach dem LIFO-Prinzip (Last-In First-Out). Nur das oberste Element (top) kann gelesen oder entfernt werden.

• push() → fügt ein Element oben hinzu
• pop() → entfernt das oberste Element
• top() → liefert das oberste Element
• empty() → prüft, ob der Stack leer ist
• size() → Anzahl der Elemente

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> st;

    st.push(10);
    st.push(20);
    st.push(30);

    cout << "Top: " << st.top() << endl; // 30

    st.pop(); // 30 wird entfernt

    cout << "Top: " << st.top() << endl; // 20
}

Einsatzgebiete: Undo-Funktionen, Klammerüberprüfung, Call-Stack-Simulation.

2) Was ist queue? (FIFO-Struktur)

std::queue folgt dem FIFO-Prinzip: Das zuerst hinzugefügte Element wird zuerst entfernt.

• push() → fügt ein Element hinten an
• front() → liefert das erste Element
• back() → liefert das letzte Element
• pop() → entfernt das erste Element
• empty(), size()

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<string> q;

    q.push("Johann");
    q.push("Emily");
    q.push("Michael");

    cout << "Front: " << q.front() << endl; // Johann
    cout << "Back: " << q.back() << endl;   // Michael

    q.pop(); // Johann wird entfernt

    cout << "Front: " << q.front() << endl; // Emily
}

Einsatzgebiete: Aufgabenwarteschlangen, Prozesspipelines, Nachrichtensysteme.

3) Was ist priority_queue?

std::priority_queue ist eine prioritätsbasierte Warteschlange, die Elemente automatisch sortiert. Standardmäßig handelt es sich um einen Max-Heap: Das größte Element befindet sich immer oben.

• push() → fügt ein Element ein
• top() → liefert das höchstpriorisierte Element
• pop() → entfernt dieses Element
• empty(), size()

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(50);
    pq.push(10);
    pq.push(80);
    pq.push(20);

    cout << "Top: " << pq.top() << endl; // 80

    pq.pop(); // 80 wird entfernt

    cout << "Top: " << pq.top() << endl; // 50
}

Einsatzgebiete: Dijkstra-Algorithmus, CPU-Scheduling, prioritätsbasierte Aufgabenverwaltung.

4) priority_queue als Min-Heap verwenden

Standardmäßig ist priority_queue ein Max-Heap. Für einen Min-Heap muss greater<> verwendet werden.

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> minpq;

    minpq.push(40);
    minpq.push(10);
    minpq.push(30);

    cout << "Top: " << minpq.top() << endl; // 10
}

5) Praktische Beispiele

a) Klammerprüfung mit stack

#include <stack>
#include <string>
#include <iostream>
using namespace std;

bool check(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    cout << check("((a+b)*(c-d))"); // 1
}

b) Bankschlangen-Simulation mit queue

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<string> customers;

    customers.push("Johann");
    customers.push("Emily");
    customers.push("David");

    while (!customers.empty()) {
        cout << "Bedient wird: " << customers.front() << endl;
        customers.pop();
    }
}

c) Aufgabenpriorisierung mit priority_queue

#include <queue>
#include <iostream>
using namespace std;

int main() {
    priority_queue<pair<int,string>> tasks;

    tasks.push({3, "Niedrige Priorität"});
    tasks.push({10, "Hohe Priorität"});
    tasks.push({5, "Mittlere Priorität"});

    while (!tasks.empty()) {
        cout << "Aufgabe: " << tasks.top().second << endl;
        tasks.pop();
    }
}

6) Wann sollte man welche Struktur verwenden?

• stack: Undo-Mechanismen, Ausdrucksanalyse, Call-Stacks
• queue: Ablaufsteuerung, Job-Warteschlangen, Nachrichtenwarteschlangen
• priority_queue: prioritätsbasierte Aufgaben, Algorithmen, Sortiermechanismen

Die Wahl der richtigen Struktur verbessert sowohl die Leistung als auch die Lesbarkeit des Codes.

7) TL;DR

Ähnliche Artikel