目的：使用C++模板设计链队列的抽象数据类型（ADT）。并在此基础上，使用链队列ADT的基本操作，设计并实现简单应用的算法设计。
内容：（1）请参照单链表的ADT模板，设计链队列的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的单链表ADT原型文件，自行设计链队列的ADT。）
注意：链队列带头结点。
（2）ADT的简单应用：使用该ADT设计并实现应用链队列的算法设计。
应用：假设2个任意长度的整数x、y分别由带头结点的链队列A和B存储，现要求设计一个算法，实现任意长的整数进行加法运算。
参考函数原型：
template<class ElemType>
void Long_Int_Add( LinkQueue<ElemType> &A, LinkQueue<ElemType> &B, string &result, string &A_str, string &B_str ); //result 计算结果字符串
辅助函数原型：
（1）从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次入队到链队列中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。
template<class ElemType>
void Input_Int_Division( LinkQueue<ElemType> &A, string &str );
（2）计算结果中间位格式控制
string Int_String( int result );
（3）两个长整数的绝对值大小比较（x>y 返回值为1；x<y 返回值为2；x=y 返回值为0；）
template<class ElemType>
int Two_LongNum_Compare( string &A_str, string &B_str );
输入说明
第一行：长整数x
第二行：长整数y
输出说明
第一行：格式化后的长整数x（从低位到高位每4位用‘,’分开）
第二行：格式化后的长整数y（从低位到高位每4位用‘,’分开）
第三行：空行
第四行：格式化后的计算结果（从低位到高位每4位用‘,’分开）
输入范例
-53456467576846547658679870988098
435643754856985679
输出范例
-5345,6467,5768,4654,7658,6798,7098,8098
43,5643,7548,5698,5679
-5345,6467,5768,4611,2014,9250,1400,2419
AC代码
#include<iostream>
#include <sstream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<vector>
#include <climits>
#define MAX_SIZE 100
using namespace std;
template<class ElemType>
struct LinkQueueNode
{
ElemType data;
LinkQueueNode<ElemType> *next;
LinkQueueNode(LinkQueueNode<ElemType> *ptr = NULL){next = ptr;}
LinkQueueNode(const ElemType &item, LinkQueueNode<ElemType> *ptr = NULL)
{
next = ptr;
data = item;
}
};
template<class ElemType>
class LinkQueue
{
private:
LinkQueueNode<ElemType> *front;
LinkQueueNode<ElemType> *rear;
int length;
public:
LinkQueue()
{
front=rear=new LinkQueueNode<ElemType>();
front->next=NULL;
length=0;
}
int QueueLength() const{ return length;}
bool QueueisEmpty() const;
bool deQueue( ElemType &e )
{
if(QueueisEmpty())return false;
auto p=front->next;
e=p->data;
front->next=p->next;
if(rear==p)rear=front;
delete p;
length--;
return true;
}
bool enQueue( ElemType e )
{
auto p=new LinkQueueNode<ElemType>(e);
rear->next=p;
rear=p;
length++;
return true;
}
void clear()
{
rear->next=NULL;
front=rear;
length=0;
}
void change_front(int da)
{
front->data=da;
}
int front_data(){return front->data;}
LinkQueueNode<ElemType> * getfront(){return front;}
LinkQueueNode<ElemType> * getrear(){return rear;}
};
template<class ElemType>
void niprint(LinkQueue<ElemType> &A,LinkQueueNode<ElemType> *p)
{
if(p->next==NULL){cout<<p->data<<',';return ;}
niprint(A,p->next);
if(p!=A.getrear())
{
if(p->data<10)cout<<"000";
else if(p->data<100)cout<<"00";
else if(p->data<1000)cout<<"0";
}
cout<<p->data<<',';
}
template<class ElemType>
bool LinkQueue<ElemType>::QueueisEmpty() const
{
if(front==rear)return true;
return false;
}
template<class ElemType>
void Input_Int_Division( LinkQueue<ElemType> &A, string &str )
{
int numlen=str.size(),i,number,len,bj=0;
if(str[0]=='-')
{
bj++;
A.change_front(-1);
numlen--;
}
else A.change_front(1);
if(numlen%4==0)len=numlen/4;
else len=numlen/4+1;
int num=numlen%4;
for(int i = 1; i <= len; i ++)
{
if(4 * i <= numlen)
{
number = atoi(str.substr(numlen - 4*i+bj,4).c_str());
A.enQueue(number);
} else
{
number = atoi(str.substr(bj,num).c_str());
A.enQueue(number);
}
}
if(A.front_data()==-1)cout<<'-';
auto p=A.getfront()->next;
if(A.QueueLength()==1)
{
cout<<p->data;
}
else{
if(p->next!=NULL)niprint (A,p->next);
if(p->data<10)cout<<"000";
else if(p->data<100)cout<<"00";
else if(p->data<1000)cout<<"0";
cout<<p->data;
}
cout<<endl;
}
/*template<class ElemType>
string Int_String( int result )
{
}*/
int compare(string &a,string &b,int i,int j,int len)
{
for(int k=0;k<len;i++,j++,k++)
{
if(a[i]>b[j]){return 1;}
if(a[i]<b[j]){return 2;}
}
return 0;
}
template<class ElemType>
int Two_LongNum_Compare(string &A_str,string &B_str)
{
int alen=A_str.size(),blen=B_str.size(),signa=0,signb=0;
if(A_str[0]=='-'){alen--;signa=1;}
if(B_str[0]=='-'){blen--;signb=1;}
if(alen>blen)return 1;
else if(alen<blen)return 2;
else return compare(A_str,B_str,signa,signb,alen);
}
string Int_String( int result )
{
string str = "";
string Result;
stringstream ss;
ss<<result;
Result = ss.str();
if(result == 0) str = "0000";
else {
if(result < 10 && result > 0) str = "000";
if(result < 100 && result > 9) str = "00";
if(result < 1000 && result > 99) str = "0";
str.append(Result);
}
return str;
}
template<class ElemType>
void calculate(LinkQueue<ElemType>A,LinkQueue<ElemType>B,string &a,string &b)
{
int f=Two_LongNum_Compare<int>(a,b);//要有<int>
//绝对值大的放A中；
if(f<=1)
{
Input_Int_Division(A,a);
Input_Int_Division(B,b);
}
else
{
Input_Int_Division(B,a);
Input_Int_Division(A,b);
}
int carry=0;//进位
int Asignal=A.front_data(),Bsignal=B.front_data(),Atemp,Btemp,temp=0;
string result2,result;
while(!B.QueueisEmpty())
{
A.deQueue(Atemp);
B.deQueue(Btemp);
//中间的某一次计算
temp = Atemp + Bsignal * Asignal * Btemp + carry;
if(temp > 9999)
{
carry = 1;
temp = temp - 10000;
}
else if(temp < 0 )
{
carry = -1;
temp =10000 + temp;
}
else
{
carry = 0;
}
//对中间某一次计算的拼接
result2 = Int_String(temp);
result2.append(",");
result2.append(result);
result = result2;
result2 = "";
}
//如果A比较长，还没有遍历完
while(!A.QueueisEmpty() || carry == 1)
{
Atemp = 0;
A.deQueue(Atemp);
temp = Atemp + carry;
carry = 0;
result2 = Int_String(temp);
result2.append(",");
result2.append(result);
result = result2;
result2 = "";
}
//最后在统一去除其中没有用的0
int i = 0;
for(;i < result.length();i ++)
{
if(result.at(i) == '0' || result.at(i) == ',')
{
continue;
}else
{
break;
}
}
string reTemp = result.substr(i,result.length());
result = reTemp;
//最高位上补上对应的符号位
if(Asignal == -1)
{
result.insert(0,"-");
}
if(result.length()>0)
result.erase(result.length() - 1);
//输出最后的结果
cout<<endl;
if(result.length() == 0)
cout<<"0";
else
cout<<result;
}
int main()
{
string a,b;
getline(cin,a);
getline(cin,b);
LinkQueue<int> A,B;
calculate(A,B,a,b);
return 0;
}