队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

1.队列结构定义

typedef int QDataType;

//节点定义
typedef struct QueueNode
{	
	QDataType data;				//数据域
	struct QueueNode* next;		//指针域
};

typedef struct Queue
{	
	QueueNode* head;			//队列头指针
	QueueNode* tail;			//队列尾指针
};

2.队列初始化

void QueueInit(Queue* pq){
	assert(pq != NULL);
	pq->head = NULL;
	pq->tail = NULL;
};

3.队列的销毁

void QueueDestroy(Queue* pq){
	assert(pq != NULL);
	struct QueueNode* cur;
	cur = pq->head;
	while(cur != NULL)          //遍历节点
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
};

4.入队（尾节点后插入）

void QueuePush(Queue* pq, QDataType x){
	assert(pq != NULL);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if(newnode == NULL)
	{
		printf("malloc fault!");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if(pq->tail == NULL)							//判断是否为空队列
	{
		assert(pq->head == NULL);
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;	
		pq->tail = newnode;
	}
};

5.出队（删除头结点）

void QueuePop(Queue* pq){
	assert(pq != NULL);
	assert(pq->head != NULL && pq->tail != NULL);

	if(pq->head->next == NULL)						//如果队列就一个元素
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
};

6.取出队首元素

QDataType QueueGetFront(Queue* pq){
	assert(pq != NULL);
	assert(pq->head != NULL && pq->tail != NULL);  //防止队列为空队列

	return pq->head->data;
};

7.判断队是否为空,如果为空返回1，不为空返回0

int QueueIsempty(Queue* pq){
	assert(pq != NULL);

	return pq->head == NULL;
};

8.求队列的长度

int QueueGetCount(Queue* pq){
	assert(pq != NULL);
	int count = 0;
	QueueNode* cur = pq->head;
	while(cur != NULL)
	{
		cur = cur->next;
		count++;
	}
	return count;
};