设计一个底层容器为向量类模板Vector<T>的适配器,要求实现最大值为优先级的优先级队列,测试main函数中随机生成10个20以内的int型数据压入队列中,然后依次出队并显示。(20分)
时间: 2024-03-27 14:39:25 浏览: 22
以下是一个基于向量类模板Vector<T>的适配器实现最大值为优先级的优先级队列的代码:
```c++
#include <cstdlib>
#include <ctime>
#include <iostream>
#include "Vector.h"
template <typename T>
class PriorityQueue {
public:
void push(const T& value) {
data.push_back(value);
int i = data.size() - 1;
while (i > 0 && data[i] > data[(i - 1) / 2]) {
std::swap(data[i], data[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void pop() {
if (data.empty()) {
return;
}
data[0] = data.back();
data.pop_back();
int i = 0;
while (2 * i + 1 < data.size()) {
int j = 2 * i + 1;
if (j + 1 < data.size() && data[j + 1] > data[j]) {
++j;
}
if (data[i] < data[j]) {
std::swap(data[i], data[j]);
i = j;
} else {
break;
}
}
}
const T& top() const {
return data[0];
}
bool empty() const {
return data.empty();
}
private:
Vector<T> data;
};
int main() {
srand(static_cast<unsigned int>(time(nullptr)));
PriorityQueue<int> pq;
for (int i = 0; i < 10; ++i) {
pq.push(rand() % 20);
}
while (!pq.empty()) {
std::cout << pq.top() << ' ';
pq.pop();
}
std::cout << std::endl;
return 0;
}
```
在主函数中,我们使用srand函数设置随机数生成器的种子,然后利用rand函数生成随机数,并将其插入到优先队列中。最后,循环输出队列中的元素,直到队列为空。
需要注意的是,这里的Vector<T>是一个自定义的向量类模板,用于实现动态数组。在优先队列中,我们使用向量作为底层容器,并在push、pop、top等函数中实现了优先级队列的基本操作,使其支持最大值为优先级的优先级队列的特性。