概念
不知道你玩過英雄聯(lián)盟嗎？英雄聯(lián)盟里面的防御塔會攻擊離自己最近的小兵，但是如果有炮車兵在塔內(nèi)，防御塔會優(yōu)先攻擊炮車（因為炮車的威脅性更大），只有沒有兵線在塔內(nèi)時，防御塔才會攻擊英雄。所以你可以得出優(yōu)先級：距離最近的炮車 >?炮車 > 距離最近的小兵 > 小兵 > 距離最近的英雄 > 英雄。
那什么是優(yōu)先隊列？首先它是一個隊列，它的入隊順序沒有發(fā)生改變，但是出隊的順序是根據(jù)優(yōu)先級的高低來實現(xiàn)的，遍歷隊列，優(yōu)先級高的先出隊，有多個節(jié)點具有最高的優(yōu)先級，選取遇到的第一個具有最高的優(yōu)先級的節(jié)點。?
空隊列
插入一個元素
插入第二個元素
?刪除一個節(jié)點
上列情況是最普通的情況（無需多余的操作），顯然如果刪除的是隊列中的最后一個節(jié)點，尾指針需要手動移動；如果刪除的是隊列中的第一個節(jié)點，頭指針會自動移動。如果刪除的隊列只有一個節(jié)點，那頭尾指針需要手動置空。所以總共有 2?種情況需要考慮。
隊列的算法實現(xiàn)
隊列的結(jié)構(gòu)體定義
其中優(yōu)先級的高低是自己定義的，你也可以令 0 為最高優(yōu)先級，優(yōu)先級數(shù)也不只有這 9 個。
#define MAX_SIZE 15
typedef int DateElem;
typedef struct _QNode
{
int priority; //節(jié)點的優(yōu)先級，9為最高優(yōu)先級，0為最低優(yōu)先級，優(yōu)先級相同的取第一個
DateElem date;
struct _QNode* next;
}QNode;
typedef QNode* QueuePtr; //QueuePtr a; 就定義了一個指向結(jié)構(gòu)體QNode的指針
typedef struct _Queue
{
int length; //隊列長度
QueuePtr head; //頭指針
QueuePtr tail; //尾指針
}Queue;隊列的初始化、判空、判滿、插入
//隊列的初始化，初始化為空隊列
void initQueue(Queue* q)
{
if (!q) //指向隊頭的指針為空
{
return;
}
q->head = NULL;
q->tail = NULL;
q->length = 0;
}
//判斷隊列是否為空
bool IsEmpty(Queue* q)
{
if (!q) return false;
if (q->head == NULL) //條件用 q->tail == NULL 也行
{
return true;
}
return false; //不為空
}
//判斷隊列是否為滿
bool IsFull(Queue* q)
{
if (!q) return false;
if (q->length >= MAX_SIZE) //也可以用 q->length == MAX_SIZE
{
return true;
}
return false;
}
//入隊
bool enterQueue(Queue* q, DateElem e, int priority)
{
if (!q || IsFull(q))
{
cout << "隊列已滿" << endl;
return false;
}
QNode* p = new QNode;
//if (!q) return false; 一般不會生成失敗
p->priority = priority;
p->date = e;
p->next = NULL;
//插入有兩種情況
if (IsEmpty(q)) //空隊列
{
q->head = p;
q->tail = p;
}
else //隊列中已有元素
{
q->tail->next = p; //隊列中的最后一個節(jié)點的next指針指向新加節(jié)點
q->tail = p; //更新尾指針
}
q->length++;
return true;
}出隊
唯一與普通隊列有較大差別的就是隊列的出隊，其他的操作變化很小。
//遍歷隊列
bool popQueue(Queue* q,DateElem *out)
{
if (!q || IsEmpty(q))
{
cout << "隊列為空" << endl;
return false;
}
if (!out)
{
cout << "無法傳遞刪除節(jié)點的值" << endl;
return false;
}
QNode** prev_node_next = NULL; //二級指針，指向優(yōu)先級最高的節(jié)點的前一個節(jié)點的next指針
QNode* prev_node = NULL; //指向優(yōu)先級最高的節(jié)點的前一個節(jié)點
QNode* temp = NULL,*last = NULL; //temp遍歷隊列，last指向temp指向的前一個節(jié)點
prev_node_next = &(q->head); //最開始指向隊頭指針（也就是第一個節(jié)點的前一個節(jié)點的next指針），解引用就是指向第一個節(jié)點
last = q->head;
temp = last->next;
while (temp != NULL)
{
if (temp->priority > (*prev_node_next)->priority)
{
cout << "找到了一個更高的優(yōu)先級：" << temp->priority << endl;
prev_node_next = &(last->next); //指向temp的前一個節(jié)點的next指針
prev_node = last; //指向temp的前一個節(jié)點
}
last = temp;
temp = temp->next;
}
*out = (*prev_node_next)->date; //傳遞出隊元素的值
temp = *prev_node_next; // temp指向要刪除節(jié)點
*prev_node_next = (*prev_node_next)->next; //或者是 prev_node_next = & (*prev_node_next)->next;
delete temp;
q->length--;
//情況一：刪除節(jié)點后為空隊列
if (q->length == 0)
{
q->head = q->tail = NULL;
}
//情況二：刪除的是尾節(jié)點
else if ( *prev_node_next == NULL && prev_node != NULL)
{
q->tail = prev_node;
}
//情況三：刪除的是首節(jié)點，與情況一不同的是刪除節(jié)點后，隊列不為空
//情況四：普通情況
//這兩種情況遍歷結(jié)束后的調(diào)整中頭尾指針就弄好了
return true;
}如果你覺得我這里寫得不好，嘻嘻，因為明明只需要用一級指針，我偏要用二級指針，這就是我與明明的區(qū)別，哈哈，好了不開玩笑，可以看看下圖幫助理解。
隊列的打印、清空、獲取隊首元素
//打印隊列
bool Print(Queue* q)
{
if (!q) return false;
if (IsEmpty(q))
{
cout << "隊列為空" << endl;
}
QNode* p = q->head;
cout << "隊列中的元素：";
while (p != NULL)
{
printf("%d[優(yōu)先級%d] ", p->date,p->priority);
p = p->next;
}
cout << endl;
return true;
}
//清空隊列
bool ClearQueue(Queue* q)
{
if (!q || IsEmpty(q)) return false;
QNode* temp = q->head, * tmp = NULL;
while (temp != NULL)
{
tmp = temp->next;
delete temp;
temp = tmp;
}
q->length = 0;
q->head = NULL;
q->tail = NULL;
return true;
}
//獲取隊頭
bool GetHead(Queue* sq, DateElem* date)
{
if (!date || !sq || IsEmpty(sq))return false;
*date = sq->head->date;
return true;
}主函數(shù)測試代碼
int main(void)
{
Queue* q = new Queue;
DateElem e = -1;
initQueue(q);
for (int i = 0; i < 10; i++)
{
enterQueue(q, i + 2, i);
}
printf("隊列中有%d個元素\n", q->length);
Print(q);
for (int i = 0; i < 5; i++)
{
if (popQueue(q, &e))
{
cout << "出隊的元素是：" << e << endl;
}
else
{
cout << "出隊失敗" << endl;
}
}
cout << "出隊后，";
Print(q);
cout << "清空隊列后，";
ClearQueue(q);
Print(q);
//清理資源
delete q;
return 0;
}?運行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-737684.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-737684.html
到了這里，關于優(yōu)先隊列----數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
