Gunakan satu struktur data untuk melaksanakan berbilang tindanan (K tindanan)

Berbilang tindanan dinamik ialah struktur data yang sangat baik yang mempunyai keupayaan untuk menyimpan elemen dalam berbilang tindanan, dan bilangan tindanan sentiasa berubah. Melaksanakan tindanan K menggunakan hanya satu struktur data boleh menjadi tugas yang menakutkan. Dalam tutorial ini, kami akan meneroka dua cara berbeza untuk melaksanakan berbilang tindanan dinamik (tindanan K) menggunakan C++. Kaedah pertama menggunakan tatasusunan untuk menyimpan elemen, dan dua tatasusunan tambahan untuk memantau indeks atas dan seterusnya tindanan. Kaedah kedua menggunakan vektor nod untuk menyimpan elemen, dan vektor untuk menjejaki kepala setiap tindanan.

Artikel ini akan menumpukan pada cara menggunakan struktur data untuk melaksanakan berbilang tindanan dinamik dalam C++.

Kaedah

• Kaedah 1 - Gunakan tatasusunan untuk menyimpan elemen struktur data dan gunakan dua tatasusunan tambahan untuk menyimpan elemen atas setiap tindanan dan indeks slot kosong yang tersedia seterusnya dalam tatasusunan.

• Kaedah 2 - Gunakan senarai terpaut dua kali untuk menyimpan elemen struktur data dan gunakan vektor untuk menyimpan nod kepala setiap tindanan.

Tatabahasa

Sintaks yang diberikan adalah untuk mengisytiharkan kelas bernama KStacks dalam C++. Kelas ini mempunyai fungsi atau kaedah ahli berikut-

• Kaedah pembina KStacks, yang menerima dua parameter k dan n.

• Kaedah bernama push, yang menerima dua item parameter dan sn, digunakan untuk memasukkan elemen ke dalam tindanan sn.

• Kaedah yang dipanggil pop, yang menerima parameter sn dan digunakan untuk mengalih keluar elemen daripada sn tindanan.

• Kaedah bernama is_empty yang mengambil satu parameter sn dan mengembalikan nilai boolean yang menunjukkan sama ada tindanan sn kosong.

• Kaedah bernama is_full yang mengembalikan boolean yang menunjukkan sama ada keseluruhan struktur data penuh.

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

Algoritma

Berikut ialah algoritma untuk melaksanakan K-heap dynamic multi-knapsack menggunakan satu struktur data:

• Langkah 1 - Mula-mula buat struktur data yang mengandungi tatasusunan saiz n untuk menyimpan elemen dan dua tatasusunan tambahan saiz k. Satu tatasusunan akan menyimpan maklumat tentang elemen paling atas setiap tindanan, manakala tatasusunan yang lain akan menjejaki indeks yang tersedia seterusnya dalam tatasusunan utama.

• Langkah 2 - Seterusnya, kami memanggil tatasusunan induk dan tatasusunan yang sepadan dengan nilai -1 dan 0.

• Langkah 3 - Menggunakan fungsi cart() kita boleh menambah objek pada tindanan tertentu. Fungsi ini memerlukan dua input: item untuk ditambah dan nombor kumpulan. Sebelum menambah item, fungsi push() menyemak sama ada struktur data penuh dengan membandingkan nilai indeks yang tersedia seterusnya kepada n. Jika masih ada ruang, item itu ditambahkan pada indeks tersedia seterusnya dan nilai indeks tersedia seterusnya dikemas kini.

• Langkah 4 - Fungsi pop() digunakan untuk mengalih keluar item daripada tindanan tertentu, mengambil nombor kumpulan sebagai parameternya. Fungsi pop() menyemak sama ada timbunan kosong dengan membandingkan nilai tatasusunan induk dengan -1. Jika tindanan tidak kosong, fungsi pop() mengalih keluar elemen paling teratas daripada tindanan dan mengemas kini nilai tatasusunan induk untuk menunjuk kepada elemen paling teratas baharu.

• Langkah 5 - Untuk menyemak sama ada tindanan tertentu kosong, kami menggunakan fungsi is_empty() dan mengambil nombor kumpulan sebagai parameternya. Fungsi ini menyemak sama ada nilai tatasusunan induk adalah sama dengan -1.

• Langkah 6 - Untuk menyemak sama ada semua tindanan penuh, kami menggunakan fungsi is_full() yang menyemak sama ada nilai indeks yang tersedia seterusnya adalah sama dengan n.

Kaedah 1

Kami akan menggunakan pendekatan yang melibatkan penggunaan tatasusunan untuk menyimpan elemen, dan dua tatasusunan tambahan untuk memantau indeks paling atas dan seterusnya bagi tindanan. Walaupun ini adalah penyelesaian yang mudah dan berkesan, ia memerlukan bilangan tindanan yang telah ditetapkan untuk ditakrifkan terlebih dahulu.

Di bawah ialah kod program yang sama.

Contoh

Kod ini mewakili pelaksanaan struktur data K Stacks, yang merupakan tafsiran dinamik struktur data tindanan yang membolehkan berbilang tindanan untuk dimuatkan dalam tatasusunan tunggal.

Kelas KStacks mengandungi tiga pembolehubah ahli−

• arr − Tatasusunan yang disimpan sebagai semua elemen tindanan.

• atas − Tatasusunan yang digunakan sebagai storan teratas untuk setiap tindanan.

• next − Tatasusunan yang digunakan untuk menyimpan kedudukan tersedia seterusnya dalam tatasusunan.

• tolak − Masukkan elemen ke dalam tindanan yang ditentukan.

• pop − Mengalih keluar elemen daripada tindanan yang ditentukan.

• is_empty − Mengesahkan sama ada tindanan yang dinyatakan kosong.

• is_full - Sahkan bahawa tatasusunan telah diisi sepenuhnya.

Dalam fungsi utama, contoh kelas KStacks dijana, mengambil bilangan tindanan dan saiz tatasusunan sebagai parameter input. Unsur-unsur kemudian ditolak ke tiga tindanan yang berbeza. Akhir sekali, keluarkan dan paparkan elemen atas setiap tindanan.

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

Atas ialah kandungan terperinci Gunakan satu struktur data untuk melaksanakan berbilang tindanan (K tindanan). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!