Use one data structure to implement multiple stacks (K stacks)

Dynamic multi-stack is an excellent data structure that has the ability to store elements in multiple stacks, and the number of stacks is constantly changing. Implementing K stacks using only one data structure can be a daunting task. In this tutorial, we will explore two different ways to perform dynamic multi-stacks (K stacks) using C. The first method uses an array to store the elements, and two additional arrays to monitor the top and next index of the stack. The second method uses a node vector to store the elements, and a vector to keep track of the head of each stack.

This article will focus on how to use a data structure in C to perform dynamic multi-stack.

method

• Method 1 - Use an array to store the elements of the data structure, and use two auxiliary arrays to store the top element of each stack and the index of the next available empty slot in the array.

• Method 2 - Use a doubly linked list to store the elements of the data structure, and use a vector to store the head node of each stack.

grammar

The given syntax is to declare a class named KStacks in C. This class has the following member functions or methods-

• A constructor method KStacks, which accepts two parameters k and n.

• The method named push, which accepts two parameters item and sn, is used to insert elements into the stack sn.

• A method named pop, which accepts a parameter sn and is used to remove an element from the stack sn.

• Method named is_empty which takes a single parameter sn and returns a Boolean value indicating whether the stack sn is empty.

• Method named is_full, which returns a Boolean value indicating whether the entire data structure 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
};

algorithm

The following is an algorithm for implementing K-heap dynamic multiple backpacks using a single data structure:

• Step 1 - First create a data structure containing an array of size n to store the elements, and two auxiliary arrays of size k. One array will store information about the topmost element of each stack, while the other array will keep track of the next available index in the main array.

• Step 2 - Next, we call the parent array and its corresponding array with the values ​​-1 and 0.

• Step 3 - Using cart() function we can add objects to a specific stack. This function requires two inputs: the item to add and the group number. Before adding an item, the push() function checks whether the data structure is full by comparing the next available index value to n. If there is still space, the item is added to the next available index and the value of the next available index is updated.

• Step 4 - The pop() function is used to remove an item from a specific stack, taking the group number as its argument. The pop() function checks if the stack is empty by comparing the parent array value with -1. If the stack is not empty, the pop() function removes the top-most element from the stack and updates the parent array value to point to the new top-most element.

• Step 5 - To check if a specific stack is empty, we use the is_empty() function and take the group number as its parameter. This function checks if the value of the parent array is equal to -1.

• Step 6 - To check if all stacks are full we use is_full() function which checks if the next available index value is equal to n.

method one

We will take an approach that involves utilizing an array to hold the elements, and two additional arrays to monitor the topmost and subsequent indices of the stack. While this is a simple and effective solution, it requires a predetermined number of stacks to be defined in advance.

Below is the same program code.

Example

This code represents an implementation of the K Stacks data structure, which is a dynamic interpretation of the stacks data structure that allows multiple stacks to be accommodated in a single array.

KStacks class contains three member variables −

• arr − An array stored as all stack elements.

• top − An array used as storage at the top of each stack.

• next − An array used to store the next available position in the array.

• push − Inserts an element into the specified stack.

• pop − Removes an element from the specified stack.

• is_empty − Verifies whether the specified stack is empty.

• is_full - Verifies that the array is fully occupied.

In the main function, an instance of the KStacks class is generated, with the number of stacks and the size of the array as input parameters. The elements are then pushed onto three different stacks. Finally, remove and display the top element of each stack.

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

The above is the detailed content of Use one data structure to implement multiple stacks (K stacks). For more information, please follow other related articles on the PHP Chinese website!