队列的实现

一、什么是队列

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

二、队列的实现

队列可以使用链表和数组实现，但是使用链表更优一些，因为出队列时，数组方式需要将后面的数据覆盖到前面来，效率较低。所以下面我们使用链表是实现队列。

我们首先需要使用结构体定义出节点的类型，然后定义队列的结构包含一个队头节点，和队尾节点。（队尾节点用于插入数据，队列需要频繁地尾插）

Queue.h

typedef int QDataType;

// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* back;
}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 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"


// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->back = q->front = NULL;

}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data = data;
	newnode->next = NULL;
	if (q->front == NULL)
	{
		q->front = q->back = newnode;
	}
	else
	{
		q->back->next = newnode;
		q->back = newnode;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	//一个节点
	if (q->front->next == NULL)
	{
		free(q->front);
		q->back = q->front = NULL;
	}
	else
	{
		//多个节点
		QNode* next = q->front->next;
		free(q->front);
		q->front = next;
	}
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->back->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	int size = 0;
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		++size;
		cur = next;
	}
	return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	return q->back == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
}