Utiliser une structure de données pour implémenter plusieurs piles (K piles)

Le multi-stack dynamique est une excellente structure de données qui a la capacité de stocker des éléments dans plusieurs piles, et le nombre de piles change constamment. Implémenter des piles K en utilisant une seule structure de données peut être une tâche ardue. Dans ce didacticiel, nous explorerons deux manières différentes d'effectuer des multi-stacks dynamiques (piles K) en utilisant C++. La première méthode utilise un tableau pour stocker les éléments et deux tableaux supplémentaires pour surveiller l'index supérieur et suivant de la pile. La deuxième méthode utilise un vecteur de nœud pour stocker les éléments et un vecteur pour suivre la tête de chaque pile.

Cet article se concentrera sur la façon d'utiliser une structure de données pour effectuer un multi-stack dynamique en C++.

Méthode

• Méthode 1 - Utilisez un tableau pour stocker les éléments de la structure de données et utilisez deux tableaux auxiliaires pour stocker l'élément supérieur de chaque pile et l'index du prochain emplacement vide disponible dans le tableau.

• Méthode 2 - Utilisez une liste doublement chaînée pour stocker les éléments de la structure de données et utilisez un vecteur pour stocker le nœud principal de chaque pile.

Grammaire

La syntaxe donnée consiste à déclarer une classe nommée KStacks en C++. Cette classe a les fonctions ou méthodes membres suivantes : 

• Une méthode constructeur KStacks, qui accepte deux paramètres k et n.

• La méthode nommée push, qui accepte deux paramètres item et sn, est utilisée pour insérer des éléments dans la pile sn.

• Une méthode appelée pop, qui accepte un paramètre sn et est utilisée pour supprimer un élément de la pile sn.

• Méthode nommée is_empty qui prend un seul paramètre sn et renvoie une valeur booléenne indiquant si la pile sn est vide.

• Méthode nommée is_full qui renvoie un booléen indiquant si toute la structure de données est pleine.

class KStacks {
   public:
   KStacks(int k, int n); // Constructor
   void push(int item, int sn); // Insert an element into stack 'sn'
   int pop(int sn); // Remove an element from stack 'sn'
   bool is_empty(int sn); // Check if stack 'sn' is empty
   bool is_full(); // Check if the entire data structure is full
};

Algorithme

Voici l'algorithme permettant d'implémenter le multi-sac à dos dynamique K-heap en utilisant une seule structure de données :

• Étape 1 - Créez d'abord une structure de données contenant un tableau de taille n pour stocker les éléments, et deux tableaux auxiliaires de taille k. Un tableau stockera des informations sur l'élément le plus haut de chaque pile, tandis que l'autre tableau gardera une trace du prochain index disponible dans le tableau principal.

• Étape 2 - Ensuite, nous appelons le tableau parent et son tableau correspondant avec les valeurs -1 et 0.

• Étape 3 - En utilisant la fonction cart(), nous pouvons ajouter des objets à une pile spécifique. Cette fonction nécessite deux entrées : l'élément à ajouter et le numéro de groupe. Avant d'ajouter un élément, la fonction push() vérifie si la structure de données est pleine en comparant la prochaine valeur d'index disponible à n. S'il reste de l'espace, l'élément est ajouté au prochain index disponible et la valeur du prochain index disponible est mise à jour.

• Étape 4 - La fonction pop() est utilisée pour supprimer un élément d'une pile spécifique, en prenant le numéro de groupe comme paramètre. La fonction pop() vérifie si la pile est vide en comparant la valeur du tableau parent avec -1. Si la pile n'est pas vide, la fonction pop() supprime l'élément le plus haut de la pile et met à jour la valeur du tableau parent pour pointer vers le nouvel élément le plus haut.

• Étape 5 - Pour vérifier si une pile spécifique est vide, nous utilisons la fonction is_empty() et prenons le numéro de groupe comme argument. Cette fonction vérifie si la valeur du tableau parent est égale à -1.

• Étape 6 - Pour vérifier si toutes les piles sont pleines, nous utilisons la fonction is_full() qui vérifie si la prochaine valeur d'index disponible est égale à n.

Méthode 1

Nous utiliserons une approche qui consiste à utiliser un tableau pour contenir les éléments et deux tableaux supplémentaires pour surveiller les indices les plus élevés et les suivants de la pile. Bien qu’il s’agisse d’une solution simple et efficace, elle nécessite de définir à l’avance un nombre prédéterminé de piles.

Vous trouverez ci-dessous le même code de programme.

Exemple

Ce code représente une implémentation de la structure de données K Stacks, qui est une interprétation dynamique de la structure de données des piles qui permet d'héberger plusieurs piles dans un seul tableau.

La classe KStacks contient trois variables membres−

• arr - Un tableau stocké comme tous les éléments de la pile.

• top - Un tableau utilisé comme stockage supérieur pour chaque pile.

• next - Un tableau utilisé pour stocker la prochaine position disponible dans le tableau.

• push - Insère un élément dans la pile spécifiée.

• pop - Supprime un élément de la pile spécifiée.

• is_empty - Vérifie si la pile spécifiée est vide.

• is_full - Vérifiez que la baie est entièrement occupée.

