我正在研究 Convex hull 和 Graham Scan 来实现它，它引起了我的注意，每个人都使用过堆栈。所以我想问一下为什么算法中精确使用了堆栈，使用堆栈有什么好处？
问问题
268 次
2 回答
3
这里的栈可以看成是支持push,pop和empty操作的抽象数据结构。如果您阅读 Graham Scan 算法的描述，您会发现这些正是该算法使用的操作，所以我真的看不出有什么可以替代堆栈 - 那时它可能是一种不同的算法。
可以相当自由地决定使用什么数据结构来支持/实现堆栈中的这些操作（即实现 OO 术语中的堆栈接口的类）。通常使用数组，但对于某些应用程序，链表也可能有意义。
于 2013-12-23T23:05:49.737 回答
0
在构建船体的格雷厄姆扫描中，如果点没有与下一个考虑的点形成左转，则需要回溯，因此需要将先前的点重新考虑为船体的有效点，因此我们使用堆栈按最后的顺序获取它们首先访问以进行重新验证。虽然使用堆栈不是强制性的，但您也可以使用简单的数组来做同样的事情。
于 2013-12-24T04:31:25.397 回答