Verwenden Sie eine Datenstruktur, um mehrere Stapel (K-Stacks) zu implementieren.

Dynamischer Multi-Stack ist eine hervorragende Datenstruktur, die Elemente in mehreren Stapeln speichern kann, und die Anzahl der Stapel ändert sich ständig. Die Implementierung von K-Stacks mit nur einer Datenstruktur kann eine entmutigende Aufgabe sein. In diesem Tutorial werden wir zwei verschiedene Möglichkeiten zur Durchführung dynamischer Multi-Stacks (K-Stacks) mit C++ untersuchen. Die erste Methode verwendet ein Array zum Speichern der Elemente und zwei zusätzliche Arrays zum Überwachen des obersten und nächsten Index des Stapels. Die zweite Methode verwendet einen Knotenvektor zum Speichern der Elemente und einen Vektor zum Verfolgen des Kopfes jedes Stapels.

Dieser Artikel konzentriert sich auf die Verwendung einer Datenstruktur zur Durchführung eines dynamischen Multi-Stack in C++.

Methode

• Methode 1 – Verwenden Sie ein Array, um die Elemente der Datenstruktur zu speichern, und verwenden Sie zwei Hilfsarrays, um das oberste Element jedes Stapels und den Index des nächsten verfügbaren leeren Steckplatzes im Array zu speichern.

• Methode 2 – Verwenden Sie eine doppelt verknüpfte Liste, um die Elemente der Datenstruktur zu speichern, und verwenden Sie einen Vektor, um den Kopfknoten jedes Stapels zu speichern.

Grammatik

Die angegebene Syntax besteht darin, eine Klasse namens KStacks in C++ zu deklarieren. Diese Klasse verfügt über die folgenden Mitgliedsfunktionen oder -methoden:

• Eine Konstruktormethode KStacks, die zwei Parameter k und n akzeptiert.

• Die Methode namens push, die zwei Parameter item und sn akzeptiert, wird zum Einfügen von Elementen in den Stack-Sn verwendet.

• Eine Methode namens pop, die einen Parameter sn akzeptiert und zum Entfernen eines Elements aus dem Stapel sn verwendet wird.

• Methode namens is_empty, die einen einzelnen Parameter sn annimmt und einen booleschen Wert zurückgibt, der angibt, ob der Stapel sn leer ist.

• Methode namens is_full, die einen booleschen Wert zurückgibt, der angibt, ob die gesamte Datenstruktur voll ist.

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

Algorithmus

Das Folgende ist der Algorithmus zum Implementieren eines dynamischen K-Heap-Multi-Knapsacks unter Verwendung einer einzigen Datenstruktur:

• Schritt 1 – Erstellen Sie zunächst eine Datenstruktur, die ein Array der Größe n zum Speichern der Elemente und zwei Hilfsarrays der Größe k enthält. Ein Array speichert Informationen über das oberste Element jedes Stapels, während das andere Array den nächsten verfügbaren Index im Hauptarray verfolgt.

• Schritt 2 – Als nächstes rufen wir das übergeordnete Array und sein entsprechendes Array mit den Werten -1 und 0 auf.

• Schritt 3 – Mit der Funktion „cart()“ können wir Objekte zu einem bestimmten Stapel hinzufügen. Diese Funktion erfordert zwei Eingaben: das hinzuzufügende Element und die Gruppennummer. Vor dem Hinzufügen eines Elements prüft die Funktion push(), ob die Datenstruktur voll ist, indem sie den nächsten verfügbaren Indexwert mit n vergleicht. Wenn noch Platz vorhanden ist, wird das Element zum nächsten verfügbaren Index hinzugefügt und der Wert des nächsten verfügbaren Index aktualisiert.

• Schritt 4 – Die Funktion pop() wird verwendet, um ein Element aus einem bestimmten Stapel zu entfernen, wobei die Gruppennummer als Argument verwendet wird. Die Funktion pop() prüft, ob der Stapel leer ist, indem sie den Wert des übergeordneten Arrays mit -1 vergleicht. Wenn der Stapel nicht leer ist, entfernt die Funktion pop() das oberste Element vom Stapel und aktualisiert den Wert des übergeordneten Arrays so, dass er auf das neue oberste Element zeigt.

• Schritt 5 – Um zu überprüfen, ob ein bestimmter Stapel leer ist, verwenden wir die Funktion is_empty() und nehmen die Gruppennummer als Argument. Diese Funktion prüft, ob der Wert des übergeordneten Arrays gleich -1 ist.

• Schritt 6 – Um zu überprüfen, ob alle Stapel voll sind, verwenden wir die Funktion is_full(), die prüft, ob der nächste verfügbare Indexwert gleich n ist.

Methode 1

Wir werden einen Ansatz verwenden, der die Verwendung eines Arrays zur Aufnahme der Elemente und zwei zusätzlicher Arrays zur Überwachung der obersten und nachfolgenden Indizes des Stapels umfasst. Dies ist zwar eine einfache und effektive Lösung, erfordert jedoch die Festlegung einer vorgegebenen Anzahl von Stapeln im Voraus.

Nachfolgend finden Sie den gleichen Programmcode.

Beispiel

Dieser Code stellt eine Implementierung der K-Stacks-Datenstruktur dar, bei der es sich um eine dynamische Interpretation der Stacks-Datenstruktur handelt, die die Unterbringung mehrerer Stacks in einem einzigen Array ermöglicht.

KStacks-Klasse enthält drei Mitgliedsvariablen −

• arr – Ein Array, das als alle Stapelelemente gespeichert ist.

• top – Ein Array, das als oberster Speicher für jeden Stapel verwendet wird.

• next – Ein Array, das zum Speichern der nächsten verfügbaren Position im Array verwendet wird.

• push – Fügt ein Element in den angegebenen Stapel ein.

• pop − Entfernt ein Element aus dem angegebenen Stapel.

• is_empty − Überprüft, ob der angegebene Stapel leer ist.

• is_full – Stellen Sie sicher, dass das Array vollständig belegt ist.

In der Hauptfunktion wird eine Instanz der KStacks-Klasse generiert, wobei die Anzahl der Stapel und die Größe des Arrays als Eingabeparameter verwendet werden. Anschließend werden die Elemente auf drei verschiedene Stapel geschoben. Entfernen Sie abschließend das oberste Element jedes Stapels und zeigen Sie es an.

#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++ 中的单个数据结构创建动态多堆栈的两种不同方法。两种方法都有其优点和缺点，选择使用哪一种方法将取决于当前问题的具体需求。

Das obige ist der detaillierte Inhalt vonVerwenden Sie eine Datenstruktur, um mehrere Stapel (K-Stacks) zu implementieren.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!