隊列中前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 = 2

10％因此，答案應該是19和20

有是我能想到的兩種方式

1. 對隊列進行排序，將項目數（X）分成N％和th抓住頂部的X元素。
2. Selection algorithm。 （我只是碰到這個算法及其基於快速排序的想法，所以我可能要在整個隊列複製到一個數組，然後應用算法）

有沒有什麼更好的辦法來解決這個問題？

Answer 1

隊列不是最好的數據結構，因爲你不應該訪問它裏面的元素（大多數隊列實現甚至不提供訪問操作符），所以你不應該對它進行排序。所以，如果你因爲其他需求而不需要隊列，我建議你使用普通數組。

排序是一個非常耗時的過程。當你讀/插入隊列元素時，你可以計算它們的總和。根據已知總和，元素數量和所需的百分比，可以計算閾值。然後，您需要遍歷元素（如果使用隊列，則可以逐個提取它們）並顯示大於計算閾值的元素。

Answer 2

您可以使用其他數據結構來保持元素的排序。例如，您可以使用skip list，訂購tiered vector或某些二進制搜索樹。

在大多數編程語言中都有一個內置的RB樹，但是，您將無法使用它。您需要在每個節點中添加有關左右子樹權重的信息。

Answer 3

您可以將二叉查找樹/'有序集'與您的隊列一起使用。

將元素添加到隊列的後面時，同時將其添加到集合中。 從隊列（的前面）中刪除元素時，您同時從該集中刪除它。

爲了在隊列中找到前N％的元素，可以從頂部元素遍歷該集合，直到下一個元素不符合前N％條件。這是因爲該集維護了隊列中元素的有序列表。

此外，由於您的原始隊列結構仍然存在，您仍然可以保留隊列中元素的相對順序。