可以使用堆栈或队列更快地解决的问题示例
Example of a problem which can be solved faster using stack or queue
昨天才知道还有数组以外的数据结构。我了解排序数组的用处：如果您必须进行多次查找，那么先排序然后再进行查找更快。
但是，我很好奇看到一个问题可以通过实现和使用堆栈或队列来更快解决，而不是使用旧数组。
我在网上搜索了很多关于“plates”和“pancakes”的有趣解释，但我还没有看到一个具体的程序或算法利用堆栈或队列来提高性能。
使用排序数组的示例
考虑在 n 个元素的数组中进行 m 查找的问题。如果直接看的话，最坏的情况下还要付出n * m次操作。现在，如果您首先对数组进行排序（例如，使用合并排序），您最多需要支付 c * nlog(n)（其中 c 是某个常数），然后对于每个 m 查找您可以进行二分查找，只需支付 k * log(n)（其中 k 是另一个常数），因此总共支付 c * nlog(n) + m * k * log(n)，这比 m * n 要好得多，如果 [=11] =]很大，m很大。
但是
数组是一种基本的数据结构。其实计算机内存就是一个数组，既然我们可以用计算机内存来解决各种问题，我们总可以说我们是用数组来解决的。
队列和栈是更高层次的结构，具有特定的（也是约束性的）规则，有时直接用数组实现，只需要一些逻辑来维护一两个indexes/pointers。
所以本质上：你可以用队列或堆栈解决的问题，你也可以用数组解决（具有相同的时间复杂度）。
现在，您还提到了 排序 数组。它们确实有用。但是，当算法必须定期向其添加新值并保持数组排序时，它可能会变得低效。这导致您可能会查看其他一些数据结构：a binary heap.
就像堆栈和队列一样，二叉堆也可以“只是”数组，二叉堆通常 实现为数组。但是堆允许以 O(logn) 时间复杂度从中提取最小值，而无需首先对其应用 O(nlogn) 排序算法。数组可以在线性时间内变成堆。它还允许在 O(logn) 时间内向其中插入一个新值。排序数组无法提供这一点，因为平均而言，它涉及移动 O(n) 值以为新值腾出空间。
堆可以作为优先队列的实现。例如，堆对于加权图中的高效 best-first searches 很有用。
结论：与数组进行比较并不能真正告诉我们任何信息：堆栈、队列、排序数组和堆是（可以是）数组。真正具有决定性的是：用于对数据执行基本操作（例如构建、插入、删除和查找）的逻辑是什么？当我们谈论数据结构时，我们默默地包括它们含义中的基本逻辑：堆栈、队列和堆是（可以是）具有特定规则和智能操作的数组。
昨天才知道还有数组以外的数据结构。我了解排序数组的用处：如果您必须进行多次查找，那么先排序然后再进行查找更快。
但是，我很好奇看到一个问题可以通过实现和使用堆栈或队列来更快解决，而不是使用旧数组。
我在网上搜索了很多关于“plates”和“pancakes”的有趣解释，但我还没有看到一个具体的程序或算法利用堆栈或队列来提高性能。
使用排序数组的示例
考虑在 n 个元素的数组中进行 m 查找的问题。如果直接看的话，最坏的情况下还要付出n * m次操作。现在，如果您首先对数组进行排序（例如，使用合并排序），您最多需要支付 c * nlog(n)（其中 c 是某个常数），然后对于每个 m 查找您可以进行二分查找，只需支付 k * log(n)（其中 k 是另一个常数），因此总共支付 c * nlog(n) + m * k * log(n)，这比 m * n 要好得多，如果 [=11] =]很大，m很大。
但是
数组是一种基本的数据结构。其实计算机内存就是一个数组，既然我们可以用计算机内存来解决各种问题，我们总可以说我们是用数组来解决的。
队列和栈是更高层次的结构，具有特定的（也是约束性的）规则，有时直接用数组实现，只需要一些逻辑来维护一两个indexes/pointers。
所以本质上：你可以用队列或堆栈解决的问题，你也可以用数组解决（具有相同的时间复杂度）。
现在，您还提到了 排序 数组。它们确实有用。但是，当算法必须定期向其添加新值并保持数组排序时，它可能会变得低效。这导致您可能会查看其他一些数据结构：a binary heap.
就像堆栈和队列一样，二叉堆也可以“只是”数组，二叉堆通常 实现为数组。但是堆允许以 O(logn) 时间复杂度从中提取最小值，而无需首先对其应用 O(nlogn) 排序算法。数组可以在线性时间内变成堆。它还允许在 O(logn) 时间内向其中插入一个新值。排序数组无法提供这一点，因为平均而言，它涉及移动 O(n) 值以为新值腾出空间。
堆可以作为优先队列的实现。例如，堆对于加权图中的高效 best-first searches 很有用。
结论：与数组进行比较并不能真正告诉我们任何信息：堆栈、队列、排序数组和堆是（可以是）数组。真正具有决定性的是：用于对数据执行基本操作（例如构建、插入、删除和查找）的逻辑是什么？当我们谈论数据结构时，我们默默地包括它们含义中的基本逻辑：堆栈、队列和堆是（可以是）具有特定规则和智能操作的数组。