1

要素の最大値を見つけるために両端キューを使用するインターネットで見つけたコードについて質問があります-

 #include <iostream>
 #include <deque>

 using namespace std;


 void test(int arr[], int n)
 {    
   std::deque<int>  Qi(n); 
   int i;
   for (i = 0; i < n; ++i)
   {
      while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
        Qi.pop_back();  // Remove from rear

      Qi.push_back(i);
   }
  cout << arr[Qi.front()];   
}

// Driver program to test above functions
int main()
{
   int arr[] = {12, 1, 78, 90, 57, 89, 56};
   int n = sizeof(arr)/sizeof(arr[0]);    
   test(arr, n);
   return 0;
}

私の質問は、Qi.push_front（）を実行していないときに、Qi.front（）がどのように適切なインデックスを提供するかということです。

しかし、次のコードは私に0を与えます

  void test(int arr[], int n)
 {    
   std::deque<int>  Qi(n); 
   int i;
   for (i = 0; i < n; ++i)
   {           
      Qi.push_back(i);
   }
   cout << arr[Qi.front()];   
}

申し訳ありませんが、私が愚かに聞こえる場合..dequesは初めてです..。

ありがとう

4

1 に答える 1

3

std::deque<int> Qi(n);nすべてゼロの要素を持つ両端キューを作成します。操作はpush_back後ろにさらに要素を追加するので、後でdequeに2 * n要素があります。Qi.front()と同じですQi[0]。

これはすべて、たとえばここで十分に文書化されています。

于 2013-03-20T23:46:57.387 に答える