爲什麼在凸包中堆積

Question

我正在重寫有關凸包和Graham Scan的實現方法，並引起了我的注意，即每個人都使用堆棧。所以我想問一問爲什麼在算法中使用堆棧，使用堆棧有什麼好處？

Answer 1

在建造船體時的格雷厄姆掃描中，如果點不與下一個考慮的點形成左轉，則需要回溯，因此以前的點需要重新考慮爲船體的有效點，因此我們使用堆棧來獲取它們按照上次訪問的順序進行重新驗證。雖然它不是強制使用堆棧，但也可以使用簡單的數組來執行相同的操作。

Answer 2

這裏的棧可以被認爲是支持push,pop和empty操作的抽象數據結構。如果您閱讀Graham Scan算法的描述，您會發現這些正是算法使用的操作，所以我實在看不出什麼可以替代堆棧 - 這可能會是一種不同的算法。

什麼樣的數據結構被用來在堆棧中支持/實現這些操作（即以OO術語來實現堆棧接口的類）可以自由決定。通常使用一個數組，但對於一些應用程序，鏈接列表也許有意義。