使用一個資料結構實作多個棧（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中文網其他相關文章！