/***********优先队列的(单向)链式实现形式*************/ 节点类 template class QueueNode { public: Type data;//数据 int priority;//优先级 QueueNode *next; QueueNode() :data(Type()), priority(0), next(nullptr){} QueueNode(Type d, int p, QueueNode *n=nullptr) :data(d), priority(p), next(n){} }; //优先队列类 template class Priority_Queue { private: QueueNode *front;//队头指针 QueueNode *rear;//队尾指针 int length;//队列长度 public: Priority_Queue(); ~Priority_Queue(); bool isEmpty(){ return this->length == 0; } int size() const { return this->length; } bool Push(const Type &d, int p); bool Pop(); Type GetHead(); void ShowQueue() const; }; //构造函数 template Priority_Queue::Priority_Queue() :length(0) { cout << “构造函数，创建一个节点” << endl; this->front = this->rear = new QueueNode(); } //析构函数 template Priority_Queue::~Priority_Queue() { cout << “析构函数” << endl; QueueNode *dnode = this->front; QueueNode *tmp = this->front; while (tmp != nullptr) { tmp = tmp->next; delete dnode; dnode = tmp; }
} //添加节点 template bool Priority_Queue::Push(const Type &d, int p) { QueueNode *add = new QueueNode(d, p, nullptr);//将要插入的节点 if (add == nullptr) return false; //要根据优先级构造队列，数字越小优先级越高应该， 数字最小的应该放在最前面 if (this->front == this->rear) { cout << “该队列为空，直接将节点插入即可” << endl; this->rear->next = add; this->rear = add; this->length++; return true; } QueueNode *move = this->front->next;//移动指针找到第一个比塔优先级小的节点 while (move->priority < add->priority && move != nullptr) move = move->next; if (move == nullptr)//说明队列中的优先级都比add大，直接将节点插在队尾即可 { this->rear->next = add; this->rear = add; this->length++; return true; } QueueNode *tmp = this->front; while (tmp->next != move) tmp = tmp->next; add->next = move; tmp->next = add; this->length++; return true; } template bool Priority_Queue::Pop() { if (this->length == 0) { cout << “队列为空，无法输出” << endl; return false; } QueueNode *dnode = this->front->next; this->front->next = dnode->next; if (this->length == 1) this->rear = this->front; delete dnode; this->length–; return true; } template Type Priority_Queue::GetHead() { if (this->length == 0) { cout << “队列为空，无法获得第一个元素的值” << endl; return 0; } return this->front->next->data; } template void Priority_Queue::ShowQueue() const { if (this->length == 0) { cout << “队列为空，无法输出” << endl; return; } QueueNode *move = this->front->next; int i = 0; while (move != nullptr) { cout << “第” << i + 1 << “个元素输出: ” << endl << “data:” << move->data << endl << “priority:” << move->priority << endl; move = move->next; i++; } } //测试程序 int main() { Priority_Queue queue; for (int i = 0, j = 10; i < 10, j>0; i++, j–) queue.Push(i + 1, j); queue.Push(100, 4); //queue.ShowQueue(); for (int i = 0; i < 5; i++) queue.Pop(); queue.ShowQueue(); return 0; }
/***********优先队列的(双向)链式实现形式*************/ //队列节点类 template class QueueNode { public: Type data;//数据域 int priority;//优先级 QueueNode *next;//后继指针 QueueNode *prev;//前向指针 QueueNode() :data(Type()), priority(0), next(nullptr), prev(nullptr){} QueueNode(Type d, int pri, QueueNode *n = nullptr, QueueNode *p = nullptr) :data(d), priority(pri), next(n), prev(p){} }; //优先队列类 template class Priority_Queue { private: QueueNode *front;//头指针 QueueNode *rear;//尾指针 int length;//队列长度 public: Priority_Queue(); ~Priority_Queue(); bool isEmpty(){ return this->length == 0; } int size() const { return this->length; } bool Push(const Type &d, int p); bool Pop(); Type GetHead(); void ShowQueue() const; }; //构造函数 template Priority_Queue::Priority_Queue() :length(0) { cout << “构造函数,创建一个头节点” << endl; this->front = this->rear = new QueueNode(); } //析构函数 template Priority_Queue::~Priority_Queue() { cout << “析构函数” << endl; /*QueueNode *dnode = this->front; QueueNode move = this->front;/ } //添加节点 template bool Priority_Queue::Push(const Type &d, int p) { QueueNode *add = new QueueNode(d, p, nullptr, nullptr);//将要插入的节点 if (add == nullptr) return false; if (this->length == 0) { //cout << “链表为空，直接插入即可” << endl; this->front->next = add; add->prev = this->front; this->rear = add; this->length++; return true; } //加入链表不为空，排序添加节点 QueueNode *move = this->front->next; while (move->priority < add->priority && move != nullptr) move = move->next; if (move == nullptr) { //说明队列中所有元素的优先级都比add大，直接插在队后即可 this->rear->next = add; add->prev = this->rear; this->rear = add; this->length++; return true; } move->prev->next = add; add->prev = move->prev; add->next = move; move->prev = add; this->length++; return true; } //删除节点 template bool Priority_Queue::Pop() { if (this->length == 0) { cout << “队列为空，无法删除” << endl; return false; } if (this->length == 1) { delete this->front->next; this->front->next = nullptr; this->rear = nullptr; this->length–; return true; } QueueNode *dnode = this->front->next; this->front->next = dnode->next; dnode->next->prev = this->front; delete dnode; this->length–; return true; } //获取第一个元素的值 template Type Priority_Queue::GetHead() { if (this->length == 0) { cout << “队列为空，无法查看第一个元素的值” << endl; return 0;//返回0是没有元素 } return this->front->next->data; } //输出队列 template void Priority_Queue::ShowQueue() const { if (this->length == 0) { cout << “队列为空，无法删除” << endl; return; } QueueNode *move = this->front->next; int i = 0; while (move != nullptr) { cout << “第” << i + 1 << “个元素输出: ” << endl << “data:” << move->data << endl << “priority:” << move->priority << endl; move = move->next; i++; cout << endl; } } //测试程序 int main() { Priority_Queue queue; for (int i = 0, j = 10; i<10, j>0; i++, j–) queue.Push(i, j); queue.Push(1, 2); //queue.Pop(); queue.ShowQueue(); return 0; }
