学步园

  队列概念很简单，就是排队，先进先出，通常有链表形式和数组形式（即链接类型和顺序类型），它也是软件构建的一个基本数据结构，看看AMPS中的队列实现。

 AMPS_Queue.h

#ifndef __HEADER_AMPS_QUEUE_H
#define __HEADER_AMPS_QUEUE_H

#ifdef __cplusplus
extern "C" {
#endif

#include "AMPS_Defines.h"
#include "AMPS_LinkList.h"

typedef struct _AMPSListBasedQueue		t_AMPSListBasedQueue;
typedef struct _AMPSArrayBasedQueue		t_AMPSArrayBasedQueue;

/*链表形式的队列*/
struct _AMPSListBasedQueue
{
    int 			unCount;      /*队列结点个数*/
    t_AMPSSList* 		poQueueHead;  /*队列头指针*/
    t_AMPSSList* 		poQueueTail;  /*队列尾指针*/
};

int Queue_EnQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue);
int Queue_EnQueueListBasedDataAtHead(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, 
                                     void* r_pvDataToEnQueue);
void* Queue_DeQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);
int Queue_GetListBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);

/*数组形式的队列*/
struct _AMPSArrayBasedQueue
{
	int				nSizeOfQueue; /*队列总大小*/
    int 			unCount;      /*当前结点个数*/
    unsigned char**	ppuchQueue;   /*队列结点内容(可看做一个长度为nSizeOfQueue,内容为char*的数组)*/

	int				nHeadIndex;   /*队列头下标*/
	int				nTailIndex;   /*队列尾下标*/
};

int Queue_EnQueueArrayBasedInit(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, int r_nSizeOfQueue);
void Queue_EnQueueArrayBasedCleanup(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue);
int Queue_EnQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, void* r_pvDataToEnQueue);
void* Queue_DeQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue);
int Queue_GetArrayBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue);


#ifdef __cplusplus
}
#endif

#endif //__HEADER_AMPS_QUEUE_H

AMPS_Queue.c

/*****************************************************************
文件名称: AMPS_Queue.c
功能描述: 队列操作函数(包括链表类型队列和数据类型队列)
备注:     通常的队列是队头删除，队尾插入(这个函数库的实现刚好相反)
*****************************************************************/

#include "AMPS_Core.h"
#include "AMPS_Defines.h"
#include "AMPS_MemMgt.h"
#include "AMPS_Queue.h"
#include "AMPS_LinkList.h"

/*****************************************************************
函数名称: Queue_EnQueueListBasedData
功能描述: 向队列中写数据(链表类型队列) 队头插入
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待写入的队列
      void* r_pvDataToEnQueue      待写入队列的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*向队列中添加结点，前向插入，即向队头插入*/
	if (NULL == SList_Prepend(&poAMPSListBasedQueue->poQueueHead, r_pvDataToEnQueue))
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Prepend is failed.\n");
		return AMPS_ERROR_FAILURE;
	}

    /*在写入前，如果队列为空，队尾与队头指向同一位置*/
	if (0 == poAMPSListBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG_2, "Set Tail to Head.\n");
		poAMPSListBasedQueue->poQueueTail = poAMPSListBasedQueue->poQueueHead;
	}

    /*队列中元素个数加1*/
	poAMPSListBasedQueue->unCount++;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_EnQueueListBasedData
功能描述: 向队列中写数据(链表类型队列)，队尾插入
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待写入的队列
      void* r_pvDataToEnQueue      待写入队列的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueListBasedDataAtHead(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
	t_AMPSSList* poSList = NULL;

	TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*向队头追加结点*/
	poSList = SList_AppendEx(&poAMPSListBasedQueue->poQueueHead, r_pvDataToEnQueue);
	if(NULL == poSList)
	{
		TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Prepend is failed.\n");
		return AMPS_ERROR_FAILURE;
	}

	if(0 == poAMPSListBasedQueue->unCount)
	{
		TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG_2, "Set Tail to Head.\n");
		poAMPSListBasedQueue->poQueueTail = poAMPSListBasedQueue->poQueueHead;
	}
	else
	{
        /*将队尾指向当前结点位置，即队头指向链表首结点，队尾指向链表尾结点*/
		poAMPSListBasedQueue->poQueueTail = poSList;
	}

	poAMPSListBasedQueue->unCount++;

	TRACE(QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_DeQueueListBasedData
功能描述: 队尾结点出队列(链表类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待操作的队列

出参:
     --
返回值:
      void* 队尾结点内容

*****************************************************************/
void* Queue_DeQueueListBasedData(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
	t_AMPSSList* poSList = NULL;
	void* pvQueueData = NULL;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	if (NULL == poAMPSListBasedQueue->poQueueTail || 0 == poAMPSListBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Queue is empty.\n");
		return NULL;
	}

    /*删除队尾结点*/
	poSList = poAMPSListBasedQueue->poQueueTail->poAMPSSListPrev;
	pvQueueData = poAMPSListBasedQueue->poQueueTail->pvData;

	if (AMPS_SUCCESS != SList_Remove(&poAMPSListBasedQueue->poQueueHead, poAMPSListBasedQueue->poQueueTail, NULL))
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "SList_Remove is failed\n");
		return NULL;	
	}

	poAMPSListBasedQueue->poQueueTail = poSList;
	poAMPSListBasedQueue->unCount--;

    /*返回已删除的队尾结点的内容*/
	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return pvQueueData;
}

