algorithm - 队列中的前 n 个元素

Question

我已经使用两个堆栈实现了一个队列，我想找到队列中前 N% 的元素。

例如:
队列按此顺序获取元素 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19, 20}

前 10% 的元素表示 20 的 10% = 2

因此答案应该是 19 和 20

我能想到的有两种方法

1. 对队列进行排序，计算 N% 的项目数 (X)，然后获取前 X 个元素。
2. Selection algorithm . (我刚刚遇到这个算法，它基于快速排序的思想。所以我可能必须将整个队列复制到一个数组中，然后应用该算法)

有没有更好的办法解决这个问题？

Answer 1

队列不是最好的数据结构，因为你不应该访问其中的元素(大多数队列实现甚至不提供访问运算符)所以你不应该对它进行排序。所以，如果你因为一些其他需求不需要队列，我建议你使用普通数组。

排序是一个非常耗时的过程。当您读取/插入队列元素时，您可以计算它们的总和。根据已知的总和、元素的数量和所需的百分比，您可以计算出一个阈值。然后，您需要遍历元素(如果使用队列，您可以一个一个地提取它们)并显示那些大于计算阈值的元素。