Pile et file d'attente en C++

Introduction aux piles et aux files d'attente en C++

Les piles et les files d'attente sont des structures de données couramment utilisées en C++, et elles sont largement utilisées dans les programmes. Cet article présentera en détail les concepts, les scénarios d'utilisation et d'application des piles et des files d'attente.

1. Le concept de stack

Stack (Stack) est une structure de données linéaire, qui présente les caractéristiques du « premier entré, dernier sorti ». Dans la pile, les données poussées dans la pile sont plus proches du bas de la pile ; les données poussées plus tard dans la pile sont plus proches du haut de la pile.

Les principales opérations de la pile sont le push et le pop. Pousser consiste à ajouter des données à la pile, et popper consiste à supprimer des données de la pile. La pile comporte également deux opérations spéciales importantes : visualiser l'élément supérieur de la pile (top) et déterminer si la pile est vide (vide).

Les scénarios d'application de la pile sont très larges, par exemple, l'utilisation de la pile est impliquée dans les appels de fonction. Lorsqu'une fonction est appelée, ses paramètres, variables locales et autres informations seront poussés sur la pile. Lorsque l'exécution de la fonction se termine, ces informations seront extraites de la pile et restaurées à l'état avant l'appel de la fonction.

2. Le concept de file d'attente

Queue (Queue) est également une structure de données linéaire, qui présente les caractéristiques du « premier entré, premier sorti ». Dans la file d'attente, les données mises en file d'attente plus tôt sont plus proches de la tête de la file d'attente ; les données mises en file d'attente plus tard sont plus proches de la fin de la file d'attente.

Les principales opérations de la file d'attente sont la mise en file d'attente et la sortie de la file d'attente. Entrer dans la file d'attente signifie ajouter des données à la fin de la file d'attente, tandis que sortir de la file d'attente signifie supprimer les données de la tête de la file d'attente. La file d'attente comporte également deux opérations spéciales importantes : visualiser l'élément de tête (avant) et déterminer si la file d'attente est vide (vide).

Les files d'attente sont également largement utilisées. Par exemple, dans la planification des processus dans le système d'exploitation, les files d'attente peuvent être utilisées pour enregistrer les processus en attente d'exécution. Lorsque les ressources système sont libres, un processus est retiré de la tête de la file d'attente et exécuté jusqu'à ce que toutes les tâches soient terminées.

3. Exemples d'application de piles et de files d'attente

1. Correspondance de supports

En programmation, il est souvent nécessaire de déterminer si les parenthèses d'une chaîne correspondent. Par exemple, lors de l'écriture d'un programme Python, si vous devez vérifier si le bloc de code est correctement indenté, vous pouvez utiliser la pile pour y parvenir.

La méthode d'implémentation spécifique consiste à parcourir chaque caractère de la chaîne et à le pousser sur la pile lorsque vous rencontrez un crochet gauche. Lorsqu'une parenthèse droite est rencontrée, l'élément supérieur de la pile est sauté pour la correspondance. Si la correspondance réussit, continuez la traversée ; sinon, un message d’erreur est renvoyé.

2. Planification des processus

Dans le système d'exploitation, il est nécessaire de parvenir à une planification et une coordination unifiées des processus. À ce stade, vous pouvez utiliser une file d'attente pour stocker les processus en attente d'exécution, et le système d'exploitation détermine la priorité et l'ordre d'exécution.

La méthode de mise en œuvre spécifique consiste à résumer chaque processus dans une structure de données, comprenant le numéro de processus, la priorité et d'autres informations. Mettez ces processus dans une file d'attente, puis exécutez les processus dans la file d'attente dans l'ordre. Lorsqu'un processus termine sa tâche, il est retiré de la file d'attente jusqu'à ce que la file d'attente soit vide.

4. Implémentation de piles et de files d'attente en C++

En C++, vous pouvez utiliser les classes conteneur fournies par la bibliothèque standard pour implémenter des piles et des files d'attente.

1. Implémentation de la pile

La pile peut être implémentée à l'aide de la classe conteneur std::stack.

std::stack est une classe de modèle qui nécessite de spécifier le type d'élément et le type de conteneur sous-jacent. Lorsque le type de conteneur sous-jacent n'est pas spécifié, std::deque est utilisé par défaut comme conteneur sous-jacent.

Ce qui suit est un exemple d'implémentation de pile simple :

#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. Implémentation de la file d'attente

La file d'attente peut être implémentée à l'aide de la classe conteneur std::queue.

std::queue est également une classe de modèle et doit spécifier le type d'élément et le type de conteneur sous-jacent. Lorsque le type de conteneur sous-jacent n'est pas spécifié, std::deque est utilisé par défaut comme conteneur sous-jacent.

Ce qui suit est un exemple simple d'implémentation de file d'attente :

#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;
}

Résumé

Comme le montre l'introduction ci-dessus, les piles et les files d'attente sont des structures de données très pratiques qui peuvent nous aider à résoudre de nombreux problèmes pratiques. En programmation, maîtriser les principes d'utilisation et de mise en œuvre de ces deux structures de données peut améliorer l'efficacité et la fiabilité du programme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!