Utilisation de std::stack, std::queue et std::priority_queue en C++

La bibliothèque standard C++ fournit stack, queue et priority_queue pour manipuler facilement différents types de structures linéaires. Ces structures reposent sur trois modèles classiques : LIFO (Last-In First-Out), FIFO (First-In First-Out) et un modèle basé sur la priorité. Cet article explique le fonctionnement de chacune, leurs cas d’usage, ainsi que des exemples pratiques.

1) Qu’est-ce que stack ? (Structure LIFO)

std::stack fonctionne selon le principe LIFO (Last-In First-Out). Seul l’élément du sommet (top) peut être consulté, ajouté ou retiré.

• push() → ajoute un élément au sommet
• pop() → retire l’élément du sommet
• top() → retourne l’élément du sommet
• empty() → indique si la pile est vide
• size() → nombre d’éléments

#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(); // retire 30

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

Cas d’utilisation : fonctionnalités d’annulation, vérification de parenthèses, pile d’appels.

2) Qu’est-ce que queue ? (Structure FIFO)

std::queue suit le modèle FIFO : le premier élément inséré est le premier retiré.

• push() → ajoute un élément à l’arrière
• front() → retourne le premier élément
• back() → retourne le dernier élément
• pop() → retire le premier élément
• empty(), size()

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

int main() {
    queue<string> q;

    q.push("Jean");
    q.push("Émilie");
    q.push("Michel");

    cout << "Front: " << q.front() << endl; // Jean
    cout << "Back: " << q.back() << endl;   // Michel

    q.pop(); // retire Jean

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

Cas d’utilisation : files d’attente, pipelines de tâches, systèmes de messagerie.

3) Qu’est-ce que priority_queue ?

std::priority_queue est une file à priorité qui trie automatiquement les éléments. Par défaut, c’est un max-heap : l’élément le plus grand/d’alerte priorité se trouve en tête.

• push() → ajoute un élément
• top() → retourne l’élément prioritaire
• pop() → retire l’élément prioritaire
• size(), empty()

#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(); // retire 80

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

Cas d’utilisation : algorithmes comme Dijkstra, ordonnancement de tâches, systèmes de priorités.

4) Utiliser priority_queue comme Min-Heap

Par défaut, priority_queue est un max-heap. Pour créer un min-heap, on utilise greater<>.

#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) Exemples pratiques

a) Vérification de parenthèses avec 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) Simulation d’une file de banque avec queue

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

int main() {
    queue<string> customers;

    customers.push("Jean");
    customers.push("Émilie");
    customers.push("David");

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

c) Priorisation de tâches avec priority_queue

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

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

    tasks.push({3, "Faible priorité"});
    tasks.push({10, "Haute priorité"});
    tasks.push({5, "Priorité moyenne"});

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

6) Quand utiliser quelle structure ?

• stack : annulation, analyse d’expressions, piles d’appels
• queue : files d’attente, enchaînement de tâches, systèmes de messages
• priority_queue : traitement prioritaire, algorithmes, ordonnancement

Choisir la bonne structure améliore à la fois la performance et la lisibilité du code.

7) TL;DR

Articles connexes