的Deque實現

Question

我有一個關於我在互聯網上找到的代碼，它使用一個deque尋找元素的最大問題 -

#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.front（）時給予正確的索引我還沒有做過任何Qi.push_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()]; 
} 

很抱歉，如果我聽起來愚蠢的。新來雙端...

感謝

Answer 1

std::deque<int> Qi(n);創建一個雙端隊列n元素，全部爲零。 push_back操作在後面添加了更多元素，因此後來該元素有2 * n元素。 Qi.front()與Qi[0]相同。

所有這些都有很好的記錄，例如， here。