如何在单个数组中高效实现 k 个栈？

本文讨论了 k 个栈的通用解决方案。下面提供了整个研究目标。创建一个名为 kStacks 的数据结构来表示 k 个栈。kStacks 的实现只能使用一个数组，即 kstacks 应该在同一个数组中存储元素。

kStacks 必须支持以下功能。

方法 1（将数组平均划分为 n/k 个槽）

实现 kstacks 的一种简单方法是将数组划分为 k 个大小为 n/k 的槽，并将这些槽分配给不同的栈。也就是说，使用 arr1[0] 到 arr1[n/k-1] 作为第一个栈，使用 arr1[n/k] 到 arr1[2n/k-1] 作为第二个栈，其中 arr1[] 是用于实现两个栈的数组，数组大小为 n。这种方法的问题在于它浪费了数组空间。当 arr1[] 中有空间时，栈的 push 操作可能会导致栈溢出。例如，假设 k 为 2，数组大小 (n) 为 6，我们将三个元素推入第一个栈，而第二个栈为空。即使数组还有三个元素的空间，如果要将第四个元素推入第一个栈，也会发生溢出。

方法 2（一种节省空间的实现）

为了在一个数组中高效地实现 k 个栈，使用了两个额外的数组。对于整数栈来说，这听起来可能不太对，但是栈的元素，例如工人的栈、学习者的栈等，可能很大，每个元素有数百字节。由于我们使用两个整数数组作为这些大型栈的额外存储空间，因此额外空间的利用率相对较低。

以下是两个附加数组

1) top1[]：这是一个 k 维数组，用于存储所有栈的栈顶元素的索引。

2) next1[]：它的容量为 n，用于存储 arr1[] 中元素的下一个元素索引。

在这里，arr1[] 是包含 k 个栈的实际数组。除了 k 个栈之外，还维护着 arr1[] 中的空闲空间栈。该栈的栈顶存储在名为 'free' 的变量中。为了表示所有栈都为空，top1[] 中的所有条目都初始化为 -1。由于所有槽最初都是空闲的，并且指向下一个槽，因此 next1[i] 的所有条目都初始化为 i+1。空闲栈的栈顶 'free' 设置为 0。

上述概念的实现如下所示。

C++ 程序

输出

The element removed from stack 2 is 45
The element removed from stack 1 is 39
The element removed from stack 0 is 7