使用1个数组实现3个堆栈,这个代码可以工作吗?
这是我在算法/面试问题书上发现的,其他人在这个问题上有几个帖子,但我还有一些问题,这里是原始文本和书中的代码:
implement 3 stacks using 1 array: Approach 2: 在这种方法中,只要阵列中有任何空闲空间,任何堆栈都可以增长. 1 int stackSize = 300; 2 int indexUsed = 0; 3 int[] stackPointer = {-1,-1,-1}; 4 StackNode[] buffer = new StackNode[stackSize * 3]; 5 void push(int stackNum,int value) { 6 int lastIndex = stackPointer[stackNum]; 7 stackPointer[stackNum] = indexUsed; 8 indexUsed++; 9 buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value); 10 } 11 int pop(int stackNum) { 12 int value = buffer[stackPointer[stackNum]].value; 13 int lastIndex = stackPointer[stackNum]; 14 stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous; 15 buffer[lastIndex] = null; 16 indexUsed--; 17 return value; 18 } 19 int peek(int stack) { return buffer[stackPointer[stack]].value; } 20 boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; } 21 22 class StackNode { 23 public int previous; 24 public int value; 25 public StackNode(int p,int v){ 26 value = v; 27 previous = p; 28 } 29 } 我的问题是:在mothod pop()中,将缓冲区[lastIndex]设置为null(第15行),然后indexUsed – (第16行),indexUsed会是空白的头部吗? index: 10 11 12 13 ------------------------------- | ... | s1 | s2 | s3 | null | ------------------------------- indexUsed现在是13. index: 10 11 12 13 ---------------------------------- | ... | null | s2 | s3 | null | ---------------------------------- 而indexUsed现在是13–,即12, added: 以及如何更改它以使其工作? 谢谢! 解决方法
据我所知,你是对的 – 它没有存储足够的信息来指示内存中的漏洞.
堆栈的一大优势是可以在数组列表之上分配它而不是链接列表来保存前一个/下一个指针的内存 – 这种实现消除了这一优势 – 很难想象一个应用程序这实际上是一个很好的解决方案. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |