求栈中元素个数(StackLength)的两个算法那个正确?

发布网友发布时间：2022-05-05 09:22

共3个回答

热心网友时间：2022-06-27 06:25

不正确，因为前面我们已经提到过，通过继承Vector，很大一部分功能的实现就由Vector涵盖了。Vector的详细实现我们会在后面分析。它实现了很多的辅助方法，给Stack的实现带来很大的便利。现在，我们按照自己的思路来分析每个方法的具体步骤，再和具体实现代码对比。
empty
从我们的思路来说，如果要判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。或者说我们有一个指向栈顶的变量，如果它开始的时候是设置为空的，我们可以认为栈为空。这部分的实现代码也很简单：
在这里，判断是否可以取栈顶元素在peek方法里实现了，也将如果栈为空则抛异常的部分包含在peek方法里面。这里有必要注意的一个细节就是，在通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。我们平时可能不太会留意到这一点。
为什么要移除呢？我们反正有一个elementCount来记录栈的长度，不管它不是也可以吗？
实际上，这么做在程序运行的时候会有一个潜在的内存泄露的问题。因为在java里面，如果我们普通定义的类型属于强引用类型。
比如这里vector就底层用的Object[]这个数组强类型来保存数据
。强类型在jvm中做gc的时候，只要程序中有引用到它，它是不会被回收的。这就意味着在这里，只要我们一直在用着stack，那么stack里面所有关联的元素就都别想释放了。这样运行时间一长就会导致内存泄露的问题。那么，为了解决这个问题，这里就是用的removeElementAt()方法。

热心网友时间：2022-06-27 06:26

这只是一个伪代码，就算法思想考虑都是正确的。
第一个逐一判断是否到底，否则累加1。
第二个直接用栈顶位置减去栈底位置。
前者要求内存空间连续，后者要求存放位置连续（比如数组下标）追问前者要求内存空间连续，后者要求存放位置连续（比如数组下标）....这个意思很奇怪，我写的栈是顺序存储的，存放在内存空间的位置连续

追答比如开新的栈空间的时候，又额外开辟了其它变量x的空间，这时候栈内元素的地址就不连续了，p--后就可以跑到x的地址上。
不过理解成伪代码我们可以认为它的p--就是到下一个元素的地址。
如果用容器vector里的stack就没有这个问题了。

看见了楼上的回复。
通常是用第一种方式的。因为栈通常都是指针操作，数组操作局限性太大学到后面就几乎不用了。动态链表实现时通常不会额外记录栈顶或栈底元素的地址。比较之下前者更好，后者更好写

热心网友时间：2022-06-27 06:26

感觉都正确，这两个没有什么区别啊。追问第二个算法是我自己写的，网上找打的居然都是第一个算法.....为什么？最优算法是？

追答这两个没有什么本质的区别，
就像一般的一维数组，告诉两个下标，让计算两者之间的元素个数，
方法1，就是直接拿下标相加减
方法2，就是让大的下标递减直到小的下标。
原理就是这个原理，这两个之间那个最好，我说不清楚，因为第二个里面牵涉到一系列的转换，这种转换我们是看不到的，当然第一个里面也有。