使用c实现链式队列

队列是什么

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

队列的特定也就是绝对的公平，也就是先进入的数据一定先移除。

图像：其中的A就是元素

对于队列一样你可以使用数组去实现也可以使用链表去实现，这里我就拿链表去实现队列了。选择使用链表的原因有两个首先我们要从队头删除元素，那如果使用数组去实现的话我们入队是很简单的，但是如果我们想要出队列呢？对比于使用链表在入队时只需要模拟尾插，而出队只需要模拟头删。总言之就是出队列在数组头上出数据，效率会比较低。要完成的队列头文件：

队列要完成的函数

这里使用的链表结构是无头单向不循环链表。

// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* _pNext;
	QDataType _data;
}QNode;//我们是运用的链表实现的队列，队列的特点是先进先出
//这一个结构体代表的就是一个节点
// 队列的结构
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;//用以储存有效数据的个数
}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);

现在我来解释这两个结构体的作用，第一个结构体所创建的是一个一个节点，而第二个结构体所创建的是指向队列头和尾节点的指针。

这里我们也可以知道在不使用二级指针的条件下，我们将一个结构体指针放在另外一个结构体里面通过改变包含结构体就可以改变被包含结构体指针。

函数接口1：初始化队列

初始化队列的函数很简单我们只需要将Queue里面的结构体指针置为空即可。

void QueueInit(Queue* q)
{
	assert(q);//理由依旧是这是一个结构体指针只有外面存在结构体以后
  //才会有结构体指针所以结构体指针绝对不可能为NULL
	//这里我们只用使用一级指针就可以改变front和rear因为这两个指针都存在于queue的结构体里面
  //我们使用queue的指针就可以改变里面的值
	q->_front = NULL;
	q->_rear = NULL;//刚开始时队列中没有元素
	q->size = 0;
}

函数接口2：队尾入队列

这个函数也很简单直接模拟实现尾插链表即可

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_pNext = NULL;//创建一个储存了有效数据的新节点
	//这里就是尾插但是依旧分两种情况
	//情况一：队列为空
	if (q->_front == NULL&&q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else//情况二：队列不为空
	{
		q->_rear->_pNext = newnode;
		q->_rear = newnode;
	}
	q->size++;
}

函数接口三，四：队头出队列，判空

模拟于头删，对于所有的删除类函数我们都要进行判空，否则会导致错误。

所以我们先来写出判空函数，那么什么时候队列为空呢？很明显就是当_front和_rear指针都为空的时候队列是空的。

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->_front == NULL)&&(q->_rear==NULL);
}

下面我们就来完成出队列函数，这里需要注意一点当队列里面只有一个元素且被删除后，我们要将_front和_rear指针置空，否则就会出现野指针问题。

// 队头出队列
void QueuePop(Queue* q)
{
	//和头删差不多
	assert(q);
	assert(!QueueEmpty(q));//注意当队列为空时直接断言
	if (q->_front->_pNext == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}	
	else
	{
		QNode* tmp = q->_front;
		q->_front = q->_front->_pNext;
		free(tmp);
	}
	q->size--;
}

函数接口五：获取队列头部元素

这个函数的实现非常的简单因为对列的头部元素正是_front指针所指向的节点当然这里也需要判空。

如果没有元素的队列自然是不能进行获取元素操作的。

// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//当队列为空的时候我们就不能获取元素
	return q->_front->_data;
}

函数接口六：获取队列尾部元素

和上面的那个函数的实现是一个道理只不过指针换为了_next而已。

// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}

函数接口七：销毁队列

依次释放节点即可

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	while (!QueueEmpty(q))//这里判断队列是否为空，当队列为空的时候自然就不需要释放了
	{
		QNode* tmp = q->_front;
		q->_front = q->_front->_pNext;
		free(tmp);
	}
}

下面我们来测试队列的功能

void testqueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	printf("%d", QueueFront(&q));//获取对头元素并打印
	QueuePop(&q);//将对头元素移除
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))//判断是否为空
	{
		printf("%d", QueueFront(&q));//获取对头元素并打印
		QueuePop(&q);//将对头元素移除
	}
	QueueDestroy(&q);
}
int main()
{

	testqueue();
	return 0;
}

从这里我们也能证明队列的特点：先进先出，让入队列和出队列的顺序保证绝对一致。

还有一个获取有效元素个数的函数我就部赘述了，直接获取size即可。

所有函数实现代码

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);//理由依旧是这是一个结构体指针只有外面存在结构体以后才会有结构体指针所以结构体指针绝对不可能为NULL
	//这里我们只用使用一级指针就可以改变front和rear因为这两个指针都存在于queue的结构体里面我们使用queue的指针就可以改变里面的值
	q->_front = NULL;
	q->_rear = NULL;//刚开始时队列中没有元素
	q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_pNext = NULL;//创建一个储存了有效数据的新节点
	//这里就是尾插但是依旧分两种情况
	//情况一：队列为空
	if (q->_front == NULL&&q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else//情况二：队列不为空
	{
		q->_rear->_pNext = newnode;
		q->_rear = newnode;
	}
	q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
	//和头删差不多
	assert(q);
	assert(!QueueEmpty(q));//注意当队列为空时直接断言
	if (q->_front->_pNext == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}	
	else
	{
		QNode* tmp = q->_front;
		q->_front = q->_front->_pNext;
		free(tmp);
	}
	q->size--;//出了一个元素有效元素的个数自然会减一
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//当队列为空的时候我们就不能获取元素
	return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return (q->_front == NULL)&&(q->_rear==NULL);
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	while (!QueueEmpty(q))
	{
		QNode* tmp = q->_front;
		q->_front = q->_front->_pNext;
		free(tmp);
	}
}

希望这篇博客能对你有所帮助，如果有错误烦请指出我一定改正。