在一个数组算法中实现 K 个堆栈 [英] Implementing K stacks in one array algorithm

问题描述

如何在一个数组中实现 K 个堆栈，并具有最佳的存储使用率(堆栈应该是动态的)?

How to implement K stacks in an array, with best storage usage (stacks should be dynamic)?

推荐答案

好吧，如果你只担心空间使用，而不关心栈操作会占用O(N)，您可以使用数组的前几个单元格来管理堆栈:

Well, if you're only worried about space usage, and don't care that stack operations can take O(N), you can use the array's first few cells to manage the stacks:

Array[0] - 栈尾 0

Array[1] - 栈 1 的结尾

...

Array[K-1] = 栈尾 K

Stack n 从 Array[n-1] 开始，到 Array[n] 结束 (exclusive - [Array[n-1], 数组[n]) ).如果 Array[n-1]==Array[n] 堆栈为空.第一个堆栈从 K 开始，所以首先 Array[0]..Array[K-1] = K

Stack n starts at Array[n-1] and ends at Array[n] (exclusive - [Array[n-1], Array[n]) ). If Array[n-1]==Array[n] the stack is empty. The first stack starts at K, so at first Array[0]..Array[K-1] = K

入栈时，只需移动其下方栈中的所有元素，分别调整指针即可.

When you push into a stack, just move all the elements in the stacks below it, and adjust the pointers respectively.

它将为您提供所需的内存限制.

It'll get you the memory constraint you need.

这篇关于在一个数组算法中实现 K 个堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！