在一个数组算法中实现 K 个堆栈

Question

如何在数组中实现 K 个堆栈，并具有最佳的存储利用率（堆栈应该是动态的）？

Answer 1

好吧，如果您只担心空间使用情况，而不关心堆栈操作可能需要 O(N)，您可以使用数组的前几个单元来管理堆栈：

Array[0] - 堆栈 0 的末尾

Array[1] - 堆栈 1 的末尾

...

Array[K-1] = 末尾堆栈 K 的堆栈

n 起始于Array[n-1] 并以 Array[n] 结束 （独占 - [Array[n-1], Array[n]) )。 如果 Array[n-1]==Array[n] 则堆栈为空。第一个堆栈从 K 开始，因此首先 Array[0]..Array[K-1] = K

压入堆栈时，只需将其下方堆栈中的所有元素移动即可，并且分别调整指针。

它会给你带来你需要的内存限制。

Answer 2

答案1：
在开始处存储K个堆栈指针。现在将其后的第一个地址标记为地址 0（让生活更简单）
偶数 K 个堆栈 (stack_0, stack_2, ...) 应该向上增长；奇数 K 个堆栈 (stack_1, ..) 应向下增长
初始化时将数组分段为 K/2 部分（为了简单起见，假设 K 是偶数）。
stack0从地址0开始
stack1 从 (arraySize / (k/2)) 开始并向下增长
stack3从(arraySize / (k/2))开始并向上增长，

当将数据推入某个堆栈时，我们应该确保它不会溢出到相邻堆栈，否则抛出异常。

该数组应如下所示：
[[堆栈指针][stack_0][stack_1]...[stack_k]] 其中 stack[0] 和 stack[1] 共享同一区域，以便它们可以最佳地利用可用空间。

可以通过将每个大堆栈与一个小堆栈配对来完成进一步的优化（这可以通过检查堆栈随时间的行为来完成）。此外，将快速变化的数组与缓慢变化的数组组合在一起可能会有所帮助。

答案2：
再想一想，我发现我的第一个解决方案仅保证使用 array_size/(k/2) （因为如果我们只有一个大小为 array_size/(k/2) 的数组，我们将出现堆栈溢出）。
以下（完全不切实际）解决方案可以满足要求：
我们为 k 堆栈指针分配数组的开头，并从现在开始忽略该区域。
在数组的其余部分中，我们将每个单元格视为一个结构体 [data, previous, next]。

推送（stack_i，数据）->从堆栈指针区域获取 sp_i。然后转到该地址，填写“下一个”指针以指向数组中的下一个空单元（我们可以将所有空空间在另一个堆栈中链接在一起，因此这是 o(1)）。在“下一个”单元格中存储我们的数据，并填写“上一个”指针。更新 sp_i

pop(stack_i) ->获取 sp_i。从该单元格获取“数据”。该单元格中的“prev”是我们的新 sp_i。将旧的（现在为空）单元格推入空列表。

Answer 3

噢噢，如果 K 也是动态的，那么你只需将 K 元素数组设为动态即可。让它变得更大仅仅意味着推倒所有的堆栈。所以如果你不介意 O(N) 的入栈和出栈操作，K 不应该是一个常数。

我想知道我是否得到了这份工作。

Answer 4

我将使用包含所有空闲槽的队列，并在添加或弹出数据时更新该队列。这样，空间复杂度为 O(N)，其中 N 是数组的大小。 pop 和 add 操作的时间复杂度为O(1)。

例如：你有一个大小为 S 的数组，其中有 K 个堆栈。您有一个队列，其中包含从 0 到 S-1 的所有空闲槽。您添加的第一个值将位于第一个空闲槽（索引 0）中。然后从队列中弹出索引 0。添加或弹出数据到哪个堆栈并不重要。如果弹出一个值，则会将删除节点的槽的索引排入队列，并相应地设置指针或索引。

这是 C++ 中的实现。我已经使用索引来指向下一个节点（毕竟我们使用的是数组），但是您可以使用指针或迭代器，这并不重要。

// TYPE: type of the stacks, SIZE: size of the array, STACKS: number of stacks
template <typename TYPE, size_t SIZE, size_t STACKS>
class KStacksInOneArray
{
// A node holds the data and a pointer or index to the next value
private:
    struct Node
    {
        TYPE data;
        int next = -1; // -1 is equivalent to nullptr:
                       // there is no next element
    };

public:
    KStacksInOneArray()
    {
        // initialize the free slots from 0 to SIZE - 1
        for (size_t idx = 0; idx < SIZE; ++idx)
            _freeSlots.push(idx);

        // initialize the heads, all to -1
        std::fill(_heads.begin(), _heads.end(), -1);
    }

    void pop(size_t stack)
    {
        // don't trust the user
        if (stack >= STACKS) throw std::out_of_range("there are only " + std::to_string(STACKS) + " stacks");
        if (isEmpty(stack)) throw std::out_of_range("cannot pop from an empty stack");

        // before destroying the node, get the new head  
        auto newHead = _arr[_heads[stack]].next;
        _arr[_heads[stack]] = Node{};

        // push the free slot on the queue and adjust the head
        _freeSlots.push(_heads[stack]);
        _heads[stack] = newHead;
    }

    const TYPE& top(size_t stack) const
    {
        if (stack >= STACKS) throw std::out_of_range("there are only 3 stacks");

        return _arr[_heads[stack]];
    }

    void add(size_t stack, TYPE data)
    {
        if (stack >= STACKS) throw std::out_of_range("there are only " + std::to_string(STACKS) + " stacks");
        if (_freeSlots.empty()) throw std::bad_alloc();

        // set the new node in the first free slot and 
        _arr[_freeSlots.front()] = {std::move(data), _heads[stack] != -1 ? _heads[stack] : -1};

        // update the head and remove the free slot from the queue
        _heads[stack] = _freeSlots.front();
        _freeSlots.pop();
    }

    bool isEmpty(size_t stack) const
    {
        if (stack >= STACKS) throw std::out_of_range("there are only " + std::to_string(STACKS) + " stacks");

        if (_heads[stack] == -1) return true;
        return false;
    }

private:
    std::vector<Node> _arr = std::vector<Node>(SIZE);
    std::array<int, STACKS> _heads;
    std::queue<int> _freeSlots;
};