数据结构C语言实现之队列

核心提示：#include<stdio.h>#include<stdlib.h>typedefintelemType;///*以下是关于队列链接存储操作的6种算法*///structsNode{ elemTypedata;/*值域*/ structsNode*next;/*链接指针*/};structqu

#include<stdio.h>
#include<stdlib.h>
typedefintelemType;
/************************************************************************/
/*　　　　　　　　　　以下是关于队列链接存储操作的6种算法　　　　　　　*/
/************************************************************************/
structsNode{
　　 elemTypedata;　　　　　　/*值域*/
　　 structsNode*next;　　　　/*链接指针*/
};
structqueueLK{
　　 structsNode*front;　　/*队首指针*/
　　 structsNode*rear;　　　　/*队尾指针*/
};
/*1.初始化链队*/
voidinitQueue(structqueueLK*hq)
{
　　 hq->front=hq->rear=NULL;　　　　/*把队首和队尾指针置空*/
　　 return;
}
/*2.向链队中插入一个元素x*/
voidenQueue(structqueueLK*hq,elemTypex)
{
　　 /*得到一个由newP指针所指向的新结点*/
　　 structsNode*newP;
　　 newP=malloc(sizeof(structsNode));
　　 if(newP==NULL){
　　　　 printf("内存空间分配失败！ ");
　　　　 exit(1);
　　 }
　　 /*把x的值赋给新结点的值域，把新结点的指针域置空*/
　　 newP->data=x;
　　 newP->next=NULL;
　　 /*若链队为空，则新结点即是队首结点又是队尾结点*/
　　 if(hq->rear==NULL){
　　　　 hq->front=hq->rear=newP;
　　 }else{　　/*若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点*/
　　　　 hq->rear=hq->rear->next=newP;　　　　/*注意赋值顺序哦*/
　　 }
　　 return;
}
/*3.从队列中删除一个元素*/
elemTypeoutQueue(structqueueLK*hq)
{
　　 structsNode*p;
　　 elemTypetemp;
　　 /*若链队为空则停止运行*/
　　 if(hq->front==NULL){
　　　　 printf("队列为空，无法删除！ ");
　　　　 exit(1);
　　 }
　　 temp=hq->front->data;　　　　/*暂存队尾元素以便返回*/
　　 p=hq->front;　　　　　　　　/*暂存队尾指针以便回收队尾结点*/
　　 hq->front=p->next;　　　　/*使队首指针指向下一个结点*/
　　 /*若删除后链队为空，则需同时使队尾指针为空*/
　　 if(hq->front==NULL){
　　　　 hq->rear=NULL;
　　 }
　　 free(p);　　　　/*回收原队首结点*/
　　 returntemp;　　/*返回被删除的队首元素值*/
}
/*4.读取队首元素*/
elemTypepeekQueue(structqueueLK*hq)
{
　　 /*若链队为空则停止运行*/
　　 if(hq->front==NULL){
　　　　 printf("队列为空，无法删除！ ");
　　　　 exit(1);
　　 }
　　 returnhq->front->data;　　　　/*返回队首元素*/
}
/*5.检查链队是否为空，若为空则返回1,否则返回0*/
intemptyQueue(structqueueLK*hq)
{
　　 /*判断队首或队尾任一个指针是否为空即可*/
　　 if(hq->front==NULL){
　　　　 return1;
　　 }else{
　　　　 return0;
　　 }
}
/*6.清除链队中的所有元素*/
voidclearQueue(structqueueLK*hq)
{
　　 structsNode*p=hq->front;　　　　/*队首指针赋给p*/
　　 /*依次删除队列中的每一个结点，最后使队首指针为空*/
　　 while(p!=NULL){
　　　　 hq->front=hq->front->next;
　　　　 free(p);
　　　　 p=hq->front;
　　 }　　/*循环结束后队首指针已经为空*/
　　 hq->rear=NULL;　　　　/*置队尾指针为空*/
　　 return;
}
/************************************************************************/
intmain(intargc,char*argv[])
{
　　 structqueueLKq;
　　 inta[8]={3,8,5,17,9,30,15,22};
　　 inti;
　　 initQueue(&q);
　　 for(i=0;i<8;i++){
　　　　 enQueue(&q,a[i]);
　　 }
　　 printf("%d",outQueue(&q));　　printf("%d　",outQueue(&q));
　　 enQueue(&q,68);
　　 printf("%d",peekQueue(&q));　　printf("%d　",outQueue(&q));
　　 while(!emptyQueue(&q)){
　　　　 printf("%d",outQueue(&q));
　　 }
　　 printf(" ");
　　 clearQueue(&q);
　　 system("pause");
}
#include<stdio.h>
#include<stdlib.h>
typedefintelemType;
/************************************************************************/
/*　　　　　　　　　　　以下是关于队列顺序存储操作的6种算法　　　　　　　*/
/************************************************************************/
structqueue{
　　 elemType*queue;　　　　/*指向存储队列的数组空间*/
　　 intfront,rear,len;　　/*队首指针（下标），队尾指针（下标），队列长度变量*/
　　 intmaxSize;　　　　　　/*queue数组长度*/
};
voidagainMalloc(structqueue*q)
{
　　 /*空间扩展为原来的2倍，原内容被自动拷贝到p所指向的存储空间中*/
　　 elemType*p;
　　 p=realloc(q->queue,2*q->maxSize*sizeof(elemType));
　　 /*动态存储空间分配，若失败则退出运行*/
　　 if(!p){
　　　　 printf("空间分配失败！ ");
　　　　 exit(1);
　　 }
　　 q->queue=p;　　　　/*使queue指向新的队列空间*/
　　 /*把原队列的尾部内容后移maxSize个位置*/
　　 if(q->rear!=q->maxSize-1){
　　　　 inti;
　　　　 for(i=0;i<=q->rear;i++){
　　　　　　 q->queue[i+q->maxSize]=q->queue[i];
　　　　 }
　　　　 q->rear+=q->maxSize;　　　　/*队尾指针后移maxSize个位置*/
　　 }
　　 q->maxSize=2*q->maxSize;　　/*把队列空间大小修改为新的长度*/
　　 return;
}
/*1.初始化队列*/
voidinitQueue(structqueue*q,intms)
{
　　 /*检查ms是否有效，若无效则退出运行*/
　　 if(ms<=0){
　　　　 printf("ms值非法! ");
　　　　 exit(1);
　　 }
　　 q->maxSize=ms;　　　　/*置队列空间大小为ms*/
　　 /*动态存储空间分配，若失败则退出运行*/
　　 q->queue=malloc(ms*sizeof(elemType));
　　 if(!q->queue){
　　　　 printf("内存空间分配失败！ ");
　　　　 exit(1);
　　 }
　　 q->front=q->rear=0;　　　　/*初始置队列为空*/
　　 return;
}
/*2.向队列中插入元素x*/
voidenQueue(structqueue*q,elemTypex)
{
　　 /*当队列满时进行动态生分配*/
　　 if((q->rear+1)%q->maxSize==q->front){
　　　　 againMalloc(q);
　　 }
　　 q->rear=(q->rear+1)%q->maxSize;　　　　/*求出队尾的下一个位置*/
　　 q->queue[q->rear]=x;　　　　　　　　　　　　/*把x的值赋给新的队尾*/
　　 return;
}
/*3.从队列中删除元素并返回*/
elemTypeoutQueue(structqueue*q)
{
　　 /*若队列为空则终止运行*/
　　 if(q->front==q->rear){
　　　　 printf("队列为空，无法删除！ ");
　　　　 exit(1);
　　 }
　　 q->front=(q->front+1)%q->maxSize;　　　　/*使队首指针指向下一个位置*/
　　 returnq->queue[q->front];　　　　　　　　　　/*返回队首元素*/
}
/*4.读取队首元素，不改变队列状态*/
elemTypepeekQueue(structqueue*q)
{
　　 /*若队列为空则终止运行*/
　　 if(q->front==q->rear){
　　　　 printf("队列为空，无法删除！ ");
　　　　 exit(1);
　　 }
　　 returnq->queue[(q->front+1)%q->maxSize];/*队首元素是队首指针的下一个位置中的元素*/
}
/*5.检查一个队列是否为空，若是则返回1,否则返回0*/
intemptyQueue(structqueue*q)
{
　　 if(q->front==q->rear){
　　　　 return1;
　　 }else{
　　　　 return0;
　　 }
}
/*6.清除一个队列，并释放动态存储空间*/
voidclearQueue(structqueue*q)
{
　　 if(q->queue!=NULL){
　　　　 free(q->queue);
　　　　 q->queue=NULL;　　　　　　/*设置队列空间指针为空*/
　　　　 q->front=q->rear=0;　　　　/*设置队列为空*/
　　　　 q->maxSize=0;　　　　　　　　/*设置队列大小为0*/
　　 }
　　 return;
}
/************************************************************************/
intmain(intargc,char*argv[])
{
　　 structqueueq;
　　 inta[8]={3,8,5,17,9,30,15,22};
　　 inti;
　　 initQueue(&q,5);
　　 for(i=0;i<8;i++){
　　　　 enQueue(&q,a[i]);
　　 }
　　 printf("%d",outQueue(&q));　　printf("%d　",outQueue(&q));
　　 enQueue(&q,68);
　　 printf("%d",peekQueue(&q));　　printf("%d　",outQueue(&q));
　　 while(!emptyQueue(&q)){
　　　　 printf("%d",outQueue(&q));
　　 }
　　 printf(" ");
　　 clearQueue(&q);
　　 system("pause");
　　 return0;
}