队列(queue)是一个简单而常见的数据结构。队列也是有序的元素集合。队列最大的特征是First In, First Out (FIFO，先进先出)，即先进入队列的元素，先被取出。这一点与栈(stack)形成有趣的对比。队列在生活中很常见，排队买票、排队等车…… 先到的人先得到服务并离开队列，后来的人加入到队列的最后。队列是比较公平的分配有限资源的方式，可以让队列的人以相似的等待时间获得服务。

//CirQueue.h/*循环队列的顺序存储实现*/#include<iostream>using namespace std;template<typename T>class CirQueue{private:    T *base;    int front;    int rear;    int maxSize;public:    CirQueue(int m);    ~CirQueue();    void EnQueue(T e);//元素e从队尾入队    T DeQueue();//队顶元素出队    void QueueDisplay();    T GetHead();//取队头元素    T GetLast();//取队尾元素    void Pointer();//返回队头队尾位置    int QueueEmpty();    void ClearQueue();    friend void TestCirQueue();};template<typename T>CirQueue<T>::CirQueue(int m){    base=new T[m];    if(base==NULL)    {        cout<<"创建失败，退出！"<<endl;    }    cout<<"创建了容量为"<<m<<"的"<<typeid(T).name()<<"型空队列！"<<endl;    front=0;//队头，队尾都是从0开始    rear=0;    maxSize=m;}template<typename T>CirQueue<T>::~CirQueue(){    delete []base;    front=0;    rear=0;    maxSize=0;    cout<<"析构队列，释放空间"<<endl;    getchar();}template<typename T>void CirQueue<T>::EnQueue(T e){    if((rear+1)%maxSize==front)        cout<<"队满，元素"<<e<<"不能入队"<<endl;    else    {        base[rear]=e;        rear=(rear+1)%maxSize;    }}template<typename T>void CirQueue<T>::QueueDisplay(){    int q=front;    while(q!=rear)    {        cout<<"位置"<<q+1<<"的数据元素是："<<base[q]<<endl;        q=(q+1)%maxSize;    }}template<typename T>T CirQueue<T>::DeQueue(){    T temp;    if(front==rear)        cout<<"对空，没有元素出队！"<<endl;    else    {        temp=base[front];        front=(front+1)%maxSize;        return temp;    }}template<typename T>T CirQueue<T>::GetHead(){    if(front==rear)        cout<<"对空，没有数据元素"<<endl;    else         return base[front];}template<typename T>T CirQueue<T>::GetLast(){    if(front==rear)        cout<<"对空，没有数据元素"<<endl;    else     {        if(rear==0)            return base[maxSize-1];        else            return base[rear-1];    }}template<typename T>void CirQueue<T>::Pointer(){    cout<<"队头位置front是："<<front<<endl;    cout<<"队尾位置rear是："<<rear<<endl;}template<typename T>int CirQueue<T>::QueueEmpty(){    if(front==rear)        return 1;    else         return 0;}template<typename T>void  CirQueue<T>::ClearQueue(){    front=rear=0;}void TestCirQueue()//测试，顺序循环队列各种操作{    int first;    int last;    CirQueue<int>  cq(5);    for(int i=0;i<4;i++)    {        cq.EnQueue(i);    }    cq.QueueDisplay();    cout<<"队顶元素出队后....."<<endl;    cq.DeQueue();    cq.EnQueue(7);    cq.QueueDisplay();    first=cq.GetHead();    cout<<"队首元素是:"<<first<<endl;    last=cq.GetLast();    cout<<"队尾元素是:"<<last<<endl;    cq.Pointer();    getchar();}

