使用一个数据结构实现多个栈（K个栈）-C++-PHP中文网

使用一个数据结构实现多个栈（K个栈）

动态多栈是一种非常出色的数据结构，它具有在多个栈中存储元素的能力，栈的数量是不断变化的。只使用一个数据结构来实现K个栈可能是一项艰巨的任务。在本教程中，我们将探讨两种不同的方法来使用C++执行动态多栈（K个栈）。第一种方法使用一个数组来存储元素，还有两个额外的数组来监视栈的最顶端和下一个索引。第二种方法使用一个节点向量来存储元素，还有一个向量来跟踪每个栈的头部。

本文将重点介绍如何在C++中使用一种数据结构来执行动态多堆栈。

方法

方法一 - 使用一个数组来存储数据结构的元素，并使用两个辅助数组来存储每个栈的顶部元素和数组中下一个可用空槽的索引。
方法2 - 使用双向链表来存储数据结构的元素，并使用向量来存储每个栈的头节点。

语法

给定的语法是在C++中声明名为KStacks的类。该类具有以下成员函数或方法-

一个构造方法 KStacks，它接受两个参数 k 和 n。
名为push的方法，它接受两个参数item和sn，用于将元素插入堆栈sn中。
一个名为pop的方法，它接受一个参数sn，并用于从堆栈sn中移除一个元素。
名为 is_empty 的方法，它采用单个参数 sn 并返回一个布尔值，指示堆栈 sn 是否为空。
名为 is_full 的方法，它返回一个布尔值，指示整个数据结构是否已满。

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

登录后复制

算法

以下是使用单个数据结构实现K堆动态多重背包的算法：

步骤 1 - 首先创建一个数据结构，其中包含一个大小为 n 的数组来存储元素，以及两个大小为 k 的辅助数组。一个数组将存储有关每个堆栈最顶层元素的信息，而另一个数组将跟踪主数组中的下一个可用索引。
第 2 步 - 接下来，我们使用值 -1 和 0 调用父数组及其对应的数组。
第 3 步 - 使用 cart() 函数，我们可以将对象添加到特定堆栈中。该函数需要两个输入：要添加的项目和组号。在添加项目之前，push() 函数通过将下一个可用索引值与 n 进行比较来检查数据结构是否已满。如果仍有空间，则将该项目添加到下一个可用索引，并更新下一个可用索引的值。
步骤 4 - pop() 函数用于从特定堆栈中删除项目，以组号作为其参数。 pop() 函数通过将父数组值与 -1 进行比较来检查堆栈是否为空。如果堆栈不为空，则 pop() 函数会从堆栈中删除最顶层元素，并更新父数组值以指向新的最顶层元素。
第五步 - 要检查特定的堆栈是否为空，我们使用is_empty()函数，并将组号作为其参数。该函数检查父数组的值是否等于-1。
第 6 步 - 要检查所有堆栈是否已满，我们使用 is_full() 函数，该函数检查下一个可用索引值是否等于 n。

方法一

我们将采用一种方法，其中涉及利用一个数组来保留元素，以及两个附加数组来监视堆栈的最顶层和后续索引。虽然这是一个简单有效的解决方案，但它需要预先定义预定数量的堆栈。

下面是相同的程序代码。

示例

该代码代表 K Stacks 数据结构的实现，它是堆栈数据结构的动态解释，允许在单个数组中容纳多个堆栈。

KStacks类包含三个成员变量−

arr − 一个作为所有栈元素存储的数组。
top − 一个用作每个栈顶部存储的数组。
next − 一个用作存储数组中下一个可用位置的数组。
push − 将一个元素插入到指定的堆栈中。
pop − 从指定的堆栈中移除一个元素。
is_empty − 验证指定的堆栈是否为空。
is_full - 验证数组是否完全被占用。

在main函数中，生成了KStacks类的实例，以栈的数量和数组的大小作为输入参数。然后，元素被推入三个不同的堆栈中。最后，删除并显示每个堆栈的顶部元素。

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

以上是使用一个数据结构实现多个栈（K个栈）的详细内容。更多信息请关注PHP中文网其他相关文章！