在前面，相信大家也已经感觉到，如果用单链表实现队列，不含队头队尾指针，每次入队操作都要遍历单链表，所以极不方便。那么在这里，就给大家介绍下含有队头队尾指针的队列（单链表实现）。

 

        如图

 

 

 

        这里介绍双向链表的常用操作：

 

l 创建队列

l 销毁队列

l 清空队列

l 入队

l 出队

l 返回队首元素

l 返回队的大小

 

 

   代码总分为三个文件：

LinkQueue.h ： 放置功能函数的声明，以及表的声明 

LinkQueue.c ： 放置功能函数的定义，以及表的定义，表结点的定义

Main.c     ： 主函数，使用功能函数完成各种需求，一般用作测试

 

   整体结构图为：

 

 

   这里详细说下入队操作，出队操作和返回队首元素操作：

 

入队操作：

 

 如图：

  

出队操作：

 

 如图：

 

返回队首元素：

 

如图：

 

 

 

OK! 上代码：

 

LinkQueue.h ： 

#ifndef _LINKQUEUE_H_#define _LINKQUEUE_H_typedef void LinkQueue;LinkQueue* LinkQueue_Create();void LinkQueue_Destroy(LinkQueue* queue);void LinkQueue_Clear(LinkQueue* queue);int LinkQueue_Append(LinkQueue* queue, void* item);void* LinkQueue_Retrieve(LinkQueue* queue);void* LinkQueue_Header(LinkQueue* queue);int LinkQueue_Length(LinkQueue* queue);#endif

 

LinkQueue.c ： 

#include 
       
        #include 
        
         #include "LinkQueue.h"typedef struct _tag_LinkQueueNode TLinkQueueNode;struct _tag_LinkQueueNode{	TLinkQueueNode* next;	void* item;	};typedef struct _tag_LinkQueue{	TLinkQueueNode* front;	TLinkQueueNode* rear;	int length;	}TLinkQueue;LinkQueue* LinkQueue_Create(){	TLinkQueue* ret = (TLinkQueue*)malloc(sizeof(TLinkQueue));		if(NULL != ret)	{		ret->front = NULL;		ret->rear  = NULL;		ret->length= 0;	}		return ret;}void LinkQueue_Destroy(LinkQueue* queue){	LinkQueue_Clear(queue);		free(queue);}void LinkQueue_Clear(LinkQueue* queue){	while(LinkQueue_Length(queue) > 0)	{		LinkQueue_Retrieve(queue);	}}int LinkQueue_Append(LinkQueue* queue, void* item){	TLinkQueue* sQueue = (TLinkQueue*)queue;		TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));		int ret = (NULL!=sQueue) && (NULL!=item) && (NULL!=node);		if(ret)	{		node->item = item;				if(0 < sQueue->length)		{			sQueue->rear->next = node;			sQueue->rear = node;			node->next = NULL;		}		else		{			sQueue->front = node;			sQueue->rear = node;			node->next = NULL;		}				sQueue->length++;	}		if(!ret)	{		free(node);	}		return ret;}void* LinkQueue_Retrieve(LinkQueue* queue){	TLinkQueue* sQueue = (TLinkQueue*)queue;		TLinkQueueNode* node = NULL;		void* ret = NULL;		if((NULL != sQueue) && (0 < sQueue->length))	{		node = sQueue->front;		sQueue->front = node->next;				ret = node->item;				free(node);				sQueue->length--;				if(0 == sQueue->length)		{			sQueue->front = NULL;			sQueue->rear  = NULL;		}	}		return ret;}void* LinkQueue_Header(LinkQueue* queue){	TLinkQueue* sQueue = (TLinkQueue*)queue;		void* ret = NULL;		if((NULL!=sQueue)&&(0
         
          length))	{		ret = sQueue->front->item;	}		return ret;}int LinkQueue_Length(LinkQueue* queue){	TLinkQueue* sQueue = (TLinkQueue*)queue;		int ret = -1;		if(NULL != sQueue)	{		ret = sQueue->length;	}		return ret;}
         
        
       

 

Main.c     ：

 

#include 
      
       #include 
       
        #include "LinkQueue.h"int main(void){	LinkQueue* queue = LinkQueue_Create();		int a[10];	int i = 0;		for(i=0; i<10; i++)	{		a[i] = i+1;				LinkQueue_Append(queue, a+i);	}		printf("Header:  %d\n", *(int*)LinkQueue_Header(queue));	printf("Length:  %d\n\n", LinkQueue_Length(queue));		//LinkQueue_Clear(queue);		while(LinkQueue_Length(queue) > 0)	{		printf("Retrieve:  %d\n", *(int*)LinkQueue_Retrieve(queue));	}		LinkQueue_Destroy(queue);		return 0;}