Empiler la structure de données à l'aide d'une liste chaînée en C++

Cet article explique comment implémenter une structure de données de pile à l’aide d’une liste chaînée en C++.

Implémenter la structure de données de pile à l’aide d’une liste à liaison unique en C++

La pile est une structure de données abstraite fréquemment utilisée dans les programmes, les cas d’utilisation les plus courants étant la mémoire de pile de programmes.

Ce type de données abstrait a deux opérations principales : push et pop. Le premier effectue l’insertion de l’élément au-dessus des autres éléments et le second supprime l’élément le plus récent de la pile.

Une pile est classée comme structure de données LIFO (last in, first out). La pile peut être implémentée avec différentes méthodes, mais nous la construirons à partir d’une liste à chaînage unique dans cet article.

Notez qu’une pile n’a besoin de garder une trace que de l’élément le plus haut car c’est là que les modifications se produisent. Sinon, il s’agit essentiellement d’une collection séquentielle de données qui peuvent ou non avoir une capacité fixe. Ce dernier dépend de la décision de conception prise par le programmeur.

Les extraits de code suivants implémentent une pile qui peut croître sans limites de capacité prédéfinies. Dans un premier temps, nous définissons un nœud d’une liste chaînée singulièrement et le typedef comme ListNode. Ensuite, nous déclarons une classe Stack et incluons un seul membre de données pour suivre le haut de la liste.

Dans cet exemple, nous n’implémenterons que les fonctions push et printNodes. La fonction membre push fonctionne de manière similaire à l’opération d’insertion pour la liste à chaînage simple, sauf qu’elle ajoute chaque nouvel élément en tête de liste.

Bien que notre classe Stack ait le constructeur qui initialise le premier élément, ce mauvais choix de conception n’est pris que pour simplifier l’exemple de code de cet article d’introduction.

En revanche, la fonction membre printNodes n’est pas la fonction essentielle pour le type de données stack, mais elle facilite la démonstration. Cela nous aide à vérifier que notre implémentation fonctionne comme prévu.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class Stack {
 public:
  explicit Stack(string data) {
    top = new ListNode;
    top->data = std::move(data);
    top->next = nullptr;
  };

  ListNode *push(string data);
  void printNodes();

 private:
  ListNode *top = nullptr;
};

ListNode *Stack::push(string data) {
  auto new_node = new ListNode;
  new_node->data = std::move(data);
  new_node->next = top;
  top = new_node;
  return top;
}

void Stack::printNodes() {
  auto count = 0;
  auto tmp = top;
  while (tmp) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  Stack s1("Xenial");

  for (const auto &item : data_set) {
    s1.push(item);
  }
  s1.printNodes();

  return EXIT_SUCCESS;
}

node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial

Le code précédent n’a pas l’opération pop, qui est nécessaire pour qu’une structure de données de pile fonctionne correctement. Puisque nous implémentons une pile illimitée et ne nous soucions que de la simplicité des exemples, les allocations de mémoire sont gérées à la demande. Chaque opération pop invoque delete pour libérer la mémoire détenue par l’élément précédent au-dessus. Dans un scénario réel, il faudrait préférer limiter la capacité de la pile ou allouer de la mémoire à l’avance pour de meilleures performances.

Enfin, nous avons besoin d’un destructeur qui libère l’objet après qu’il soit hors de portée. La fonction destructrice itère de l’élément top jusqu’à ce que nullptr soit trouvé, ce qui dénote la fin de la pile.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class Stack {
 public:
  explicit Stack(string data) {
    top = new ListNode;
    top->data = std::move(data);
    top->next = nullptr;
  };

  ListNode *push(string data);
  void pop();
  void printNodes();

  ~Stack();

 private:
  ListNode *top = nullptr;
};

ListNode *Stack::push(string data) {
  auto new_node = new ListNode;
  new_node->data = std::move(data);
  new_node->next = top;
  top = new_node;
  return top;
}

void Stack::pop() {
  auto tmp = top->next;
  delete top;
  top = tmp;
}

Stack::~Stack() {
  struct ListNode *tmp = nullptr;
  while (top) {
    tmp = top->next;
    delete top;
    top = tmp;
  }
}

void Stack::printNodes() {
  auto count = 0;
  auto tmp = top;
  while (tmp) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  Stack s1("Xenial");

  for (const auto &item : data_set) {
    s1.push(item);
  }
  s1.printNodes();

  cout << "/ ------------------------------ / " << endl;

  s1.pop();
  s1.pop();
  s1.printNodes();

  return EXIT_SUCCESS;
}

node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
/ ------------------------------ /
node 0 - data: Quantal
node 1 - data: Precise
node 2 - data: Xenial