java - 使用 Stack 上 Vector 类的 remove(item) 是否会保持 O(1) 弹出、查看、推送运行时间？

Question

在我之前的问题 ( Calculating Space Complexity of Stack Search ) 中，有人说您不应该在堆栈中使用 search(item) 或 remove(item)。我选择堆栈的原因是，如果您始终采用后进先出法，则弹出而不是访问 array.length-1 似乎更容易。

使用这些非传统堆栈操作会影响弹出、查看和推送的 O(1) 运行时间吗？

Answer 1

Will using remove(item) from Vector class on a Stack maintain O(1) pop, peek, push run times?

这取决于 remove 是如何实现的以及 Stack 的底层实现是什么(在这种情况下，你说它是一个 Java Vector，所以它取决于Vector.remove 是如何实现的)。

如果底层数据结构是基于链表的，那么我们必须迭代到我们要删除的位置，这是一个O(n)操作，其中n 是 vector 的长度。如果底层数据结构是基于数组的，那么它是一个 O(1) 索引，可以到达我们想要删除的位置。这里的问题是，如果我们想删除数组开头的一个元素，那么我们必须将每个元素向左移动，这是一个线性时间操作。因此，这也有一个 O(n) 最坏情况。

在 Java 中，Vector 类是使用数组作为底层结构实现的。这意味着如果 Stack.pop 实现查找 Vector 中的最后一个元素，则 Vector 将不必移动任何元素，并且因此运行时间为 O(1)。

这个问题的 tl;dr 是“有时”。

Would using these non traditional stack operations impact O(1) runtimes of pop, peek, and push?

search 肯定是一个 O(n) 操作(即，它通过查找您请求的元素进行迭代)。

要回答这个问题，使用这些非传统堆栈操作将不会影响pop、peek 的 O(1) 运行时间，和推送。也就是说，search 和 remove 本身确实具有 O(n) 的运行时间。