//LinkQueue.h/*链dui的实现*/#include<iostream>using namespace std;template<typename T>struct Node{    T data;    Node<T> *next;};template<typename T>class LinkQueue{private:    Node<T> *front;    Node<T> *rear;public:    LinkQueue();//构造函数    ~LinkQueue();//析构函数    void EnQueue(T e);//从队尾入队    T DeQueue();//从队头出队    void QueueDisplay();//队列元素显示    T GetHead();//获得队列首元素    T GetLast();//获得队尾元素    int QueueEmpty();//判断队列是否为空    void ClearQueue();//清空队列    friend void TestLinkQueue();//测试队列的各种操作};template<typename T>LinkQueue<T>::LinkQueue(){    front=new Node<T>;    front->next=NULL;    rear=front;    //cout<<"链队已创建！"<<endl;}template<typename T>LinkQueue<T>::~LinkQueue(){    Node<T> *p;    while(front!=NULL)    {    p=front;        front=front->next;        delete p;    }    rear=NULL;    //cout<<"析构链队，释放空间！"<<endl;    getchar();}template<typename T>void LinkQueue<T>::EnQueue(T e){    Node<T> *s;    s=new Node<T>;    s->data=http://www.mamicode.com/e;    rear->next=s;    s->next=NULL;    rear=s;}template<typename T>void LinkQueue<T>::QueueDisplay(){    Node<T> *p;    p=front->next;    while(p!=NULL)    {        cout<<p->data<<"\t";        p=p->next;    }    cout<<endl;}template<typename T>T LinkQueue<T>::DeQueue(){    T temp;    Node<T> *p;    p=front->next;    temp=p->data;    front->next=p->next;    delete p;    return  temp;}template<typename T>T LinkQueue<T>::GetHead(){        if(front->next==NULL)    {        cout<<"空链队，没有元素,默认为-9999！"<<endl;        return -9999;    }    else        return front->next->data;}template<typename T>T LinkQueue<T>::GetLast(){    if(front->next==NULL)    {        cout<<"空链队，没有元素,默认为-9999！"<<endl;        return -9999;    }    else         return rear->data;}template<typename T>int LinkQueue<T>::QueueEmpty(){    if(front->next==NULL&&front==rear)        return 1;    else        return 0;}template<typename T>void LinkQueue<T>::ClearQueue()//恢复到调用构造函数后的阶段{    Node<T> *p;    while(front->next!=NULL)    {        p=front->next;        front->next=p->next;        delete p;    }    rear=front;}void TestLinkQueue(){    int element;    LinkQueue<int> lq;    for(int i=0;i<5;i++)    {        lq.EnQueue(i);    }    cout<<"队列所以元素为：";    lq.QueueDisplay();    element=lq.DeQueue();    cout<<"出队元素为："<<element<<endl;    element=lq.GetHead();    cout<<"链队首元素为："<<element<<endl;    element=lq.GetLast();    cout<<"链队尾元素为："<<element<<endl;        cout<<"调用清空函数后的链队..."<<endl;    lq.ClearQueue();    cout<<"队列所有元素为：";    lq.QueueDisplay();    element=lq.GetHead();    cout<<"链队首元素为："<<element<<endl;    element=lq.GetLast();    cout<<"链队尾元素为："<<element<<endl;    getchar();}

#include<iostream>using namespace std;#include"CirQueue.h"//顺序存储的循环队列实现#include"LinkQueue.h"//链对的实现void YangHui(int n);//使用链对的一个例子：输出杨辉三角形列表void TestYangHui();int main(void){    cout<<"--------------测试，顺序循环队列各种操作--------------"<<endl;    TestCirQueue();    cout<<"--------------测试，链队各种操作--------------"<<endl;    TestLinkQueue();    cout<<"--------------测试，使用链队输出杨辉三角形列表（二项式系数）--------------"<<endl;    TestYangHui();        }void YangHui(int n){    LinkQueue<int> lq;    lq.EnQueue(1);    lq.EnQueue(1);    int s=0;    for(int i=1;i<=n;i++)    {        lq.EnQueue(0);        //cout<<"i="<<i<<endl;        for(int j=1;j<=i+2;j++)        {            int t;            t=lq.DeQueue();            lq.EnQueue(s+t);            s=t;            //cout<<"j="<<j<<"\t"<<"t="<<t<<"\t"<<"s="<<s<<endl;            if(j<i+2)                cout<<s<<" ";        }        cout<<endl;    }    cout<<endl;}void TestYangHui(){    cout<<"--------------使用链队，完成杨辉三角形的输出（二项式系数表）--------------"<<endl;    int p;    cout<<"输入想要输出的二项式阶数：";    cin>>p;    cout<<"阶数为"<<p<<"的二项式系数表为:"<<endl;    YangHui(p);    getchar();}