设计一个队列数据结构，在 O(1) 时间内获取最小值或最大值
C++ 有一个 deque 头文件，用于处理堆栈和队列的属性。在数据结构中，为了以 O(1) 时间复杂度解决问题，需要常数时间。通过在此程序中使用 deque，我们可以同时使用堆栈和队列。
在本文中，我们将解决队列数据结构，以在 O(1) 时间内获取数字的最小值或最大值。
语法
deque<data_type> name_of_queue;
参数
deque − 这是双端队列，它按顺序排列一组项目或与队列等同的数字。
data_type − 使用的数据类型，如 int、float 等。
name_of_queue − 为队列指定的任何名称，如 ab、cd 等。
front()
front() 是 C++ STL 中的预定义函数，它直接引用队列的第一个索引位置。
back()
back() 是 C++ STL 中的预定义函数，它直接引用最后一个队列的索引位置。
push_back()
push_back() 也是一个预定义函数，用于从后面插入元素。
算法
我们将使用头文件 'iostream' 和 'deque' 启动程序。
我们插入双端队列来处理数字的最大值或最小值。
"deque<int> dq" − 通过使用它，我们可以启用堆栈和队列的属性
从 for 循环开始，我们插入一个从 10 到 15 范围的元素。然后使用名为 'push_back[i]' 的方法，该方法接受 'i' 作为参数，使用 for 循环推送数组元素。
然后，我们创建两个变量，通过使用预定义函数 front() 和 back() 来查找数字的最小值和最大值。 front() 查找第一个索引以显示最小数字，而 back() 查找最后一个索引以显示最大数字。
现在我们初始化 for 循环以迭代索引号长度，并使用此长度将最小和最大元素的比较分类为 'dq[i]'。 因此这将找到最小和最大数字。
最后，我们借助 'min_element' 和 'max_element' 变量打印最小和最大长度的输出。
示例
在此程序中，我们将解决队列数据结构以在 O(1) 时间内获得最小值和最大值。
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
// 双端队列
// 使用循环将元素插入双端队列
for(int i = 10; i <= 15; i++) {
dq.push_back(i);
}
// 查找最小和最大元素
int min_element = dq.front();
int max_element = dq.back();
for(int i = 1; i < dq.size(); i++) {
if(dq[i] < min_element) {
min_element = dq[i];
}
if(dq[i] > max_element) {
max_element = dq[i];
}
}
//打印最小和最大元素
cout << "最小元素:" << min_element << endl;
cout << "最大元素:" << max_element << endl;
return 0;
}
输出
最小元素:10 最大元素:15
结论
我们探索了队列数据结构的概念来查找最小或最大元素。我们看到了 front() 和 back() 如何有助于找到元素的最小值和最大值，还看到了如何将 pushback 添加到索引元素的末尾。通过使用双端队列，我们可以在 O(1) 时间复杂度内处理该问题。
