数据结构（4）——单链队列基本操作

#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>


#define OK 1
#define ERROR -1 
#define OVERFLOW  -2
#define TRUE 1
#define FALSE 0
typedef int QElemType;
typedef int Status;


typedef struct QNode{
QElemType data;
struct QNode  *next;
}QNode, *QueuePtr;


typedef struct{
QueuePtr front;   //队头指针
QueuePtr rear;    //队尾指针 
}LinkQueue;


Status InitQueue(LinkQueue &Q);  
    //构造一个空队列Q  
Status DestroyQueue(LinkQueue &Q);  
    //销毁队列Q，Q不再存在  
Status ClearQueue(LinkQueue &Q);  
    //将Q清为空队列  
Status QueueEmpty(LinkQueue Q);  
    //若队列Q为空队列，则返回TRUE,否则返回FALSE  
int QueueLength(LinkQueue Q);  
    //返回队列Q元素个数，即队列长度  
Status GetHead(LinkQueue Q,QElemType &e);  
    //若队列不为空，则用e返回Q的队首元素，并返回OK；否则返回ERROR  
Status EnQueue(LinkQueue &Q,QElemType e);  
    //插入元素e为Q的新的队尾元素  
Status DeQueue(LinkQueue &Q,QElemType &e);  
    //若队列不为空，则删除Q的队首元素，用e返回，并返回OK；否则返回ERROR  
Status QueueTraverse(LinkQueue Q);  
    //从队首至队尾遍历队列Q中的元素  



/*构造一个空的队列*/
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(OVERFLOW);
Q.front->next = NULL;
return OK;
} //InitQueue


/*销毁队列*/
Status DestoryQueue(LinkQueue &Q){
while(Q.front){
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}//while
return OK;
}//DestoryQueue


/*将Q清为空队列 */
Status ClearQueue(LinkQueue &Q){
   QueuePtr p,q;
   Q.rear=Q.front;
   p=Q.front->next;
   Q.front->next=NULL;
   while(p)
   {
     q=p;
     p=p->next;
     free(q);
   }
return OK;
}//ClearQueue


/*若队列Q为空队列，则返回TRUE,否则返回FALSE */
Status QueueEmpty(LinkQueue Q){
if(Q.front == Q.rear&& Q.front!=NULL)
return TRUE;
else 
return FALSE;
} //QueueEmpty


/*返回队列Q的元素个数 即队列长度*/
Status QueueLength(LinkQueue Q){
QueuePtr p;
int counts=0;
p = Q.front->next;
while(p){
p = p->next;
counts++;
} 
return counts;
}//QueueLength


/*则用e返回Q的队首元素*/
Status GetHead(LinkQueue Q,QElemType &e){
if(QueueEmpty(Q) == TRUE)
return ERROR;
e = Q.front->next->data;
return OK;
}


/*插入元素E为Q的新的队尾元素*/
Status EnQueue(LinkQueue &Q,QElemType e){
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
} //EnQueue


/*删除队头元素 用e返回其值*/
Status DeQueue(LinkQueue &Q,QElemType &e){
QueuePtr p;
if(Q.rear == Q.front)  //队列为空 
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return OK; 
} //DeQueue


/*从队首至队尾遍历队列Q中的元素  */
Status QueueTraverse(LinkQueue Q){
QueuePtr p;
p = Q.front->next;
if(!p)
return ERROR;
printf("队列元素为：\n");
while(p){
printf("%d ",p->data);
p=p->next;
} //while
printf("\n");
return OK;
}//QueueTraverse


int main(){
LinkQueue Q;
QElemType t; 
InitQueue(Q);

printf("请输入元素个数：\n");
<span style="white-space:pre"></span>scanf("%d",&n);
<span style="white-space:pre"></span>for(int i=1;i<=n;i++){
<span style="white-space:pre"></span>scanf("%d",&m);
<span style="white-space:pre"></span>EnQueue(Q,m);
<span style="white-space:pre"></span>}

QueueTraverse(Q);
<span style="white-space:pre"></span>GetHead(Q,t);
<span style="white-space:pre"></span>printf("队头元素为：%d\n",t);
<span style="white-space:pre"></span>DeQueue(Q,e);
<span style="white-space:pre"></span>printf("删除队头元素：\n");
<span style="white-space:pre"></span>QueueTraverse(Q);
return 0;
}