java - 我如何知道何时使用 Stack 而不是其他 Collections？

Question

这是我想知道的更普遍的问题的一个小序曲:

我最近在做一个编程挑战，你应该编写一个方法来检查给定字符串中括号的平衡。该方法应该接受一个字符串并返回第一个额外的 ')' 或 '(' 括号所在的索引，或者如果它们相等则返回字符串的长度。一些示例输入将像这样:")( asdf)))"- 0; “((((asdf)))”- 0；“((((asdf))”- 1；“(ab)(((cd)(asdf)”- 5。

我首先尝试为括号的每个方向创建一个列表，它将所有括号的索引存储在字符串中。然后我将遍历字符串中的每个字符，如果匹配则将其索引添加到任一列表，并检查它们是否已经不匹配。这种策略对某些情况有效，但某些情况仍然失败。感觉卡住了，我检查了挑战中的其他一些答案，看到他们使用 Stack 来存储左括号的索引，必要时他们会插入和弹出。这种方法很管用，好多了，我为自己没有想到它而感到有点尴尬。

这让我想到了我的问题……我怎么知道什么时候使用 Stack 比其他各种 Collections 更好？有哪些常见的事情会提示我使用 Stack 而不是任何其他 Collection？

我知道 Stacks 是如何工作的，并在一些教程等中使用过它们，但从未真正发现自己在现实世界中使用过它们......在看到它们通过挑战创造的简单性之后，让我觉得我已经错过了一些制作更简单/更好代码的机会。

Answer 1

堆栈的另一个很好的例子是当你进入一些你最终会离开的“上下文”时。如果您存储一些仅在这两个时刻之间有效并且一旦离开此“上下文”就可能被遗忘的信息，则更是如此。

在括号示例中，只要匹配 ( 和“离开”匹配 ) 的括号 block ，就会“进入”。当你在括号内时，你需要记住起始 ( 的位置(以防它没有匹配的 ))，但是一旦你找到匹配的 ) 你可以忘记这些信息。