数据结构-优先级队列

// queue_node.h
#ifndef QUEUE_NODE_H
#define QUEUE_NODE_H

#include <iostream>

template<typename Type, typename Cmp> class PriorityQueue;

template<typename Type, typename Cmp> class QueueNode
{
private:
    friend class PriorityQueue<Type, Cmp>;
    QueueNode(const Type item, QueueNode<Type, Cmp> *next = NULL)
        : m_data(item), m_pnext(next) {}

private:
    Type m_data;
    QueueNode<Type, Cmp> *m_pnext;
};

#endif // QUEUE_NODE_H

// compare.h
#ifndef COMPARE_H
#define COMPARE_H

#include <iostream>

template<typename Type> class Compare
{
public:
    static bool lt(Type item1, Type item2);
};

template<typename Type> bool Compare<Type>::lt(Type item1, Type item2)
{
    return item1 < item2;
}

struct SpecialData
{
    friend std::ostream& operator<<(std::ostream &os, SpecialData out)
    {
        os << out.m_ntenor << " " << out.m_npir;
        return os;
    }

    int m_ntenor;
    int m_npir;
};

class SpecialCmp
{
public:
    static bool lt(SpecialData item1, SpecialData item2)
    {
        return item1.m_npir < item2.m_npir;
    }
};

#endif // COMPARE_H

// priority_queue.h
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include "compare.h"
#include "queue_node.h"
#include <iostream>

template<typename Type, typename Cmp> class PriorityQueue
{
public:
    PriorityQueue() : m_prear(NULL), m_pfront(NULL){}
    ~PriorityQueue()
    {
        MakeEmpty();
    }

public:
    void MakeEmpty();
    void EnQueue(const Type item);
    Type DeQueue();
    Type GetFront();
    bool IsEmpty() const
    {
        return (m_pfront == NULL);
    }
    void Print();

private:
    QueueNode<Type,Cmp> *m_prear;
    QueueNode<Type,Cmp> *m_pfront;
};

template<typename Type, typename Cmp> void PriorityQueue<Type, Cmp>::MakeEmpty()
{
    QueueNode<Type, Cmp> *pdel;
    while(m_pfront)
    {
        pdel = m_pfront;
        m_pfront = m_pfront->m_pnext;
        delete pdel;
    }
}

template<typename Type, typename Cmp> void PriorityQueue<Type, Cmp>::EnQueue(const Type item)
{
    QueueNode<Type, Cmp> *m_pnew = new QueueNode<Type, Cmp>(item);
    if(m_pfront == NULL)
    {
        m_pfront  = m_prear = m_pnew;
    }
    else
    {
        m_prear = m_prear->m_pnext = m_pnew;
    }
}

template<typename Type, typename Cmp> Type PriorityQueue<Type, Cmp>::DeQueue()
{
    if(m_pfront == NULL)
    {
        std::cout << __FUNCTION__ << " error : queue is empty " << std::endl;
        exit(1);
    }
    QueueNode<Type, Cmp> *pdel = m_pfront, *pCursor = m_pfront;
    while(pCursor->m_pnext)
    {
        if(Cmp::lt(pCursor->m_pnext->m_data, pdel->m_pnext->m_data))
        {
            pdel = pCursor;
        }
        pCursor = pCursor->m_pnext;
    }

    pCursor = pdel;
    pdel = pdel->m_pnext;
    pCursor->m_pnext = pdel->m_pnext;
    Type tmp = pdel->m_data;
    delete pdel;
    return tmp;
}

template<typename Type, typename Cmp> Type PriorityQueue<Type, Cmp>::GetFront()
{
    if(m_pfront == NULL)
    {
        std::cout << __FUNCTION__ << " error : queue is empty " << std::endl;
        exit(1);
    }
    QueueNode<Type, Cmp> *pdel = m_pfront, *pcursor = m_pfront->m_pnext;
    while(pcursor)
    {
        if(Cmp::lt(pcursor->m_data, pdel->m_data))
        {
            pdel = pcursor;
        }
        pcursor = pcursor->m_pnext;
    }

    return pdel->m_data;
}

template<typename Type, typename Cmp> void PriorityQueue<Type, Cmp>::Print()
{
    QueueNode<Type, Cmp> *m_pcursor = m_pfront;
    std::cout << "front" ;
    while(m_pcursor)
    {
        std::cout << "--->" << m_pcursor->m_data;
        m_pcursor = m_pcursor->m_pnext;
    }
    std::cout << "--->rear" << std::endl << std::endl << std::endl;
}

#endif // PRIORITY_QUEUE_H

// main.cpp
#include <iostream>
#include <cstdlib>
#include "priority_queue.h"
#include "compare.h"

using namespace std;

int main(int argc, char *argv[])
{
    PriorityQueue<int, Compare<int> > queue;
    int init[10] = {11, 13, 15, 17, 19, 1, 3, 5, 7, 9};
    for(int i = 0; i < 10; i++)
    {
        queue.EnQueue(init[i]);
    }
    queue.Print();

    cout << queue.GetFront() << endl;

    queue.DeQueue();
    queue.Print();

    PriorityQueue<SpecialData, SpecialCmp> spe_queue;
    int init2[5][2] = {{34, 2}, {64, 1}, {18, 3}, {24, 2}, {55, 4}};
    SpecialData data[5];
    for(int i = 0; i < 5; i++)
    {
        data[i].m_npir = init2[i][1];
        data[i].m_ntenor = init2[i][0];
    }
    for(int i = 0; i < 5; i++)
    {
        spe_queue.EnQueue(data[i]);
    }
    spe_queue.Print();

    cout << spe_queue.GetFront() << endl << endl;

    spe_queue.DeQueue();
    spe_queue.Print();

    return 0;
}