数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学仅用一种数据结构实现多栈 (K 个栈)
动态多栈是一种优秀的数据结构，它能够存储多个栈中的元素，并且栈的数量可以动态变化。使用单一数据结构实现 K 个栈可能是一项艰巨的任务。在本教程中，我们将探讨两种使用 C++ 实现动态多栈 (K 个栈) 的不同方法。第一种方法使用一个数组来存储元素，以及另外两个数组来跟踪栈的顶部和下一个索引。第二种方法使用节点向量来存储元素，以及一个向量来跟踪每个栈的头部。
本文将重点介绍如何使用 C++ 中的一种数据结构来实现动态多栈。
方法
方法 1 − 使用数组存储数据结构的元素，并使用两个辅助数组存储每个栈的顶部元素和数组中下一个可用槽的索引。
方法 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() 函数会从栈中移除顶部元素，并将父数组值更新为指向新的顶部元素。
步骤 5 − 要检查特定栈是否为空，我们使用 is_empty() 函数，其参数为组号。此函数检查父数组值是否等于 -1。
步骤 6 − 要检查所有栈是否已满，我们使用 is_full() 函数，该函数检查下一个可用索引值是否等于 n。
方法 1
我们将采用一种方法，该方法使用一个数组来保留元素，以及另外两个数组来监视栈的顶部和后续索引。虽然这是一个简单有效的解决方案，但它需要预定义预定的栈数。
以下是相同的程序代码。
示例
该代码表示 K 栈数据结构的实现，它是栈数据结构的动态解释，允许在单个数组中容纳多个栈。
KStacks 类包含三个成员变量：
arr − 一个用作所有栈的元素存储的数组。
top − 一个用作每个栈顶部的存储的数组。
next − 一个用作数组中下一个可用位置的存储的数组。
push − 将元素插入到指定的栈中。
pop − 从指定的栈中移除元素。
is_empty − 验证指定的栈是否为空。
is_full − 验证数组是否完全被占用。
在主函数中，生成 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
我们将采用一种方法，其中将使用节点向量来存储元素。这种方法将由一个向量补充，该向量用于维护每个栈的头部。我们的方法被证明是一个更灵活的解决方案，它可以容纳数量发生动态变化的栈。但是，这种方法可能会带来更大的内存负担，并带来更多开销成本。
示例 2
该代码构成一个 C++ 程序，它实现了名为“KStacks”的数据架构。这种数据结构通过应用称为“固定划分”的方法，允许在单个数组中存储多个栈。
“KStacks”类包含一系列成员函数，包括“push”、“pop”、“is_empty”和“is_full”。“push”操作允许将项目添加到指定的栈中，“pop”函数则从指定的栈中删除顶部项目。
“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++ 中的单个数据结构创建动态多栈的不同方法。这两种方法都有其优点和缺点，选择哪种方法将取决于问题的具体需求。
2000+ 浏览量
