队列基本操作- 校招VIP

转载声明：文章来源 https://blog.csdn.net/zhang21722668/article/details/82155301

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

2.顺序队列
（1）队头不动，出队列时队头后的所有元素向前移动

缺陷：操作是如果出队列比较多，要搬移大量元素。

（2）队头移动，出队列时队头向后移动一个位置

如果还有新元素进行入队列容易造成假溢出。

假溢出：顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。
真溢出：顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。
3.循环队列

循环队列如何进行判空和满操作：

少用一个存储单元
设置一个标记flag；
初始值 flag = 0；入队列：flag = 1；出队列：flag = 0；
队列为空时：（front == rear && flag == 0）
队列为满时：（front == rear && flag == 1）
设置一个计数器
4.链式队列
链式队列：特殊的单链表，只在单链表上进行头删尾插的操作
***【1.定义一个队列结构体】***】

由于是链式队列，所以先定义一个存放数据域和指针域的结构体
队列结构体中定义一个队头指针和队尾指针

typedef int QElemType;
//typedef struct BTNode* QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode *_pNext;
}QNode;

typedef struct LQueue
{
	QNode *pFront;
	QNode *pRear;
}LQueue;

【2.创建新结点】

//创建新结点
static QNode *BuyLQNode(QElemType data)
{
	QNode *pLQNode = (QNode *)malloc(sizeof(QNode));
	if (NULL == pLQNode)
	{
		printf("申请空间失败!\n");
		assert(pLQNode);
	}
	pLQNode->data = data;
	pLQNode->_pNext = NULL;

	return pLQNode;
}

【3.初始化队列】

让队列的队头，队尾分别指向空

void LQueueInit(LQueue *q)
{
	assert(q);
	q->pFront = q->pRear = NULL;
}

【4.入队列】

判断队中是否有元素
找到队尾元素
让新入队的元素链在原先队列的队尾上，更新新的队尾

void LQueuePush(LQueue *q, QElemType data)
{
	assert(q);
	if (NULL == q->pFront)
	{
		q->pFront = q->pRear = BuyLQNode(data);
		return;
	}
	q->pRear->_pNext = BuyLQNode(data);
	q->pRear = q->pRear->_pNext;
}

【5.出队列】

这里的出队列采用是让队头元素不断后移，刷新队头元素，这样优化时间效率

void LQueuePop(LQueue *q)
{
	assert(q);
	QNode *pDel;
	if (NULL == q->pFront)
	{
		return;
	}

	if (q->pFront == q->pRear)
	{
		q->pRear = NULL;
	}

	pDel = q->pFront;
	q->pFront = q->pFront->_pNext;
	free(pDel);
}

【6.返回队头元素】

直接返回队头元素

QElemType LQueueTop(LQueue *q)
{
	assert(q);
	return q->pFront->data;
}

【7.返回队尾元素】

直接返回队尾元素

QElemType LQueueBack(LQueue *q)
{
	assert(q);
	return q->pRear->data;
}

【8.计算队列长度】

定义一个变量count
将队列从头到尾遍历，每访问一个元素count加1一下
最后count的值就是队列长度

int LQueueSize(LQueue *q)
{
	int count = 0;
	QNode *pCur;
	assert(q);
	pCur = q->pFront;
	while (pCur)
	{
		pCur = pCur->_pNext;
		count++;
	}
	return count;
}

【9.队列判空操作】

int LQueueEmpty(LQueue *q)
{
	return NULL == q->pFront;
}

5.完整代码块

/*****************************************/
//LQueue.h

typedef int QElemType;
//typedef struct BTNode* QElemType;
typedef struct QNode
{
	QElemType data;
	struct QNode *_pNext;
}QNode;

typedef struct LQueue
{
	QNode *pFront;
	QNode *pRear;
}LQueue;


//初始化
void LQueueInit(LQueue *q);

//入队列
void LQueuePush(LQueue *q, QElemType data);

//出队列
void LQueuePop(LQueue *q);

//返回队头元素
QElemType LQueueTop(LQueue *q);

//返回返回队列长度
int LQueueSize(LQueue *q);

//队列是否为空
int LQueueEmpty(LQueue *q);


/************************************************/
//LQueue.c

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

//创建新结点
static QNode *BuyLQNode(QElemType data)
{
	QNode *pLQNode = (QNode *)malloc(sizeof(QNode));
	if (NULL == pLQNode)
	{
		printf("申请空间失败!\n");
		assert(pLQNode);
	}
	pLQNode->data = data;
	pLQNode->_pNext = NULL;

	return pLQNode;
}

//初始化
void LQueueInit(LQueue *q)
{
	assert(q);
	q->pFront = q->pRear = NULL;
}

//入队列
void LQueuePush(LQueue *q, QElemType data)
{
	assert(q);
	if (NULL == q->pFront)
	{
		q->pFront = q->pRear = BuyLQNode(data);
		return;
	}
	q->pRear->_pNext = BuyLQNode(data);
	q->pRear = q->pRear->_pNext;
}

//出队列
void LQueuePop(LQueue *q)
{
	assert(q);
	QNode *pDel;
	if (NULL == q->pFront)
	{
		return;
	}

	if (q->pFront == q->pRear)
	{
		q->pRear = NULL;
	}

	pDel = q->pFront;
	q->pFront = q->pFront->_pNext;
	free(pDel);
}

//返回队头元素
QElemType LQueueTop(LQueue *q)
{
	assert(q);
	return q->pFront->data;
}

//返回队尾元素
QElemType LQueueBack(LQueue *q)
{
	assert(q);
	return q->pRear->data;
}

//返回返回队列长度
int LQueueSize(LQueue *q)
{
	int count = 0;
	QNode *pCur;
	assert(q);
	pCur = q->pFront;
	while (pCur)
	{
		pCur = pCur->_pNext;
		count++;
	}
	return count;
}

//队列是否为空
int LQueueEmpty(LQueue *q)
{
	return NULL == q->pFront;
}