一步一步写算法（之线性队列）

原文:一步一步写算法（之线性队列）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    这里的线性结构实际上指的就是连续内存的意思，只不过使用“线性”这个词显得比较专业而已。前面一篇博客介绍了现象结构的处理方法，那么在这个基础之上我们是不是添加一些属性形成一种新的数据结构类型呢？答案是肯定的，队列便是其中的一种。

    队列的性质很简单：

    （1）队列有头部和尾部

    （2）队列从尾部压入数据

    （3）队列从头部弹出数据

    那么连续内存下的队列是怎么实现的呢？

    a）设计队列数据结构

typedef struct _QUEUE_NODE
{
	int* pData;
	int length;
	int head ;
	int tail;
	int count;
}QUEUE_NODE;

    b）申请队列内存

QUEUE_NODE* alloca_queue(int number)
{
	QUEUE_NODE* pQueueNode;
	if( 0 == number)
		return NULL;

	pQueueNode = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE));
	assert(NULL != pQueueNode);
	memset(pQueueNode, 0, sizeof(QUEUE_NODE));

	pQueueNode->pData = (int*)malloc(sizeof(int) * number);
	if(NULL == pQueueNode->pData){
		free(pQueueNode);
		return NULL;
	}

	pQueueNode->length = number;
	return pQueueNode;
}

    c）释放队列内存

STATUS delete_queue(const QUEUE_NODE* pQueueNode)
{
	if(NULL == pQueueNode)
		return FALSE;

	assert(NULL != pQueueNode->pData);

	free(pQueueNode->pData);
	free((void*)pQueueNode);
	return TRUE;
}

    d）把数据压入队列

STATUS insert_queue(QUEUE_NODE* pQueueNode, int value)
{
	if(NULL == pQueueNode)
		return FALSE;

	if(pQueueNode->length == pQueueNode->count)
		return FALSE;

	pQueueNode->pData[pQueueNode->tail] = value;
	pQueueNode->tail = (pQueueNode->tail + 1) % pQueueNode->length;
	pQueueNode->count ++;
	return TRUE;
}

    e）把数据弹出队列

STATUS get_queue_data(QUEUE_NODE* pQueueNode, int* value)
{
	if(NULL == pQueueNode || NULL == value)
		return FALSE;

	if(0 == pQueueNode->count)
		return FALSE;

	*value = pQueueNode->pData[pQueueNode->head];
	pQueueNode-> pData[pQueueNode->head] = 0;
	pQueueNode-> count --;
	pQueueNode->head = (pQueueNode->head + 1) % pQueueNode->length;
	return TRUE;
}

    f）统计当前队列中有多少数据

int  get_total_number(const QUEUE_NODE* pQueueNode)
{
	if(NULL == pQueueNode)
		return 0;

	return pQueueNode->count;
}

    g）查看队列中初始化的时候总长度是多少

int  get_total_number(const QUEUE_NODE* pQueueNode)
{
	if(NULL == pQueueNode)
		return 0;

	return pQueueNode->length;
}

【预告： 下一篇博客介绍线性堆栈的内容】