队列的实现

队列

1.队列的概念及结构

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

2.队列的实现

队列也可以由数组和链表实现，但是由链表实现更好。因为如果使用数组的结构，出队列在数组头上的数据，效率会比较低。

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
// 链式结构：表示队列 
typedef int QDataType;
//单个节点的结构体
typedef struct QListNode
{
	struct QListNode* _next;
	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);

初始化一个队列

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
	q->size = 0;
}

下面这个是测试时要用到的打印代码

void print(Queue* q,int size)
{
	assert(q);
	QNode* str = q->_front;
	for (int i=0;i<size;i++)	
	{
		printf("%d ",str->_data);
		str = str->_next;
	}
}

获取队列中有效元素个数

int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

队尾插入数据

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->_next = NULL;
	if (q->_front ==NULL)
	{
		q->_front = q->_rear=newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
		
	}
	q->size++;

}

代码的实现

队头释放节点

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front);
	QNode* tem = q->_front;
	q->_front = q->_front->_next;
	free(tem);
	tem = NULL;
	if (q->_front == NULL)
	{
		q->_rear = NULL;
	}
	q->size--;
}

返回队头节点

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}

返回队尾节点

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);

	return q->_rear->_data;
}

检查队列是否为空

bool QueueEmpty(Queue* q)
{

	assert(q);
	return q->_front == NULL;
}

不为空

为空

销毁队列

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;

	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

先将每一个节点依次释放，然后再销毁队列