队列的实现

什么是队列队列用数组（顺序表）还是用线性表头文件入队出队初始化打印访问队头元素访问队尾元素队列的大小销毁

队列：只允许在一端进行插入数据操作，另一端进行删除数据操作特殊的线性表。
他具有先进先出（FIFO）特性，进行插入的一端为队尾，进行删除的一端为队头。

要出队列的性质去分析，先进先出。当我们在队头删除的时候，如果用数组，明显的要挪动元素，
这样效率太低了，所以用链表更好一些。

#include
#include
#include
#include

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

// 初始化队列
void QueueInit(Queue* q);

// 队尾入队列
void QueuePush(Queue* q, QDataType data);

// 队头出队列
void QueuePop(Queue* q);

// 获取队列头部元素
QDataType QueueFront(Queue* q);

// 获取队列队尾元素
QDataType QueueBack(Queue* q);

// 获取队列中有效元素个数
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);

// 销毁队列
void QueueDestroy(Queue* q);

这里涉及两个结构体，画图示意一下。

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//这里判断链表为空不能用head==tail，因为只有一个节点也是这样
	if (q->head == NULL && q->tail==NULL)
	{
		q->head = newnode;
		q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}

void QueuePop(Queue* q)
{
	assert(q);
	//分为三种情况，无节点，1个节点，多个节点
	if (q->head == NULL && q->tail == NULL)
	{
		printf("NO Data to Popn");
		return;
	}
	else if (q->head == q->tail)
	{
		QNode* cur = q->head;
		free(cur);
		q->head = q->tail = NULL;
	}
	else
	{
		QNode* cur = q->head->next;
		free(q->head);
		q->head = cur;
	}
}

初始化就很简单啦

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

void QueuePrint(Queue* q)
{
	assert(q);
	assert(q->head);
	if (q->tail == q->head)
		printf("%d ", q->head->data);
	else
	{
		QNode* cur = q->head;
		while (cur)
		{
			printf("%d ", cur->data);
			cur = cur->next;
		}
	}
	printf("n");
} 

QDataType QueueFront(Queue* q)
{
	assert(q);
    assert(q->tail && q->head); //没有元素还访问啥
	return q->head->data;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail && q->head); //没有元素还访问啥
	return q->tail->data;
}

int QueueSize(Queue* q)
{
	assert(q);
	if (q->head == NULL && q->tail == NULL)
	{
		return 0;
	}
	else if (q->head == q->tail)
	{
		return 1;
	}
	else
	{
		int count = 0;
		QNode* cur = q->head;
		while (cur)
		{
			count++;
			cur = cur->next;
		}
		return count;
	}
}

void QueueDestroy(Queue* q)
{
	assert(q);
	assert(q->tail && q->head);

	QNode* cur = q->head;
	while (cur)
	{
		QNode* save = cur->next;
		free(cur);
		cur = save;
	}
}