队列链式存储函数的实现

/******************************************************************************
* 文件：LinkedQueue.h
* 功能：队列链式存储
* 说明：队列链式存储结构的类定义
        及类成员函数包括插入、删除等函数的实现
* 时间：2011-4-3
Author: Lzy
*******************************************************************************/
#include <iostream.h>
#include "LinearList.h"

template<class T>
class LinkedQueue;        //声明


/********************************************************************
* 类名: 类模板Node
* 功能: 节点定义
* 说明：
/********************************************************************/
template<class T>
class Node
{
    friend class LinkedQueue<T>;
private:
    T data;
    Node<T> *link;
};


/********************************************************************
* 类名: LinkedQueue
* 功能: 队列链表类定义
* 说明：队列链表相关操作函数的实现
/********************************************************************/
template<class T>
class LinkedQueue
{
private:
    Node<T> *front;                //指向队头节点

    Node<T> *rear;                //指向队尾节点


public:
    LinkedQueue() {front = rear = 0;}
    ~LinkedQueue();
    bool IsEmpty() const {return front ? false:true;}
    T & First() const;                            //返回队首元素

    T & Last() const;                            //返回队尾元素

    bool Insert(const T &x);
    bool Delete(T &x);
    void visit();
};

/********************************************************************
* 所属类名: LinkedQueue
* 成员名称：～LinkedQueue
* 函数功能：析构函数
* 说    明：删除所有节点
/********************************************************************/
template<class T>
LinkedQueue<T>::~LinkedQueue()
{
    Node<T> *next;
    while(front)
    {
        next = front->link;
        delete front;
        front = next;
    }
}

/********************************************************************
* 所属类名: LinkedQueue
* 成员名称：First()
* 函数功能：返回第一个队列元素
* 说    明：
/********************************************************************/
template<class T>
T & LinkedQueue<T>::First() const
{
    if(IsEmpty())
        throw OutOfBounds();
    return front->data;
}

/********************************************************************
* 所属类名: LinkedQueue
* 成员名称：Last()
* 函数功能：返回最后一个元素
* 说    明：
/********************************************************************/
template<class T>
T & LinkedQueue<T>::Last() const
{
    if(IsEmpty())
        throw OutOfBounds();
    return rear->data;
}

/********************************************************************
* 所属类名: LinkedQueue
* 成员名称：Insert
* 函数功能：插入元素
* 说    明：把X插入队尾
/********************************************************************/
template<class T>
bool LinkedQueue<T>::Insert(const T &x)
{
    Node<T> *p = new Node<T>;
    p->data = x;
    p->link = 0;
    if(front)
        rear->link = p;                //队尾添加新节点

    else
        front = p;                    //插入第一个元素

    rear = p;                        //队尾节点后移

    return true;
}

/********************************************************************
* 所属类名: LinkedQueue
* 成员名称：Delete
* 函数功能：删除元素
* 说    明：删除队首元素，数据保存至x中
/********************************************************************/
template<class T>
bool LinkedQueue<T>::Delete(T &x)
{
    if(IsEmpty())
        throw OutOfBounds();        //检查队列是否为空

    x = front->data;                //数据弹出

    Node<T> *p = front;
    front = front->link;            //队首指针后移

    delete p;                        //删除第一个节点

    return true;
}

/********************************************************************
* 所属类名: SeQueue
* 成员名称：<<
* 函数功能：<<重载
* 说    明：
/********************************************************************/
template<class T>
ostream& operator<<(ostream& out, const SeQueue<T>& x)
{
    x.Output(out);
    return out;
}

/********************************************************************
* 所属类名: SeQueue
* 成员名称：visit
* 函数功能：队列遍历
* 说    明：
/********************************************************************/
template<class T>
void LinkedQueue<T>::visit()
{
    Node<T> *p = front;
    while(p)                //遍历队列

    {
        cout<<p->data<<" ";
        p = p->link;
    }
    cout<<endl;
}

//测试程序
void main()
{
    LinkedQueue<int>L;
    for(int i = 1; i < 16; i++)
        L.Insert(i);                    //插入15个元素
    L.visit();                            //全部显示
    int z;
    for(i = 1; i < 6; i++)
    {
        L.Delete(z);                    //删除5个元素
        cout<<z<<" ";
    }
    cout<<endl;
    L.visit();

}