链式队列类定义

template <class T>
class Link  // 定义每个节点类
{
public:
    T data;
    Link *next;
    Link(Link *nextLink=NULL)
    {
        next = nextLink;
    }
    Link(T item, Link *nextLink=NULL)     // 初始化节点内容
    {
        data = item;
        next = nextLink;
    }
};

template <class T>
class Queue
{
public:                                    // 队列的运算集
    void clear();                          // 变为空队列
    bool enQueue(const T& item);           // item入队，插入队尾，成功则返回真否则返回假
    bool deQueue(T& item);                 // 返回队头元素并从队列中删除，成功则返回真
    bool getFront(T& item);                // 返回队头元素，但不删除，成功则返回真
    bool isEmpty();                        // 返回真，若队列已空
    bool isFull();                         // 返回真，若队列已满
};

template <class T>
class lnkQueue: public Queue <T>
{
private:
    int      size;                          // 队列中当前元素的个数
    Link<T>* front;                         // 表示队头的指针
    Link<T>* rear;                          // 表示队尾的指针
public:                                     // 队列的运算集
    lnkQueue()                              // 创建队列的实例
    {
        size = 0;
        front = rear = NULL;
    }
    ~lnkQueue()                             // 消除该实例，并释放其空间
    {
        clear();
    }
    void clear()                            // 清空队列
    {
        while (front != NULL)
        {
            rear = front;
            front = front->next;
            delete rear;
        }
        rear = NULL;
        size = 0;
    }
    bool enQueue(const T item)              // item入队，插入队尾
    {
        if (rear == NULL)                   // 空队列
        {
            front = rear = new Link<T> (item, NULL);
        }
        else                                // 添加新的元素
        {
            rear-> next = new Link<T> (item, NULL);
            rear = rear ->next;
        }
        size++;
        return true;
    }
    bool deQueue(T &item)                   // 返回队头元素并从队列中删除
    {
        Link<T> *tmp;
        if (size == 0)                      // 队列为空，没有元素可出队
        {
            cout << "The Queue is empty!" << endl;
            return false;
        }
        item = front->data;
        tmp = front;
        front = front -> next;
        delete tmp;
        if (front == NULL)
            rear = NULL;
        size--;
        return true;
    }
    bool getFront(T &item)                   // 返回队头元素，但不删除
    {
        if (size == 0)                       // 队列为空，没有元素可出队
        {
            cout << "The queue is empty!" << endl;
            return false;
        }
        item = front->data;
        return true;
    }
};