#include <iostream>

#include <Windows.h>

#include <iomanip>

//优先级队列的实现

using namespace std;

#define MaxSize 5

typedef int DataType; //队列中的元素类型

typedef struct _QNode { //结点结构

    int priority; //每个节点的优先级,0 最低优先级，9 最高优先级，优先级相同，取第一个节点

    DataType data;

    struct _QNode* next;

}QNode;

typedef QNode* QueuePtr;

typedef struct Queue

{

    int length; //队列的长度

    QueuePtr front; //队头指针

    QueuePtr rear; //队尾指针

}LinkQueue;

//队列初始化，将队列初始化为空队列

void InitQueue(LinkQueue* LQ)

{

    if (!LQ) return;

    LQ->length = 0;

    LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0

}

//判断队列为空

int IsEmpty(LinkQueue* LQ)

{

    if (!LQ) return 0;

    if (LQ->front == NULL)

    {

        return 1;

    }

    return 0;

}

//判断队列是否为满

int IsFull(LinkQueue* LQ)

{

    if (!LQ) return 0;

    if (LQ->length == MaxSize)

    {

        return 1;

    }

    return 0;

}

//入队,将元素 data 插入到队列 LQ 中

int EnterQueue(LinkQueue* LQ, DataType data, int priority) {

    if (!LQ) return 0;

    if (IsFull(LQ)) {

        cout << "无法插入元素 " << data << ", 队列已满!" << endl;

        return 0;

    }

    QNode* qNode = new QNode;

    qNode->data = data;

    qNode->priority = priority;

    qNode->next = NULL;

    if (IsEmpty(LQ)) {//空队列

        LQ->front = LQ->rear = qNode;

    }

    else {

        LQ->rear->next = qNode;//在队尾插入节点 qNode

        LQ->rear = qNode; //队尾指向新插入的节点

    }

    LQ->length++;

    return 1;

}

//出队，遍历队列，找到队列中优先级最高的元素 data 出队

int DeleteQueue(LinkQueue* LQ, DataType* data) {

    QNode** prev = NULL, * prev_node = NULL;//保存当前已选举的最高优先级节上一个节点的指针地址。

    QNode* last = NULL, * tmp = NULL; //last是已选举的最高优先级的前一个结点，tmp是已选举的最高优先级，即将要删除的结点

    if (!LQ || IsEmpty(LQ)) {

        cout << "队列为空！" << endl;

        return 0;

    }

    if (!data) return 0;

    //prev 指向队头 front 指针的地址

    prev = &(LQ->front);

    printf("第一个节点的优先级: %d\n", (*prev)->priority);

    last = LQ->front;

    tmp = last->next;

    while (tmp) {

        if (tmp->priority > (*prev)->priority) {

            printf("抓到个更大优先级的节点[priority: %d]\n",

                tmp->priority);

            prev = &(last->next);

            prev_node = last;

        }

        last = tmp;

        tmp = tmp->next;

    }

    *data = (*prev)->data;

    tmp = *prev;

    *prev = (*prev)->next;

    delete tmp;

    LQ->length--;

    //接下来存在 2 种情况需要分别对待

    //1.删除的是首节点,而且队列长度为零

    if (LQ->length == 0) {

        LQ->rear = NULL;

    }

    //2.删除的是尾部节点

    if (prev_node && prev_node->next == NULL) {

        LQ->rear = prev_node;

    }

    return 1;

}

//打印队列中的各元素

void PrintQueue(LinkQueue* LQ)

{

    QueuePtr tmp;

    if (!LQ) return;

    if (LQ->front == NULL) {

        cout << "队列为空！";

        return;

    }

    tmp = LQ->front;

    while (tmp)

    {

        cout << setw(4) << tmp->data << "[" << tmp->priority << "]";

        tmp = tmp->next;

    }

    cout << endl;

}

//获取队首元素，不出队

int GetHead(LinkQueue* LQ, DataType* data)

{

    if (!LQ || IsEmpty(LQ))

    {

        cout << "队列为空!" << endl;

        return 0;

    }

    if (!data) return 0;

    *data = LQ->front->data;

    return 1;

}

//清空队列

void ClearQueue(LinkQueue* LQ)

{

    if (!LQ) return;

    while (LQ->front) {

        QueuePtr tmp = LQ->front->next;

        delete LQ->front;

        LQ->front = tmp;

    }

    LQ->front = LQ->rear = NULL;

    LQ->length = 0;

}

//获取队列中元素的个数

int getLength(LinkQueue* LQ) {

    if (!LQ) return 0;

    return LQ->length;

}

int main()

{

    LinkQueue* LQ = new LinkQueue;

    DataType data = -1;

    //初始化队列

    InitQueue(LQ);

    //入队

    for (int i = 0; i < 5; i++) {

        EnterQueue(LQ, i + 10, i);

    }

    //打印队列中的元素

    printf("队列中的元素(总共%d 个)：", getLength(LQ));

    PrintQueue(LQ);

    cout << endl;

    //出队

    for (int i = 0; i < 5; i++) {

        if (DeleteQueue(LQ, &data)) {

            cout << "出队的元素是：" << data << endl;

        }

        else {

            cout << "出队失败！" << endl;

        }

    }

    //打印队列中的元素

    printf("出队五个元素后，队列中剩下的元素[%d]：\n", getLength(LQ));

    PrintQueue(LQ);

    cout << endl;

    ClearQueue(LQ);

    cout << "清空队列!\n";

    PrintQueue(LQ);

    //清理资源

    delete LQ;

    system("pause");

    return 0;

}