队列是常用的数据结构之一，下面给出一个链式队列的实现：
头文件Queue.h
#ifndef Queue_H
#define Queue_H typedef int Item;
typedef struct node * PNode;
typedef struct node
{
Item data;
PNode next;
}Node; typedef struct
{
PNode front;
PNode rear;
int size;
}Queue; /*构造一个空队列*/
Queue *InitQueue(); /*销毁一个队列*/
void DestroyQueue(Queue *pqueue); /*清空一个队列*/
void ClearQueue(Queue *pqueue); /*判断队列是否为空*/
int IsEmpty(Queue *pqueue); /*返回队列大小*/
int GetSize(Queue *pqueue); /*返回队头元素*/
PNode GetFront(Queue *pqueue,Item *pitem); /*返回队尾元素*/
PNode GetRear(Queue *pqueue,Item *pitem); /*将新元素入队*/
PNode EnQueue(Queue *pqueue,Item item); /*队头元素出队*/
PNode DeQueue(Queue *pqueue,Item *pitem); /*遍历队列并对各数据项调用visit函数*/
void QueueTraverse(Queue *pqueue,void (*visit)()); #endif
实现代码Queue.c如下:
#include"Queue.h"
#include<malloc.h>
#include<stdio.h> /*构造一个空队列*/
Queue *InitQueue()
{
Queue *pqueue = (Queue *)malloc(sizeof(Queue));
if(pqueue!=NULL)
{
pqueue->front = NULL;
pqueue->rear = NULL;
pqueue->size = ;
}
return pqueue;
} /*销毁一个队列*/
void DestroyQueue(Queue *pqueue)
{
if(IsEmpty(pqueue)!=)
ClearQueue(pqueue);
free(pqueue);
} /*清空一个队列*/
void ClearQueue(Queue *pqueue)
{
while(IsEmpty(pqueue)!=)
{
DeQueue(pqueue,NULL);
} } /*判断队列是否为空*/
int IsEmpty(Queue *pqueue)
{
if(pqueue->front==NULL&&pqueue->rear==NULL&&pqueue->size==)
return ;
else
return ;
} /*返回队列大小*/
int GetSize(Queue *pqueue)
{
return pqueue->size;
} /*返回队头元素*/
PNode GetFront(Queue *pqueue,Item *pitem)
{
if(IsEmpty(pqueue)!=&&pitem!=NULL)
{
*pitem = pqueue->front->data;
}
return pqueue->front;
} /*返回队尾元素*/ PNode GetRear(Queue *pqueue,Item *pitem)
{
if(IsEmpty(pqueue)!=&&pitem!=NULL)
{
*pitem = pqueue->rear->data;
}
return pqueue->rear;
} /*将新元素入队*/
PNode EnQueue(Queue *pqueue,Item item)
{
PNode pnode = (PNode)malloc(sizeof(Node));
if(pnode != NULL)
{
pnode->data = item;
pnode->next = NULL; if(IsEmpty(pqueue))
{
pqueue->front = pnode;
}
else
{
pqueue->rear->next = pnode;
}
pqueue->rear = pnode;
pqueue->size++;
}
return pnode;
} /*队头元素出队*/
PNode DeQueue(Queue *pqueue,Item *pitem)
{
PNode pnode = pqueue->front;
if(IsEmpty(pqueue)!=&&pnode!=NULL)
{
if(pitem!=NULL)
*pitem = pnode->data;
pqueue->size--;
pqueue->front = pnode->next;
free(pnode);
if(pqueue->size==)
pqueue->rear = NULL;
}
return pqueue->front;
} /*遍历队列并对各数据项调用visit函数*/
void QueueTraverse(Queue *pqueue,void (*visit)())
{
PNode pnode = pqueue->front;
int i = pqueue->size;
while(i--)
{
visit(pnode->data);
pnode = pnode->next;
} }
简单测试程序Test.c：
#include"Queue.h"
#include<stdio.h>
void print(Item i)
{
printf("该节点元素为%d\n",i);
}
main()
{
Queue *pq = InitQueue();
int i,item;
printf("0-9依次入队并输出如下：\n");
for(i=;i<;i++)
{
EnQueue(pq,i);
GetRear(pq,&item);
printf("%d ",item);
} printf("\n从队头到队尾遍历并对每个元素执行print函数：\n");
QueueTraverse(pq,print); printf("队列中元素依次出队列并输出如下：\n");
for(i=;i<;i++)
{
DeQueue(pq,&item);
printf("%d ",item);
}
ClearQueue(pq);
if(IsEmpty(pq))
printf("\n将队列置空成功\n");
DestroyQueue(pq);
printf("队列已被销毁\n");
}