algorithm - 为什么堆叠在凸包中

Question

我正在研究 Convex hull 和 Graham Scan 来实现它，它引起了我的注意，每个人都使用过堆栈。所以我想问一下，为什么在算法中使用堆栈，使用堆栈有什么好处？

Answer 1

这里的栈可以认为是一个抽象的数据结构，支持push、pop和empty操作。如果你阅读了格雷厄姆扫描算法的描述，你会发现这些正是该算法使用的操作，所以我真的看不出有什么可以替代堆栈 - 它可能是一个不同的算法。

可以相当自由地决定使用什么数据结构来支持/实现堆栈中的这些操作(即在 OO 术语中实现堆栈接口(interface)的类)。通常使用数组，但对于某些应用程序，链表也可能有意义。