Dans la fonction principale, une instance de la classe KStacks est générée, prenant le nombre de piles et la taille du tableau comme paramètres d'entrée. Les éléments sont ensuite poussés sur trois piles différentes. Enfin, supprimez et affichez l'élément supérieur de chaque pile.

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

class KStacks {
   private:
   int *arr;
   int *top;
   int *next;
   int n, k;
   public:
   KStacks(int k, int n) {
      this->k = k;
      this->n = n;
      arr = new int[n];
      top = new int[k];
      next = new int[n];
   for (int i = 0; i < k; i++)
      top[i] = -1;

   for (int i = 0; i < n - 1; i++)
      next[i] = i + 1;
   next[n - 1] = -1;
}

void push(int item, int sn) {
   if (is_full()) {
      cout << "Stack Overflow\n";
      return;
   }

   int i = next[sn];
   next[sn] = top[sn];
   top[sn] = i;
   arr[i] = item;
}

int pop(int sn) {
   if (is_empty(sn)) {
      cout << "Stack Underflow\n";
      return INT_MAX;
   }

   int i = top[sn];
   top[sn] = next[i];
   next[i] = i;
   return arr[i];
   }

   bool is_empty(int sn) {
      return top[sn] == -1;
   }

   bool is_full() {
      return next[0] == -1;
   }
};

int main() {
   KStacks ks(3, 10);
   ks.push(15, 2);
   ks.push(45, 2);

   ks.push(17, 1);
   ks.push(49, 1);
   ks.push(39, 1);

   ks.push(11, 0);
   ks.push(9, 0);
   ks.push(7, 0);

   cout << "Popped element from stack 2: " << ks.pop(2) << endl;
   cout << "Popped element from stack 1: " << ks.pop(1) << endl;
   cout << "Popped element from stack 0: " << ks.pop(0) << endl;

   return 0;
}

输出

Stack Overflow
Stack Overflow
Popped element from stack 2: Stack Underflow
2147483647
Popped element from stack 1: 39
Popped element from stack 0: 11

方法二

我们将采用一种方法，其中使用节点向量来存储元素。这种方法应该由一个用于维护每个堆栈头部的向量来补充。事实证明，我们的方法是一种更灵活的解决方案，可以容纳经历动态变化的可变数量的堆栈。然而，这种方法可能会带来更重的内存负担并带来更多的开销。

示例 2

该代码构成了一个 C++ 程序，该程序实现了称为“KStacks”的数据架构。这种数据结构通过应用一种称为“固定划分”的方法，可以在单个数组中存储多个堆栈。

“KStacks”类包含一系列成员函数，包括“push”、“pop”、“is_empty”和“is_full”。 “推入”操作允许将项目添加到指定的堆栈，而“弹出”功能则从指定的堆栈中消除顶部项目。

如果指定的堆栈未被占用，则“is_empty”函数返回true，如果所有堆栈都完全被占用，则“is_full”函数返回true。在主函数中，建立了三个容量为10的堆栈，并从每个堆栈中推入和弹出项目。最终，弹出的项目将显示在控制台上。

代码

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

class Node {
public:
   int data;
   int prev;
   int next;
};

class KStacks {
  private:
   vector<Node> arr;
   vector<int> head;
   int n, k;
   int free;

  public:
   KStacks(int k, int n) {
   this->k = k;
   this->n = n;
   arr.resize(n);
   head.resize(k, -1);
   free = 0;
   for (int i = 0; i < n - 1; i++)
      arr[i].next = i + 1;
   arr[n - 1].next = -1;
}

void push(int item, int sn) {
   if (is_full()) {
      cout << "Stack Overflow\n";
      return;
   }

   int i = free;
   free = arr[i].next;
   arr[i].data = item;
   arr[i].prev = head[sn];
   arr[i].next = -1;

   if (head[sn] != -1)
      arr[head[sn]].next = i;
      head[sn] = i;
   }

   int pop(int sn) {
      if (is_empty(sn)) {
         cout << "Stack Underflow\n";
         return INT_MAX;
      }
      int i = head[sn];
      head[sn] = arr[i].prev;

      if (head[sn] != -1)
         arr[head[sn]].next = -1;

      arr[i].next = free;
      free = i;

      return arr[i].data;
   }

   bool is_empty(int sn) {
      return head[sn] == -1;
   }
   bool is_full() {
      return free == -1;
   }
};

int main() {
   KStacks ks(3, 10);
   ks.push(15, 2);
   ks.push(45, 2);

   ks.push(17, 1);
   ks.push(49, 1);
   ks.push(39, 1);

   ks.push(11, 0);
   ks.push(9, 0);
   ks.push(7, 0);

   cout << "Popped element from stack 2: " << ks.pop(2) <<endl;
   cout << "Popped element from stack 1: " << ks.pop(1) <<endl;
   cout << "Popped element from stack 0: " << ks.pop(0) <<endl;

   return 0;
}

输出

Popped element from stack 2: 45
Popped element from stack 1: 39
Popped element from stack 0: 7

结论

在本文中，我们讨论了使用 C++ 中的单个数据结构创建动态多堆栈的两种不同方法。两种方法都有其优点和缺点，选择使用哪一种方法将取决于当前问题的具体需求。

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!