在一个数组算法中实现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]
(独占-[Array [n-1],Array [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屋!