目錄
方法
文法
演算法
方法一
範例
输出
方法二
示例 2
代码
结论
首頁 後端開發 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中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1666
14
CakePHP 教程
1425
52
Laravel 教程
1325
25
PHP教程
1272
29
C# 教程
1252
24
C#與C:歷史,進化和未來前景 C#與C:歷史,進化和未來前景 Apr 19, 2025 am 12:07 AM

C#和C 的歷史與演變各有特色,未來前景也不同。 1.C 由BjarneStroustrup在1983年發明,旨在將面向對象編程引入C語言,其演變歷程包括多次標準化,如C 11引入auto關鍵字和lambda表達式,C 20引入概念和協程,未來將專注於性能和系統級編程。 2.C#由微軟在2000年發布,結合C 和Java的優點,其演變注重簡潔性和生產力,如C#2.0引入泛型,C#5.0引入異步編程,未來將專注於開發者的生產力和雲計算。

C#vs. C:學習曲線和開發人員的經驗 C#vs. C:學習曲線和開發人員的經驗 Apr 18, 2025 am 12:13 AM

C#和C 的学习曲线和开发者体验有显著差异。1)C#的学习曲线较平缓,适合快速开发和企业级应用。2)C 的学习曲线较陡峭,适用于高性能和低级控制的场景。

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和XML:探索關係和支持 C和XML:探索關係和支持 Apr 21, 2025 am 12:02 AM

C 通過第三方庫(如TinyXML、Pugixml、Xerces-C )與XML交互。 1)使用庫解析XML文件,將其轉換為C 可處理的數據結構。 2)生成XML時,將C 數據結構轉換為XML格式。 3)在實際應用中,XML常用於配置文件和數據交換,提升開發效率。

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

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

什麼是C  中的靜態分析? 什麼是C 中的靜態分析? Apr 28, 2025 pm 09:09 PM

靜態分析在C 中的應用主要包括發現內存管理問題、檢查代碼邏輯錯誤和提高代碼安全性。 1)靜態分析可以識別內存洩漏、雙重釋放和未初始化指針等問題。 2)它能檢測未使用變量、死代碼和邏輯矛盾。 3)靜態分析工具如Coverity能發現緩衝區溢出、整數溢出和不安全API調用,提升代碼安全性。

C的未來:改編和創新 C的未來:改編和創新 Apr 27, 2025 am 12:25 AM

C 的未來將專注於並行計算、安全性、模塊化和AI/機器學習領域:1)並行計算將通過協程等特性得到增強;2)安全性將通過更嚴格的類型檢查和內存管理機制提升;3)模塊化將簡化代碼組織和編譯;4)AI和機器學習將促使C 適應新需求,如數值計算和GPU編程支持。

C  中的chrono庫如何使用? C 中的chrono庫如何使用? Apr 28, 2025 pm 10:18 PM

使用C 中的chrono庫可以讓你更加精確地控制時間和時間間隔,讓我們來探討一下這個庫的魅力所在吧。 C 的chrono庫是標準庫的一部分,它提供了一種現代化的方式來處理時間和時間間隔。對於那些曾經飽受time.h和ctime折磨的程序員來說,chrono無疑是一個福音。它不僅提高了代碼的可讀性和可維護性,還提供了更高的精度和靈活性。讓我們從基礎開始,chrono庫主要包括以下幾個關鍵組件:std::chrono::system_clock:表示系統時鐘,用於獲取當前時間。 std::chron

See all articles