给定两个整数 n 和 k。我们的目标是在一个大小为 n 的单个数组中实现 k 个栈。多个栈必须共享同一个数组空间，并且需要支持以下操作：
> push(x, i): 将元素 x 压入第 i 个栈。
> pop(i): 从第 i 个栈弹出顶部元素并返回它。
目录
- [朴素方法] 将数组划分为 k 段
- [高效方法] 使用空间优化技术
[朴素方法] 将数组划分为 k 段
> 这个思路的核心是将数组划分为固定的部分，每个栈占据一部分。如果数组大小为 n，共有 k 个栈，那么每个栈可以获得 n/k 个槽位。
我们需要维护另一个大小为 k 的数组 INLINECODEb886bb85，其中 INLINECODE71376807 存储第 i 个栈的顶部元素索引。最初，所有的 top[i] 都被设置为它们各自段的起始位置减一（表示栈为空）。
压入 操作通过递增 INLINECODE64bf34e1 并插入元素来完成，而 弹出 操作则是返回 INLINECODE48438380 位置的元素然后递减索引。
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20250407110640301713/Division-of-an-Array-to-Implement-k-Stacks.webp">Division-of-an-Array-to-Implement-k-Stacks
局限性： 这种方法会导致空间利用率低下，因为即使其他栈还有空闲空间，某一个栈可能已经满了。
C++
#include
#include
using namespace std;
class kStacks {
// 用于存储元素的主数组
int *arr;
// 存储每个栈的顶部索引
int *top;
// 每个段的大小
int segSize;
public:
kStacks(int n, int k) {
segSize = n / k;
arr = new int[n];
top = new int[k];
// 初始化顶部指针
for (int i = 0; i < k; i++)
top[i] = i * segSize - 1;
}
// 将元素 x 压入栈 i
void push(int x, int i) {
int end = (i + 1) * segSize - 1;
if (top[i] == end) {
cout << "Stack " << i << " overflow" << endl;
return;
}
top[i]++;
arr[top[i]] = x;
}
// 从栈 i 弹出元素
int pop(int i) {
int start = i * segSize;
if (top[i] < start) {
cout << "Stack " << i << " underflow" << endl;
return -1;
}
int val = arr[top[i]];
top[i]--;
return val;
}
};
int main() {
int n = 4, k = 2;
kStacks st(n, k);
// 每个操作具有以下格式：
// 1. 压入操作 → {1, value, stackNumber}
// 2. 弹出操作 → {2, stackNumber}
vector<vector> operations = {
{1, 5, 0},
{1, 9, 0},
{1, 10, 0},
{1, 15, 1},
{2, 0},
{2, 1},
{2, 1}
};
for (auto &op : operations) {
if (op[0] == 1) {
int x = op[1], m = op[2];
st.push(x, m);
} else if (op[0] == 2) {
int m = op[1];
int res = st.pop(m);
if (res != -1)
cout << "Popped Element: " << res << endl;
}
}
return 0;
}
Java
“java
import java.util.Vector;
class kStacks {
// 用于存储元素的主数组
private int[] arr;
// 存储每个栈的顶部索引
private int[] top;
// 每个段的大小
private int segSize;
public kStacks(int n, int k) {
segSize = n / k;
arr = new int[n];
top = new int[k];
// 初始化顶部指针
for (int i = 0; i < k; i++)
top[i] = i * segSize – 1;
}
// 将元素 x 压入栈 i
public void push(int x, int i) {
int end = (i + 1) * segSize – 1;
if (top[i] == end) {
System.out.println("Stack " + i + " overflow");
return;
}
top[i]++;
arr[top[i]] = x;
}
// 从栈 i 弹出元素
public int pop(int i) {
int start = i * segSize;
if (top[i] < start) {
System.out.println("Stack " + i + " underflow");
return -1;
}
int val = arr[top[i]];
top[i]–;
return val;
}
}
public class Main {
public static void main(String[] args) {
int n = 4, k = 2;
kStacks st = new kStacks(n, k);
// 每个操作具有以下格式：
// 1. 压入操作 → {1, value, stackNumber}
// 2. 弹出操作 → {2, stackNumber}
int[][] operations = {
{1, 5, 0},
{1, 9, 0},
{1, 10, 0},
{1, 15, 1},
{2, 0},
{2, 1},
{2, 1}
};
for (int[] op : operations) {
if (op[0] == 1) {
int x = op[1], m = op[2];