我对在互联网上找到的代码有疑问,该代码使用双端队列来查找元素的最大值 -
#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()];
}
抱歉,如果我听起来很愚蠢......双端队列新手......
谢谢
最佳答案
std::deque<int> Qi(n);
使用 n
创建一个双端队列元素,全部为零。 push_back
操作在后面添加更多元素,因此双端队列之后有 2 * n
元素。 Qi.front()
与 Qi[0]
相同.
所有这些都有详细记录,例如here .
关于c++ - 双端队列实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15536901/