数据结构-队列的实现

队列的基本概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，
    队列具有先进先出FIFO(First In First Out) 
    入队列：进行插入操作的一端称为队尾
    出队列：进行删除操作的一端称为队头

思考：用什么结构实现队列

数组

链表

综上，我们选择用链表实现

1.0-队列结构

==为了方便尾插，头删。我们定义两个指针标志头和尾==

typedef int QDataType;
//队列中的结构体
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//存放指向结构体的两个指针
typedef struct Queue
{
	QueueNode* head;//指向链表的头
	QueueNode* tail;//指向链表的尾
}Queue;

1.1-初始化

最初：把两个指针置空

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

1.2-销毁

由于队列是用链表实现的

链表中每个结点都是malloc出来的，所以我们需要遍历把链表的结点释放掉

释放时要注意：

**1.要先保存下一个结点再释放 **

2.释放之后，把指向头的指针和指向尾的指针置空

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	//链表要遍历销毁结点，不能直接销毁
	QueueNode* cur = pq->head;
	while (cur)
	{
		//保存下一个结点
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}

1.3-队尾入数据

相当于尾插

==特殊情形：链表为空==(pq->head == NULL 或者 pq->tail == NULL)

此时，头指针和尾指针指向新结点

==普通情形：==

• 1.开辟新结点 newnode
• 2.尾指针和新结点进行链接 (pq->tail )
• 3.新结点成为尾

//队尾入数据
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//相当于尾插
	
	//构建新结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->next = NULL;
	newnode->data = x;
	//情况1：链表为空
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}

	//情况2：
	//tail newnode 
	else
	{
		pq->tail->next = newnode; //尾插
	//注意如果一开始没有数据，pq->tail = NULL，此时会出错，相当于对空指针解引用
	//所以没有数据时需要单独判断
		pq->tail = newnode;//指向新的尾
	}	
}

1.4-队头出数据

注意：要保证链表中还有数据（链表不为空）->即pq->head != NULL

队头出数据：

• 先保存头结点的下一个结点，记为next结点
• 释放头结点，然后head指向next结点

==注意点：删除最后一个结点时==

//队头出数据
void QueuePop(Queue* pq)
{
	assert(pq);
	//情况1：链表为空
	/*if (pq->head == NULL)
	{
		return -1;
	}*/
	assert(!QueueEmpty(pq));

	//情况2
	QueueNode* next = pq->head->next;//保存下一个结点
	free(pq->head);//释放队头
	pq->head = next;//next成为新的队头

	//注意！！！！如果一直删，删最后一个时候 此时next为NULL的,如果不把tail也置空，就会造成野指针
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

1.5-取队头数据

注意：要保证链表有数据

返回头指针指向结点的数据

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//链表为空
	/*if (pq->head == NULL)
	{
		return -1;
	}*/
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

1.6-取队尾数据

注意：要保证链表有数据

返回尾指针指向结点的数据

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

1.7-队列的长度

方法1：遍历链表进行统计

方法2：在定义结构体时，添加一个size变量

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
    int size ;//计算队列长度
}QueueNode;

后序我们插入数据：size++

出数据：size –

这样size标志的就是队列的长度

//队列的长度
int QueueSize(Queue* pq)
{
	assert(pq);
	//方法1：遍历统计
	//方法2：定义结构体时添加一个size变量，入数据：size++ 出数据size -- 用size标志队列长度

	//遍历统计
	QueueNode* cur = pq->head;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

1.8-判断队列是否为空

如果头指针或者尾指针为空->说明链表为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	/*if (pq -> head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return pq->head == NULL;
}