队列（Queue）

队列是一种特殊的受限制的线性表。  

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

LinkQueue.h：

#ifndef LINKQUEUE_H
#define LINKQUEUE_H

#define QUEUE_FALSE 0
#define QUEUE_TRUE 1

#include<stdlib.h>
#include<stdio.h>

//链表队列结点
typedef struct _LINKNODE{
	void* data;
	struct _LINKNODE* next;
}LinkNode;

//链式队列头结点
typedef struct _LINKQUEUE{
	LinkNode* head;
	int length;
}LinkQueue;

//初始化链式队列
LinkQueue* InitLinkQueue();
//销毁链式队列
void DestroyLinkQueue(LinkQueue* lqueue);
//向队尾插入结点
int PushLinkQueue(LinkQueue* lqueue,void* data);
//返回对头数据
void* FrontLinkQueue(LinkQueue* lqueue);
//弹出对头结点
void PopLinkQueue(LinkQueue* lqueue);
//返回队列长度
int GetLengthLinkQueue(LinkQueue* lqueue);
//判断队列是否为空
int IsEmptyLinkQueue(LinkQueue* lqueue);

#endif

LinkQueue.c：

#include"LinkQueue.h"

//初始化链式队列
LinkQueue* InitLinkQueue(){

	LinkQueue* lqueue = (LinkQueue*)malloc(sizeof(LinkQueue));
	if (lqueue == NULL){
		return NULL;
	}

	lqueue->head = NULL;
	lqueue->length = 0;

	return lqueue;
}
//销毁链式队列
void DestroyLinkQueue(LinkQueue* lqueue){

	while (!IsEmptyLinkQueue(lqueue)){
		PopLinkQueue(lqueue);
	}
	free(lqueue);
}
//向队尾插入结点
int PushLinkQueue(LinkQueue* lqueue, void* data){

	//创建新结点
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	newnode->data = data;
	newnode->next = NULL;

	//第一次插入
	if (lqueue->head == NULL){
		lqueue->head = newnode;
		lqueue->length++;
		return 0;
	}

	//其他插入
	newnode->next = lqueue->head;
	lqueue->head = newnode;
	lqueue->length++;

	return 0;
}
//返回对头数据
void* FrontLinkQueue(LinkQueue* lqueue){
	LinkNode* pCurrent = lqueue->head;
	while (pCurrent->next != NULL){
		pCurrent = pCurrent->next;
	}
	return pCurrent->data;
}
//弹出对头结点
void PopLinkQueue(LinkQueue* lqueue){

	//如果只有一个结点
	if (lqueue->length == 1){
		free(lqueue->head);
		lqueue->head = NULL;
		lqueue->length--;
		return;
	}
	//多于一个结点
	LinkNode* pPrev = lqueue->head;
	LinkNode* pCurrent = pPrev->next;
	while (pCurrent->next != NULL){
		pPrev = pCurrent;
		pCurrent = pPrev->next;
	}
	free(pCurrent);
	pPrev->next = NULL;
	lqueue->length--;
}
//返回队列长度
int GetLengthLinkQueue(LinkQueue* lqueue){
	return lqueue->length;
}
//判断队列是否为空
int IsEmptyLinkQueue(LinkQueue* lqueue){
	if (lqueue->length == 0){
		return QUEUE_TRUE;
	}
	return QUEUE_FALSE;
}

main.c

#include"LinkQueue.h"


typedef struct _TEAHCER{
	char name[64];
	int age;
}Teacher;

void test01(){
	
	//创建链式队列
	LinkQueue* queue = InitLinkQueue();
	//创建数据
	Teacher t1, t2, t3;
	t1.age = 10;
	t2.age = 20;
	t3.age = 30;
	strcpy(t1.name, "aaa");
	strcpy(t2.name, "bbb");
	strcpy(t3.name, "ccc");
	//链式队列插入数据
	PushLinkQueue(queue, &t1);
	PushLinkQueue(queue, &t3);
	PushLinkQueue(queue, &t2);
	//打印链式队列
	printf("链式队列长度:%d\n",GetLengthLinkQueue(queue));
	while (!IsEmptyLinkQueue(queue)){
		Teacher* teacher = (Teacher*)FrontLinkQueue(queue);
		printf("Name:%s Age:%d\n",teacher->name,teacher->age);
		PopLinkQueue(queue);
	}
	printf("链式队列长度:%d\n", GetLengthLinkQueue(queue));
	//销毁链式队列
	DestroyLinkQueue(queue);

}

int main(){
	
	test01();
	
	system("pause");
	return EXIT_SUCCESS;
}