algorithm - 如何从堆栈中搜索项目？

Question

当我读一些书时，我看到，从堆栈中搜索一个项目的时间复杂度是 O(n)。但我很困惑，我怎么能从堆栈中搜索一个中间值，因为它是一个 LIFO。

Answer 1

堆栈通常实现为数组或链表，您可以通过其中任何一个进行迭代。

如果您有一个不为您提供迭代器的纯堆栈 API：

您必须将元素弹出到不同的堆栈，直到找到该元素，然后将它们推回。

在此之后，我们将堆栈恢复到原来的样子。

Answer 2

因为 O(n) 是线性复杂度，所以您必须弹出每个元素，直到找到匹配项。因此，搜索时间随着元素的数量而增长。

Answer 3

正如 Duekling / Duncan 非常敏锐地描述的那样，您可能想要创建一个带有计数的堆栈，然后分成两个。让 s1 和 s2 指向两个栈，所以当你在 s1 中 push 两个项目时，第一个节点成为 s2 的顶部，最后进入的节点成为 s1 的顶部。然后再添加两个项目，计数变为 4 ，将 item3 推到 s2 上，项目 4 保留在 s1 上。