java - pop() 功能如何在 Java 的堆栈中工作？

Question

我在网上搜索了Java中pop()函数的代码实现。我经常看到计数器（堆栈顶部所在的位置）减少了 1，有效地使其无法访问，但在被覆盖之前不会完全删除它。这也是它在语言中的实现方式，还是因为它们使用数组来实现堆栈功能？此外，该语言是否使用数组、链表或其他一些数据结构来实现堆栈？谢谢！

标签： java

Answer 1

作为记录，自从我在下面写下答案以来，这个问题已经改变了。该问题最初讨论的是队列和堆栈。现在标题只询问队列，而问题的主体只讨论堆栈。

---

问题的标题提到了队列和堆栈，但它们不是一回事。队列是一种结构，在通常情况下，它实现了先进先出规则（双端队列——对于双端队列——是另一回事）。想想公共汽车的队列：第一个到达公共汽车站的人应该是公共汽车到达时第一个上车的人。相比之下，堆栈显示后进先出行为。该名称倾向于表明：项目“堆叠”在另一个之上，而位于顶部的（最后放置的）是可访问的。

queue在Java中是一个接口，而不是一个类，所以有不止一个实现。JDK 7 列出了 13 个已知的实现类。只要pop满足删除前面（最旧）元素的语义，它就可以正确地完成工作。但是pop，对于队列上的方法来说，这是一个不恰当的名称，实际上java.util.queue接口并没有定义pop.

与Java 不同的是queue，stack它是一个类而不是接口，它基于旧vector类。因此，我想最后插入的项目在向量中具有最高的索引，并且pop只是将其删除。就像是

    E pop() { remove(size()-1); }

或者至少是一个逻辑等价的序列。这是基于向量的明显实现。正如在别处所指出的，如果实现还清空了向量中现在不可访问的单元格，这将很有用，这样它就不会保留对不再“在”堆栈中的对象的引用。