队列是常用的数据结构之一，下面给出一个链式队列的实现：
头文件Queue.h
1 #ifndef Queue_H 2 #define Queue_H 3 4 typedef int Item; 5 typedef struct node * PNode; 6 typedef struct node 7 { 8 Item data; 9 PNode next;10 }Node;11 12 typedef struct13 {14 PNode front;15 PNode rear;16 int size;17 }Queue;18 19 /*构造一个空队列*/20 Queue *InitQueue();21 22 /*销毁一个队列*/23 void DestroyQueue(Queue *pqueue);24 25 /*清空一个队列*/26 void ClearQueue(Queue *pqueue);27 28 /*判断队列是否为空*/29 int IsEmpty(Queue *pqueue);30 31 /*返回队列大小*/32 int GetSize(Queue *pqueue);33 34 /*返回队头元素*/35 PNode GetFront(Queue *pqueue,Item *pitem);36 37 /*返回队尾元素*/38 PNode GetRear(Queue *pqueue,Item *pitem);39 40 /*将新元素入队*/41 PNode EnQueue(Queue *pqueue,Item item);42 43 /*队头元素出队*/44 PNode DeQueue(Queue *pqueue,Item *pitem);45 46 /*遍历队列并对各数据项调用visit函数*/47 void QueueTraverse(Queue *pqueue,void (*visit)());48 49 #endif 实现代码Queue.c如下:
1 #include"Queue.h" 2 #include3 #include 4 5 /*构造一个空队列*/ 6 Queue *InitQueue() 7 { 8 Queue *pqueue = (Queue *)malloc(sizeof(Queue)); 9 if(pqueue!=NULL) 10 { 11 pqueue->front = NULL; 12 pqueue->rear = NULL; 13 pqueue->size = 0; 14 } 15 return pqueue; 16 } 17 18 /*销毁一个队列*/ 19 void DestroyQueue(Queue *pqueue) 20 { 21 if(IsEmpty(pqueue)!=1) 22 ClearQueue(pqueue); 23 free(pqueue); 24 } 25 26 /*清空一个队列*/ 27 void ClearQueue(Queue *pqueue) 28 { 29 while(IsEmpty(pqueue)!=1) 30 { 31 DeQueue(pqueue,NULL); 32 } 33 34 } 35 36 /*判断队列是否为空*/ 37 int IsEmpty(Queue *pqueue) 38 { 39 if(pqueue->front==NULL&&pqueue->rear==NULL&&pqueue->size==0) 40 return 1; 41 else 42 return 0; 43 } 44 45 /*返回队列大小*/ 46 int GetSize(Queue *pqueue) 47 { 48 return pqueue->size; 49 } 50 51 /*返回队头元素*/ 52 PNode GetFront(Queue *pqueue,Item *pitem) 53 { 54 if(IsEmpty(pqueue)!=1&&pitem!=NULL) 55 { 56 *pitem = pqueue->front->data; 57 } 58 return pqueue->front; 59 } 60 61 /*返回队尾元素*/ 62 63 PNode GetRear(Queue *pqueue,Item *pitem) 64 { 65 if(IsEmpty(pqueue)!=1&&pitem!=NULL) 66 { 67 *pitem = pqueue->rear->data; 68 } 69 return pqueue->rear; 70 } 71 72 /*将新元素入队*/ 73 PNode EnQueue(Queue *pqueue,Item item) 74 { 75 PNode pnode = (PNode)malloc(sizeof(Node)); 76 if(pnode != NULL) 77 { 78 pnode->data = item; 79 pnode->next = NULL; 80 81 if(IsEmpty(pqueue)) 82 { 83 pqueue->front = pnode; 84 } 85 else 86 { 87 pqueue->rear->next = pnode; 88 } 89 pqueue->rear = pnode; 90 pqueue->size++; 91 } 92 return pnode; 93 } 94 95 /*队头元素出队*/ 96 PNode DeQueue(Queue *pqueue,Item *pitem) 97 { 98 PNode pnode = pqueue->front; 99 if(IsEmpty(pqueue)!=1&&pnode!=NULL)100 {101 if(pitem!=NULL)102 *pitem = pnode->data;103 pqueue->size--;104 pqueue->front = pnode->next;105 free(pnode);106 if(pqueue->size==0)107 pqueue->rear = NULL;108 }109 return pqueue->front;110 }111 112 /*遍历队列并对各数据项调用visit函数*/113 void QueueTraverse(Queue *pqueue,void (*visit)())114 {115 PNode pnode = pqueue->front;116 int i = pqueue->size;117 while(i--)118 {119 visit(pnode->data);120 pnode = pnode->next;121 }122 123 }
简单测试程序Test.c：
1 #include"Queue.h" 2 #include3 void print(Item i) 4 { 5 printf("该节点元素为%d\n",i); 6 } 7 main() 8 { 9 Queue *pq = InitQueue();10 int i,item;11 printf("0-9依次入队并输出如下：\n");12 for(i=0;i<10;i++)13 {14 EnQueue(pq,i);15 GetRear(pq,&item);16 printf("%d ",item);17 }18 19 printf("\n从队头到队尾遍历并对每个元素执行print函数：\n"); 20 QueueTraverse(pq,print);21 22 printf("队列中元素依次出队列并输出如下：\n");23 for(i=0;i<10;i++)24 {25 DeQueue(pq,&item);26 printf("%d ",item);27 }28 ClearQueue(pq);29 if(IsEmpty(pq))30 printf("\n将队列置空成功\n");31 DestroyQueue(pq);32 printf("队列已被销毁\n");33 }