#include<iostream>
#include<cstring>
using namespace std;
 
template<class Type>
class Queue
{
private:
    int front;
    int rear;
    Type *item;
    int length; //有效长度
    int maxsize; //最大长度

public:
    Queue(int i)
    {
        front=rear=0;
        if(i>10)
            maxsize=i;
        else
            maxsize=10;
        length=0;
        item=new Type[maxsize];
        if(item==0)
        {
            cout<<"空间分配不成功"<<endl;
        }
    }
    ~Queue()
    {
        delete []item;
    }
    void Append(Type x);  //追加元素
    void GetHead(Type &x); //取元素
    bool Allocation_mem(); //若空间不足，分配空间
    bool IsFull()  //判断队满
    {
        if((rear+1)%maxsize==front)
            return true;
        else
            return false;
    }
    bool IsEmputy()   //判断队空
    {
        if(rear==front)
            return true;
        else
            return false;
    }
    int Q_maxsize()   //返回队列中允许存储的元素个数最大值
    {
        return maxsize;
    }
    int Q_length()  //返回当前队列的有效元素个数
    {
        return length;
    }
};
template<class Type>
void Queue<Type>::Append(Type x)
{
    if(IsFull())
    {
        Allocation_mem();
    }
    rear=(rear+1)%maxsize;
    item[rear]=x;
    length++;
}
template<class Type>
void Queue<Type>::GetHead(Type &x)
{
    if(IsEmputy())
    {
        cout<<"队列为空"<<endl;
    }
    front=(front+1)%maxsize;
    x=item[front];
    length--;
}
template<class Type>
bool Queue<Type>::Allocation_mem()
{
    Type *p,*temp;
    p=new Type[maxsize+10];
    if(!p)
    {
        cout<<"扩展空间失败"<<endl;
        return false;
    }
    memmove(p,item,sizeof(Type)*maxsize);
    temp=item;
    item=p;
    delete []temp;
    maxsize=maxsize+10;
    return true;
}

//测试程序为：
int main()
{
    cout<<"整型队列1："<<endl;
    Queue<int> queue1(8);
    int input[10],i,output;

    for(i=0;i<10;i++)
    {
        input[i]=i+1;
        queue1.Append(input[i]);
    }
    cout<<"队列中允许存储的元素个数最大为："<<queue1.Q_maxsize()<<endl;
    cout<<"队列中的有效元素个数为："<<queue1.Q_length()<<endl;
    cout<<"队列中的元素为：";
    for(i=0;i<10;i++)
    {
        queue1.GetHead(output);
        cout<<output<<" ";
    }
    cout<<endl;
    
    cout<<"字符型队列2："<<endl;
    Queue<char> queue2(26);
    char in[27]="abcdefghijklmnopqrstuvwxyz",a;
    int j,k;

    for(j=0;j<26;j++)
    {
        queue2.Append(in[j]);
    }
    cout<<"队列中允许存储的元素个数最大为："<<queue2.Q_maxsize()<<endl;
    cout<<"队列中的有效元素个数为："<<queue2.Q_length()<<endl;
    cout<<"队列中的元素为：";
    for(k=0;k<26;k++)
    {
        queue2.GetHead(a);
        cout<<a<<" ";
    }
    cout<<endl;
    return 0;
}