Floodfill：堆栈与队列

Question

可以编写使用队列或堆栈的泛洪填充函数。在什么情况下哪个更快（如果有的话），为什么？

Answer 1

如果您正确实施它们，它们应该同样快。那就是避免递归，使用向量而不是链表来实现队列。

两者都具有 O(N) 复杂度（N 是要填充的单元格数）。

对于非常大的示例（我猜是 10k x 10k），您可以实施堆栈方法，以便您喜欢内存缓存行，这会给您带来一点优势。这很难正确、可靠地完成，因为它依赖于硬件。