加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

使用1个数组实现3个堆栈,这个代码可以工作吗?

发布时间:2020-12-15 02:34:18 所属栏目:Java 来源:网络整理
导读:这是我在算法/面试问题书上发现的,其他人在这个问题上有几个帖子,但我还有一些问题,这里是原始文本和书中的代码: implement 3 stacks using 1 array:Approach 2: 在这种方法中,只要阵列中有任何空闲空间,任何堆栈都可以增长. 我们按顺序为堆栈分配空间,并将
这是我在算法/面试问题书上发现的,其他人在这个问题上有几个帖子,但我还有一些问题,这里是原始文本和书中的代码:

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会是空白的头部吗?
让我们调用第一个堆栈的Stack Top节点:S1,第二个堆栈:S2,第三个堆栈:S3;
会发生什么:
在我想要弹出s1之前,我有s1后跟s2和s3

index:    10   11   12    13
-------------------------------
| ...   | s1 | s2 | s3 | null |
-------------------------------

indexUsed现在是13.
现在,如果我想在第一个堆栈上执行pop(),
它会变成:

index:     10    11   12    13
----------------------------------
| ...   | null | s2 | s3 | null |
----------------------------------

而indexUsed现在是13–,即12,
所以如果我想将一个新的Node推到这个阵列上会发生什么,
根据push()方法,在第7行,indexUsed被赋值给stackPointer并用作数据的推送索引,不会覆盖第12个条目中的s3(stack3的顶层节点)吗?

added:

以及如何更改它以使其工作?
乍一看,我会考虑实现一个boolean []来跟踪存储阵列中每个条目的使用情况,但这会消耗时间和空间.

谢谢!

解决方法

据我所知,你是对的 – 它没有存储足够的信息来指示内存中的漏洞.

堆栈的一大优势是可以在数组列表之上分配它而不是链接列表来保存前一个/下一个指针的内存 – 这种实现消除了这一优势 – 很难想象一个应用程序这实际上是一个很好的解决方案.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读