如何用一个数组实现3个堆栈？
Mic*_*ael 41 algorithm stack data-structures
有时,我遇到了以下面试问题:如何用一个数组实现3个堆栈？当然,任何静态分配都不是解决方案.
Dr.*_*ius 82
空间(不是时间)有效.你可以:
1)定义从阵列端点开始并以相反方向增长的两个堆栈.
2)将第三个堆栈定义为从中间开始并沿任何方向生长.
3)重新定义Push op,这样当操作将覆盖其他堆栈时,在推送之前将整个中间堆栈向相反方向移动.
您需要在前两个堆栈中存储堆栈顶部,在某些结构中存储第三个堆栈的开头和结尾.
编辑
上面你可能会看到一个例子.尽管可以根据您的问题启发式选择其他策略,但是使用相等的空间分区策略完成转换.
编辑
根据@ ruslik的建议,中间堆栈可以使用交替序列实现后续推送.生成的堆栈结构将类似于:
| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |
在这种情况下,您需要在中间堆栈上存储n个元素并使用该函数:
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3
知道用于此堆栈的下一个数组元素.
虽然这可能会导致更少的转移,但是三个堆栈的实现并不均匀,并且不均匀性(您知道)导致特殊情况,更多错误和维护代码的困难.
- 一个小问题,但最好在阵列的1/3处开始中间堆栈,而不是在中点.假设堆栈平均以大约相同的速率填充,这意味着您可以等待更长时间来进行第一次大动作. (4认同)
- @ruslik当然有可能.只需将数组用作链接列表即可.但是你浪费了很多空间,并且它不知何故违背了"使用数组"的概念. (2认同)
- @belisarius:一个简单的改进:你可以"推"`BS3`:BS3,BS3 + 1,BS3-1,BS3 + 2,BS3-2等等.这将使第三个堆栈保持在中间,并且将接近堆栈2的速度的一半.这让我想起了关于`f(f(n))== - n的一个很好的问题;` (2认同)
- @hugh因为如果没有，则必须保存指针，而我试图提供一种节省空间的解决方案，所以我不允许为指针留出额外的空间。 (2认同)
只要您尝试将一个堆栈中的所有项目排列在阵列的一个"末端",就会缺少第三个堆栈的空间.
但是,您可以"散布"堆栈元素.第一堆栈的i * 3元素位于索引处,第二堆栈的i * 3 + 1元素位于索引处,第三堆栈的元素位于索引处i * 3 + 2(其中i是整数).
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : B1 : C1 | A2 : B2 : C2 | : B3 | C3 | : B4 : | :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top C´s top B´s top
当然,这种方案会浪费空间,特别是当堆栈的尺寸不相等时.您可以创建类似于上述方案的任意复杂方案,但不知道对提出的问题有任何更多限制,我将在此处停止.
更新:
由于下面的评论确实有一个非常好的观点,因此应该补充说,没有必要进行散布,与更简单的内存布局相比,甚至可能会降低性能,如下所示:
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : A2 : : : | B1 : B2 : B3 : B4 : | C1 : C2 : C3 :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top B´s top C´s top
即给每个堆栈它自己的连续内存块.如果真正的问题确实是如何尽可能最好地使用固定数量的内存,为了不限制每个堆栈超过必要,那么我的答案将不会是非常有帮助的.
在那种情况下,我会选择@belisarius的回答:一个堆栈进入内存区域的"底部"端,增长"向上"; 另一个堆栈进入内存区域的"顶部"端,"向下"增长,并且一个堆栈位于中间,在任何方向上增长,但是当它太靠近其他堆栈之一时能够移动.
- 这与将数组任意划分为三个相同大小的静态分配部分有何不同？ (6认同)
- 它实际上更糟糕.最有可能的是它们不会以相同的速度使用,每个堆栈将使用不同的缓存线,因此使用3倍的内存带宽.3个明显不同的堆栈将具有更好的局部性.此外,问题的主要问题是将总大小限制在可用空间,而不是每一个到三分之一. (4认同)
为所有三个筹码维持一个竞技场.推入堆栈的每个元素都有一个指向其前一个元素的向后指针.每个堆栈的底部都有一个指向NULL/None的指针.
竞技场维护指向可用空间中下一个项目的指针.推送将此元素添加到相应的堆栈,并将其标记为不再位于空闲空间中.弹出窗口从相应的堆栈中删除元素并将其添加到空闲列表中.
从这个草图中,堆栈中的元素需要一个反向指针和数据空间.自由空间中的元素需要两个指针,因此可用空间实现为双向链表.
包含三个堆栈的对象需要一个指向每个堆栈顶部的指针以及一个指向空闲列表头部的指针.
此数据结构使用所有空间,并在恒定时间内推送和弹出.堆栈中的所有数据元素都有单个指针的开销,而空闲列表元素使用最大值(两个指针,一个指针+一个元素).
后来:python代码就是这样的.注意使用整数索引作为指针.
class StackContainer(object):
def __init__(self, stack_count=3, size=256):
self.stack_count = stack_count
self.stack_top = [None] * stack_count
self.size = size
# Create arena of doubly linked list
self.arena = [{'prev': x-1, 'next': x+1} for x in range(self.size)]
self.arena[0]['prev'] = None
self.arena[self.size-1]['next'] = None
self.arena_head = 0
def _allocate(self):
new_pos = self.arena_head
free = self.arena[new_pos]
next = free['next']
if next:
self.arena[next]['prev'] = None
self.arena_head = next
else:
self.arena_head = None
return new_pos
def _dump(self, stack_num):
assert 0 <= stack_num < self.stack_count
curr = self.stack_top[stack_num]
while curr is not None:
d = self.arena[curr]
print '\t', curr, d
curr = d['prev']
def _dump_all(self):
print '-' * 30
for i in range(self.stack_count):
print "Stack %d" % i
self._dump(i)
def _dump_arena(self):
print "Dump arena"
curr = self.arena_head
while curr is not None:
d = self.arena[curr]
print '\t', d
curr = d['next']
def push(self, stack_num, value):
assert 0 <= stack_num < self.stack_count
# Find space in arena for new value, update pointers
new_pos = self._allocate()
# Put value-to-push into a stack element
d = {'value': value, 'prev': self.stack_top[stack_num], 'pos': new_pos}
self.arena[new_pos] = d
self.stack_top[stack_num] = new_pos
def pop(self, stack_num):
assert 0 <= stack_num < self.stack_count
top = self.stack_top[stack_num]
d = self.arena[top]
assert d['pos'] == top
self.stack_top[stack_num] = d['prev']
arena_elem = {'prev': None, 'next': self.arena_head}
# Link the current head to the new head
head = self.arena[self.arena_head]
head['prev'] = top
# Set the curr_pos to be the new head
self.arena[top] = arena_elem
self.arena_head = top
return d['value']
if __name__ == '__main__':
sc = StackContainer(3, 10)
sc._dump_arena()
sc.push(0, 'First')
sc._dump_all()
sc.push(0, 'Second')
sc.push(0, 'Third')
sc._dump_all()
sc.push(1, 'Fourth')
sc._dump_all()
print sc.pop(0)
sc._dump_all()
print sc.pop(1)
sc._dump_all()
为了简单起见,如果不是非常有效的内存使用,你可以[*]将数组划分为列表节点,将它们全部添加到空闲节点列表中,然后将堆栈实现为链表,根据需要从空闲列表中获取节点.但是,这种方法中的数字3并没有什么特别之处.
[*]在低级语言中,其中内存可用于存储指针,或者堆栈元素的类型int是否可以表示数组的索引.
小智 5
我有一个解决这个问题的方法.以下程序充分利用了数组(在我的例子中,是一个StackNode对象数组).如果你们对此有任何疑问,请告诉我.[这里已经很晚了,所以我没有费心去记录代码 - 我知道,我应该:)]
public class StackNode {
int value;
int prev;
StackNode(int value, int prev) {
this.value = value;
this.prev = prev;
}
}
public class StackMFromArray {
private StackNode[] stackNodes = null;
private static int CAPACITY = 10;
private int freeListTop = 0;
private int size = 0;
private int[] stackPointers = { -1, -1, -1 };
StackMFromArray() {
stackNodes = new StackNode[CAPACITY];
initFreeList();
}
private void initFreeList() {
for (int i = 0; i < CAPACITY; i++) {
stackNodes[i] = new StackNode(0, i + 1);
}
}
public void push(int stackNum, int value) throws Exception {
int freeIndex;
int currentStackTop = stackPointers[stackNum - 1];
freeIndex = getFreeNodeIndex();
StackNode n = stackNodes[freeIndex];
n.prev = currentStackTop;
n.value = value;
stackPointers[stackNum - 1] = freeIndex;
}
public StackNode pop(int stackNum) throws Exception {
int currentStackTop = stackPointers[stackNum - 1];
if (currentStackTop == -1) {
throw new Exception("UNDERFLOW");
}
StackNode temp = stackNodes[currentStackTop];
stackPointers[stackNum - 1] = temp.prev;
freeStackNode(currentStackTop);
return temp;
}
private int getFreeNodeIndex() throws Exception {
int temp = freeListTop;
if (size >= CAPACITY)
throw new Exception("OVERFLOW");
freeListTop = stackNodes[temp].prev;
size++;
return temp;
}
private void freeStackNode(int index) {
stackNodes[index].prev = freeListTop;
freeListTop = index;
size--;
}
public static void main(String args[]) {
// Test Driver
StackMFromArray mulStack = new StackMFromArray();
try {
mulStack.push(1, 11);
mulStack.push(1, 12);
mulStack.push(2, 21);
mulStack.push(3, 31);
mulStack.push(3, 32);
mulStack.push(2, 22);
mulStack.push(1, 13);
StackNode node = mulStack.pop(1);
node = mulStack.pop(1);
System.out.println(node.value);
mulStack.push(1, 13);
} catch (Exception e) {
e.printStackTrace();
}
}
}
本页已经说明了此问题的许多解决方案。恕我直言，基本问题是：
每次push/pop操作需要多长时间？
使用了多少空间？具体来说，最少可以将多少个元素压入三个堆栈，从而导致数据结构空间不足？
据我所知，此页面上已发布的每个解决方案要么会占用线性时间来进行推送/弹出，要么可能会耗尽空间，而线性数量的空间仍然为空。
在这篇文章中，我将参考性能更好的解决方案，并且我将介绍最简单的一个。
为了更仔细地描述解空间，我将按以下方式引用数据结构的两个函数：
需要 O(f(n)) 摊销时间来执行压入/弹出且不会耗尽空间的结构，除非三个堆栈至少容纳 n - O(g(n)) 项，该结构将被称为( f,g) 结构。f 和 g 越小越好。此页面上已发布的每个结构都有 n 表示时间或空间。我将演示一个 (1,√n) 结构。
这一切都是基于：
Michael L. Fredman 和 Deborah L. Goldsmith，“三个堆栈”，《算法杂志》，第 17 卷，第 1 期，1994 年 7 月，第 45-70 页
- 早期版本出现在 1988 年第 29 届计算机科学基础年度研讨会 (FOCS) 上
Deborah Louise Goldsmith 于 1987 年在加州大学圣地亚哥分校电气工程/计算机科学系发表的博士论文，“Efficient memory management for >= 3 stacks”
尽管我不会展示，但它们显示了任何 S 的 (log n/log S,S) 结构。这相当于任何 t 的(t, n 1/t ) 结构。我将展示一个简化版本，即 (1,√n) 结构。
将数组分成大小为 θ(√n) 的块。块的编号从 1 到 θ(√n)，块的编号称为它的“地址”。地址可以存储在数组槽中，而不是实际的项目中。给定块内的项目可以用小于 O(√n) 的数字来引用，这样的数字称为索引。索引也适合数组槽。
第一个块将被留出用于存储地址和索引，并且没有其他块将存储任何地址或索引。第一个块称为目录。每个非目录块要么为空，要么仅包含三个堆栈之一的元素；也就是说，任何块都不会有来自不同堆栈的两个元素。此外，每个堆栈最多有一个部分填充的块——与堆栈关联的所有其他块将完全满或完全空。
只要有空块，就允许对任何堆栈进行推送操作。Pop 操作始终是允许的。当推送操作失败时，数据结构已满。此时，不包含来自其中一个堆栈的元素的槽的数量最多为 O(√n)：来自未压入堆栈的两个部分填充的块，以及一个目录块。
每个块都经过排序，以便靠近块前面的元素（较低的索引）更靠近堆栈的底部。
该目录包含：
三个堆栈顶部的块的三个地址，如果特定堆栈中还没有块，则为 0
三个堆栈顶部元素的三个索引，如果特定堆栈中还没有项目，则为 0。
对于每个完整或部分完整的块，同一堆栈中比它低的块的地址，如果它是堆栈中最低的块，则为 0。
空闲块的地址，称为领导块，如果没有空闲块则为 0
对于每个空闲块，另一个空闲块的地址，如果没有更多空闲块，则为 0
最后两个构成一个堆栈，存储为空闲块的单链表。也就是说，跟随从引导块开始的空闲块的地址将给出一条通过所有空闲块的路径，以 0 结尾。
要将项目推入堆栈，请使用目录查找其顶部块和该块内的顶部元素。如果该区块中有空间，请将物品放在那里并返回。
否则，通过将引导块的地址更改为空闲块堆栈中下一个空闲块的地址来弹出空闲块堆栈。将堆栈的地址和索引分别更改为刚刚弹出的空闲块的地址和 1。将项目添加到索引 1 处刚刚弹出的块中，然后返回。
所有操作都需要 O(1) 时间。波普是对称的。