定义
相比较于普通队列来说，优先队列的每个元素都被赋予了优先级。当需要出队列操作时，具有最高优先级的元素会先出队列。因此是符合优先级优先的特征，被称为优先队列。
优先队列实现
#priority_queue.h
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
using std::cout;
using std::endl;
class Node
{
public:
int info;
int level;
Node *prev;
Node *next;
public:
Node() { info = 0; level = 256; prev = next = nullptr; }
Node(int value, int lev) { info = value; level = lev; prev = next = nullptr; };
friend std::ostream & operator<<(std::ostream &, Node *);
~Node(){}
};
class Priority_queue
{
private:
Node *head;
Node *tail;
public:
Priority_queue() { head = tail = nullptr; }
Priority_queue(Node *p) { head = tail = p; head->prev = tail->next = nullptr; head->next = tail->prev = p; }
bool isempty();
bool inqueue(Node *);
Node *ennode(Node *);
Node *denode();
friend std::ostream & operator<<(std::ostream &, Priority_queue &);
~Priority_queue() {}
};
#endif // !PRIORITY_QUEUE_H
#priority_queue.cpp
#include <iostream>
#include "priority_queue.h"
std::ostream & operator<<(std::ostream &out, Node *p)
{
return out << p->info << " and level " << p->level << endl;
}
bool Priority_queue::isempty()
{
return head == nullptr;
}
bool Priority_queue::inqueue(Node *p)
{
Node *tmp;
if (!isempty())
{
for (tmp = head; tmp != tail; tmp = tmp->next);
return tmp->info == p->info;
}
else
return 0;
}
Node * Priority_queue::ennode(Node *p)
{
if (!isempty())
{
tail->next = p;
tail->next->prev = tail;
tail = tail->next;
tail->next = nullptr;
return tail;
}
else
{
head = tail = p;
head->prev = tail->next = nullptr;
head->next = tail->prev = p;
return tail;
}
}
Node * Priority_queue::denode()
{
Node *min, *tmp;
if (!isempty())
{
for (min = head, tmp = head->next; tmp != tail; tmp = tmp->next)
{
if (min->level < tmp->level)
continue;
else
min = tmp;
}
min->prev->next = min->next;
min->next->prev = min->prev;
return min;
}
else
return 0;
}
std::ostream & operator<<(std::ostream &out, Priority_queue &p)
{
Node *tmp;
if (!p.isempty())
{
for (tmp = p.head; tmp != p.tail; tmp = tmp->next)
out << tmp->info << " and level " << tmp->level << endl;
return out << p.tail->info << " and level " << p.tail->level << endl;
}
return out;
}
#main.cpp
#include <iostream>
#include "priority_queue.h"
#include <crtdbg.h>
using std::cout;
using std::endl;
int main()
{
Node node1, node2(1, 2), node3(2, 3), node4(3, 4), node5(4, 5);
Priority_queue queue1, queue2(&node1);
cout << queue1.isempty() << endl;
cout << queue1.ennode(&node1) << endl;
cout << queue1.ennode(&node4) << endl;
cout << queue1.ennode(&node2) << endl;
cout << queue1.ennode(&node3) << endl;
cout << queue1.denode() << endl;
cout << queue1.inqueue(&node3) << endl;
cout << queue1.inqueue(&node5) << endl;
cout << queue1 << endl;
cout << queue2.isempty() << endl;
cout << queue2.ennode(&node1) << endl;
cout << queue2.ennode(&node4) << endl;
cout << queue2.ennode(&node2) << endl;
cout << queue2.ennode(&node3) << endl;
cout << queue2.denode() << endl;
cout << queue2.inqueue(&node3) << endl;
cout << queue2.inqueue(&node5) << endl;
cout << queue2 << endl;
_CrtDumpMemoryLeaks();
system("pause");
return 0;
}
参考资料
1. C++数据结构与算法：https://item.jd.com/29739898993.html
