linkqueue.cpp

定义链队列结点结构：数据域data和指针域next

#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);


}