我认为这将是一个堆栈，但它可以是一个跳过列表、bst 还是队列？
将它作为一个堆栈是有意义的，因为我们可以继续推入它并弹出。但是队列会更好吗，因为它按照它们进入的顺序添加它们？
问问题
574 次
1 回答
0
您自己基本上回答了一半：使用堆栈是有意义的，因为如果您使用递归，您可以按照编译器执行的相同顺序向堆栈推送和弹出堆栈。以人们期望的方式做事是一件好事（即使您可以以不同的方式做事）。
堆栈也是该问题最简单的解决方案，也是开销最小的容器，并且元素按照您在进行递归时通常想要的顺序出现，而无需您做任何特殊的事情。
相比之下，队列的复杂性要高得多，因为它有头和尾，而且内存管理也更复杂（堆栈基本上只是一块内存和一个递增/递减的指针）。
此外，当使用队列时，元素会按照您推入它们的顺序出现。这对于某些问题可能无关紧要（例如，如果您只想迭代每个元素一次并且不关心顺序），但它可以做到不必要的复杂回溯。例如，当递归细分数据块或递归遍历树时，您将首先递归到左半部分，然后再到左半部分，以此类推。
当您达到最大深度时，您将想要回溯一个级别并递归到右半部分（并回溯另一个级别，依此类推）。使用堆栈，只需简单的pop即可轻松完成。使用队列，您必须明确记住要去哪里。这当然不是不可能的，但也不是微不足道的。
您还提到了跳过列表。请注意，skiplist 并不是真正像“列表”那样简单的东西，而是一个相当复杂的结构，更类似于搜索树。它也不是问题的“自然选择”，并且由于它的复杂性绝对不是您想要用于递归之类的东西（尽管如果一个足够顽固，它可能会起作用）。
于 2012-12-01T23:02:02.840 回答