queue2.h

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>
#include "OnelinkNode2.h"              //单链表结点类，模板

template <class T>
class Queue2                           //链式队列类
{
  public:
    OnelinkNode2<T> *front,*rear;      //front、rear分别是指向队首、队尾结点的指针

    Queue2();                          //构造函数
    ~Queue2();                         //析构函数
    bool isEmpty()const;               //判断队列是否为空
    bool enQueue(T& k);                //数据元素k入队
    T deQueue();                       //出队
    friend ostream& operator<<(ostream& out,Queue2<T> &q);
                                       //输出队列中各数据元素值，输出流运算符重载
};

template <class T>
Queue2<T>::Queue2()                    //构造函数,构造空队列
{
    front=rear=NULL;                   //指针为空
}

template <class T>
Queue2<T>::~Queue2()                   //析构函数
{
    OnelinkNode2<T> *p=front,*q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;
        delete q;
    }
    front=rear=NULL;
}

template <class T>
bool Queue2<T>::isEmpty()const         //判断队列是否为空
{
    return front==NULL && rear==NULL;
}

template <class T>
bool Queue2<T>::enQueue(T& k)          //数据元素k入队列
{
    OnelinkNode2<T> *p=new OnelinkNode2<T>(k);
    if(!isEmpty())                     //队列不空
        rear->next=p;                  //p结点作为新的队尾结点
    else 
        front=p;      
    rear=p;
    return true;
}  

template <class T>
T Queue2<T>::deQueue()                 //出队
{
    T k;
    if(!isEmpty())                     //队列不空
    {
        k=front->data;                 //取得队首结点元素值
        OnelinkNode2<T> *p=front;
        front=front->next;             //后继结点作为新的队首结点
        delete p;                      //删除原队首结点
        if(front==NULL)                //空队列时，两指针同步
           rear=NULL;
    }
    return k;
}

template <class T>
ostream& operator<<(ostream& out,Queue2<T> &q)
{                                      //输出队列中各数据元素值，输出流运算符重载
    cout<<"链式队列:   ";
    OnelinkNode2<T> *p=q.front;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return out;
}