#include <iostream.h>
#include "stdlib.h"
typedef int elementtype;
typedef struct node           //定義鏈隊列結點結構：數據域data和指針域next
{
 elementtype data;
 struct node *next;
}QNode;

typedef struct linkQueue   //定義鏈隊列  
{
	QNode  *front, *rear;     //鏈隊列的隊首指針front和隊尾指針rear
}LinkQ; //鏈隊列類型

void init_que(LinkQ &Q)  //隊列初始化
{Q.front=Q.rear=0;
 //Q.front->next=0;
 //Q.rear->next=0;
}

int qempty(LinkQ Q) //判斷隊列是否空，非零值為空隊列
{return Q.rear==0;}

void Qgetfront(LinkQ Q)//取隊列隊首元素值
{ if(qempty(Q)) cout<<"隊列空!"<<endl;
else
cout<<Q.front->data<<endl;
}
void Qgetrear(LinkQ Q)//取隊列隊尾元素值
{ if(qempty(Q)) cout<<"隊列空!"<<endl;
else
cout<<Q.rear->data<<endl;
}
void qinsert(LinkQ &Q,elementtype x) //入鏈隊操作的實現
{ QNode *p=new QNode;  //申請新空間
  p->data=x;       //給數據域賦值
  p->next=0; //因為是隊尾入隊，因此指針域值為0；
  if(Q.rear!=0) Q.rear->next=p;//若是第一個結點
  if(Q.front==0) Q.front=p;
  Q.rear=p;//指向新隊尾
}

void  qdelete (LinkQ &Q,elementtype &x)    //出鏈隊操作實現
{QNode *p;
if(qempty(Q))cout<<"隊列為空"<<endl;
else
{p=Q.front;
x=p->data;  
Q.front=p->next ; //原隊首的直接后繼成為新的隊首。
p->next=0;
if(Q.front==0) Q.rear=0;
delete p;    //刪除結點
}
}
void q_print(LinkQ Q)//輸出鏈隊列中的元素
{QNode *p;
p=Q.front;//獲取隊首結點
while(p!=0)
{cout<<p->data <<"  ";
p=p->next;
}
cout<<endl;
}
void  huiwen(char str[],int n)
{
	LinkQ Q1,Q2;
	int i;
	init_que(Q1);init_que(Q2);
	for(i=0;i<n;i++) qinsert(Q1,str[i]);
    for(i=n-1;i>=0;i--) qinsert(Q2,str[i]);
	elementtype e1,e2;
	while(!qempty(Q1))
	{qdelete(Q1,e1);qdelete(Q2,e2);
	 if(e1!=e2) break;
	}
	 if(!qempty(Q1) &&!qempty(Q2))
		 cout<<"不是回文!"<<endl;
   else
     cout<<"是回文!"<<endl;

  }

void main()   //測試隊列
{int a[7]={23,45,67,89,21,53,89};
LinkQ q;
 elementtype y;

//init_que(q); //調用初始化函數
//qinsert(q,a[1]);
/*
 for(int i=0;i<7;i++)
  qinsert(q,a[i]); //調用入隊函數，以入鏈隊的方式，建立鏈隊列
 Qgetfront(q);//調用取隊首元素函數
 q_print(q);//調用輸出鏈隊列函數，輸出隊列
 cout<<endl; 
 qdelete(q,y);//調用出鏈隊列函數，出隊一個元素
 cout<<y<<endl;//輸出出隊列元素值
 qdelete(q,y);//再出隊
 cout<<y<<endl;
  q_print(q);//輸出出隊之后，隊列剩余的元素
  Qgetrear(q);*/
huiwen("thissaht",8);


}