/*****************************************************************
函数名称: Queue_DeQueueListBasedData
功能描述: 获取队列长度(链表类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSListBasedQueue 待操作的队列

出参:
     --
返回值:
      int 队列长度

*****************************************************************/
int Queue_GetListBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSListBasedQueue* poAMPSListBasedQueue = r_pvAMPSListBasedQueue;
    return (poAMPSListBasedQueue->unCount);
}


/*****************************************************************
函数名称: Queue_EnQueueArrayBasedInit
功能描述: 队列初始化(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列
      int r_nSizeOfQueue 队列总大小

出参:
     --
返回值:
      int 

*****************************************************************/
int Queue_EnQueueArrayBasedInit(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, int r_nSizeOfQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*由于队列中存放结点内容的成员为char 
    **，所以需要在初始化时预先分配好内存，在队列销毁时释放*/
	poAMPSArrayBasedQueue->ppuchQueue = AMPS_InternalMalloc(sizeof(char*) * r_nSizeOfQueue);
	if (NULL == poAMPSArrayBasedQueue->ppuchQueue)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "AMPS_InternalMalloc failed for poAMPSArrayBasedQueue->poQueue.\n");
		return AMPS_ERROR_FAILURE;
	}

	poAMPSArrayBasedQueue->unCount = 0;
	poAMPSArrayBasedQueue->nHeadIndex = 0;
	poAMPSArrayBasedQueue->nTailIndex = 0;
	poAMPSArrayBasedQueue->nSizeOfQueue = r_nSizeOfQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: Queue_EnQueueArrayBasedInit
功能描述: 队列销毁(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      void

*****************************************************************/
void Queue_EnQueueArrayBasedCleanup(void* r_pvAMPSContext, void* r_pvAMPSListBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSListBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*释放在初始化时分配的结点内存*/
	AMPS_InternalFree(poAMPSArrayBasedQueue->ppuchQueue);

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
}

/*****************************************************************
函数名称: Queue_EnQueueArrayBasedData
功能描述: 向队列中写数据(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列
      void* r_pvDataToEnQueue       待写入的数据

出参:
     --
返回值:
      int

*****************************************************************/
int Queue_EnQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue, void* r_pvDataToEnQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*判断队列是否已满*/
	if((poAMPSArrayBasedQueue->unCount + 1) == poAMPSArrayBasedQueue->nSizeOfQueue)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR, "Queue is FULL.\n");
		return AMPS_ERROR_FAILURE;
	}

    /*新队列结点赋值*/
	//printf("Queue Head Index 1 ==> %d \n", poAMPSArrayBasedQueue->nHeadIndex);
	poAMPSArrayBasedQueue->ppuchQueue[poAMPSArrayBasedQueue->nHeadIndex] = r_pvDataToEnQueue;

    /*插入新结点*/
    poAMPSArrayBasedQueue->nHeadIndex = (poAMPSArrayBasedQueue->nHeadIndex + 1) % poAMPSArrayBasedQueue->nSizeOfQueue;
	//printf("Queue Head Index 2 ==> %d \n", poAMPSArrayBasedQueue->nHeadIndex);

    /*记数增1*/
	poAMPSArrayBasedQueue->unCount++;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return AMPS_SUCCESS;
}


/*****************************************************************
函数名称: Queue_DeQueueArrayBasedData
功能描述: 从队尾删除结点(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      void* 已删除结点内容

*****************************************************************/
void* Queue_DeQueueArrayBasedData(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;
	void* pvQueueData = NULL;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*是否为空队列*/
	if (0 == poAMPSArrayBasedQueue->unCount)
	{
		TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Queue is empty.\n");
		return NULL;
	}

	//printf("Queueu Tail Index 1 ==> %d \n", poAMPSArrayBasedQueue->nTailIndex);
	pvQueueData = poAMPSArrayBasedQueue->ppuchQueue[poAMPSArrayBasedQueue->nTailIndex];

    /*从队尾删除结点，即队尾指针上移*/
	poAMPSArrayBasedQueue->nTailIndex = (poAMPSArrayBasedQueue->nTailIndex + 1) % poAMPSArrayBasedQueue->nSizeOfQueue;
	//printf("Queueu Tail Index 2 ==> %d \n", poAMPSArrayBasedQueue->nTailIndex);
	
	poAMPSArrayBasedQueue->unCount--;

	TRACE( QUEUE_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
	return pvQueueData;
}

/*****************************************************************
函数名称: Queue_DeQueueArrayBasedData
功能描述: 获取队列结点个数(数组类型队列)
入参::
      void* r_pvAMPSContext AMPS应用上下文数据结构
      void* r_pvAMPSArrayBasedQueue 待操作的队列

出参:
     --
返回值:
      int 队列结点个数

*****************************************************************/
int Queue_GetArrayBasedQueueLength(void* r_pvAMPSContext, void* r_pvAMPSArrayBasedQueue)
{
	t_AMPSArrayBasedQueue* poAMPSArrayBasedQueue = r_pvAMPSArrayBasedQueue;
    return (poAMPSArrayBasedQueue->unCount);
}