搜尋
首頁後端開發C++使用一個資料結構實作多個棧(K個棧)

使用一個資料結構實作多個棧(K個棧)

Sep 11, 2023 pm 01:05 PM
資料結構:多棧實現:一個堆疊的數量:k

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

陳述
本文轉載於:tutorialspoint。如有侵權,請聯絡admin@php.cn刪除
C#vs. C:內存管理和垃圾收集C#vs. C:內存管理和垃圾收集Apr 15, 2025 am 12:16 AM

C#使用自動垃圾回收機制,而C 採用手動內存管理。 1.C#的垃圾回收器自動管理內存,減少內存洩漏風險,但可能導致性能下降。 2.C 提供靈活的內存控制,適合需要精細管理的應用,但需謹慎處理以避免內存洩漏。

超越炒作:評估當今C的相關性超越炒作:評估當今C的相關性Apr 14, 2025 am 12:01 AM

C 在現代編程中仍然具有重要相關性。 1)高性能和硬件直接操作能力使其在遊戲開發、嵌入式系統和高性能計算等領域佔據首選地位。 2)豐富的編程範式和現代特性如智能指針和模板編程增強了其靈活性和效率,儘管學習曲線陡峭,但其強大功能使其在今天的編程生態中依然重要。

C社區:資源,支持和發展C社區:資源,支持和發展Apr 13, 2025 am 12:01 AM

C 學習者和開發者可以從StackOverflow、Reddit的r/cpp社區、Coursera和edX的課程、GitHub上的開源項目、專業諮詢服務以及CppCon等會議中獲得資源和支持。 1.StackOverflow提供技術問題的解答;2.Reddit的r/cpp社區分享最新資訊;3.Coursera和edX提供正式的C 課程;4.GitHub上的開源項目如LLVM和Boost提陞技能;5.專業諮詢服務如JetBrains和Perforce提供技術支持;6.CppCon等會議有助於職業

c#vs. c:每種語言都擅長c#vs. c:每種語言都擅長Apr 12, 2025 am 12:08 AM

C#適合需要高開發效率和跨平台支持的項目,而C 適用於需要高性能和底層控制的應用。 1)C#簡化開發,提供垃圾回收和豐富類庫,適合企業級應用。 2)C 允許直接內存操作,適用於遊戲開發和高性能計算。

繼續使用C:耐力的原因繼續使用C:耐力的原因Apr 11, 2025 am 12:02 AM

C 持續使用的理由包括其高性能、廣泛應用和不斷演進的特性。 1)高效性能:通過直接操作內存和硬件,C 在系統編程和高性能計算中表現出色。 2)廣泛應用:在遊戲開發、嵌入式系統等領域大放異彩。 3)不斷演進:自1983年發布以來,C 持續增加新特性,保持其競爭力。

C和XML的未來:新興趨勢和技術C和XML的未來:新興趨勢和技術Apr 10, 2025 am 09:28 AM

C 和XML的未來發展趨勢分別為:1)C 將通過C 20和C 23標準引入模塊、概念和協程等新特性,提升編程效率和安全性;2)XML將繼續在數據交換和配置文件中佔據重要地位,但會面臨JSON和YAML的挑戰,並朝著更簡潔和易解析的方向發展,如XMLSchema1.1和XPath3.1的改進。

現代C設計模式:構建可擴展和可維護的軟件現代C設計模式:構建可擴展和可維護的軟件Apr 09, 2025 am 12:06 AM

現代C 設計模式利用C 11及以後的新特性實現,幫助構建更靈活、高效的軟件。 1)使用lambda表達式和std::function簡化觀察者模式。 2)通過移動語義和完美轉發優化性能。 3)智能指針確保類型安全和資源管理。

C多線程和並發:掌握並行編程C多線程和並發:掌握並行編程Apr 08, 2025 am 12:10 AM

C 多線程和並發編程的核心概念包括線程的創建與管理、同步與互斥、條件變量、線程池、異步編程、常見錯誤與調試技巧以及性能優化與最佳實踐。 1)創建線程使用std::thread類,示例展示瞭如何創建並等待線程完成。 2)同步與互斥使用std::mutex和std::lock_guard保護共享資源,避免數據競爭。 3)條件變量通過std::condition_variable實現線程間的通信和同步。 4)線程池示例展示瞭如何使用ThreadPool類並行處理任務,提高效率。 5)異步編程使用std::as

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
4 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
4 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
1 個月前By尊渡假赌尊渡假赌尊渡假赌

熱工具

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具