【链式队列的实现】

标签：结点队列 next 实现链式 front 指针

1.链式队列与循环顺序队的比较

1.1链式队列

优点

动态扩展：

不需要预先分配固定的存储空间，内存使用灵活，不会因为队列满而导致溢出。

插入和删除操作简单：

在链式队列中，插入和删除操作只需调整指针，无需移动数据，时间复杂度为O(1)。

无容量限制：

只要系统有足够的内存，链式队列可以容纳任意数量的元素。

缺点

额外内存消耗：

每个元素需要额外存储指针，导致内存开销增加。

实现复杂度高：

需要处理指针的管理，容易出现难以发现的错误，特别是在多线程环境下更为复杂。

缓存性能差：

由于链表的元素在内存中可能是不连续存储的，因此缓存命中率低，访问速度可能较慢。

1.2环顺序队列

优点

内存使用紧凑：

循环顺序队列在预先分配好的固定内存空间中进行操作，无需额外的指针存储空间，内存开销较小。

缓存性能好：

元素存储在连续的内存空间中，这样能够提高缓存命中率，访问速度较快。

实现简单：

循环顺序队列的实现相对简单，不需要处理复杂的指针操作，尤其是在单线程环境下，管理更容易。

缺点

固定容量：

循环顺序队列需要预先指定容量，如果容量不足可能会导致队列溢出，容量过大会浪费内存。

插入删除操作效率稍低：

尽管循环顺序队列的插入和删除操作复杂度也是O(1)，但在环绕操作时需要计算位置，可能影响操作效率。

难以扩展：

如果需要增加队列的容量，必须重新分配更大的内存并迁移数据，这个过程复杂且耗时。

1.3小结

链式队列适合需要动态扩展、且对内存消耗不敏感的场景，适用于元素数量不可预知或频繁变化的情况。
循环顺序队列则适合对内存有严格限制、且元素数量相对固定的场景，适用于内存紧张的环境中，且能有效利用缓存提高访问速度。

2.链式队列的整队创建（包含头结点，头尾指针）

2.1链式队列的结构类型定义

在这里插入图片描述
一个完整的链式队列包含头指针，尾指针，头结点，一般结点这四个部分

//<1>队列结点结构定义
typedef struct QNode
{
	QElemType data;//队结点数据域,用来存储队列元素
	struct QNode* next;//队结点指针域，用来指向下一个队结点
}QNode, *QNodePtr;
//QNode: 链队列结点类型,用来定义队结点
//QNodePtr: 链队列结点指针类型，用来定义队结点指针

//<2>队列链式定义
typedef struct
{
	QNodePtr front, rear;//定义链队的头指针，尾指针
}LinkQueue;
//LinkQueue:通过LinkQueue定义链队列；通过 定义出的链队列 访问队列的头指针，尾指针

2.1.1链式队列的基本操作图解

在这里插入图片描述

2.2.链队列的初始化

注意：传入链队列类型的指针，因为初始化时要修改链队列类型中的头尾指针

bool InitQueue(LinkQueue * q)

2.2.1算法步骤

（1）创建头结点并将头尾指针指向头结点
（2）初始化链式队列头结点的指针域

在这里插入图片描述
初始化完成后的空队如上图

//1.链队列的初始化
//注意：传入链队列类型的指针，因为初始化时要修改 链队列类型中 的头尾指针
bool InitQueue(LinkQueue * q)
{
	//[1]创建头结点 并 将头尾指针指向头结点
	q->front = q->rear = (QNodePtr)malloc(sizeof(QNode));

	if (!q->front)
	{
		return false;//内存分配失败
	}

	//[2]初始化链式队列头结点的指针域
	q->front->next = NULL;

	return true;
}

2.3求链队列的长度

注意：不传入链队列类型的指针，因为求长度时只访问链队列类型中的头指针

int QueueLength(LinkQueue q)

2.3.1算法步骤

（1）定义并初始化临时指针p指向首元结点
（2）定义并初始化计数器为0(因为没有排除空队的情况)
（3）循环记录链式队的结点个数

本质就是单链表求长度的操作

//2.求链队列的长度
//本质为带头结点的单链表的求长度操作
//注意：不传入链队列类型的指针，因为求长度时只访问 链队列类型中 的头指针
int QueueLength(LinkQueue q)
{
	//[0]判断链式队列是否存在
	if (q.front == NULL)
	{
		return 0;//链式队列不存在
	}

	//[1]定义并初始化临时指针p指向首元结点
	QNodePtr p = q.front->next;

	//[2]定义并初始化计数器为0(因为没有排除空队的情况)
	int count = 0;

	//[3]循环记录链式队的结点个数
	while (p!=NULL)
	{
		count++;

		p = p->next;
	}

	return count;
}

2.4链队列的入队（核心1）

注意：传入链队列类型的指针，因为入队时要修改链队列类型中的尾指针

bool EnQueue(LinkQueue* q, QElemType e)

2.4.1算法步骤

（1）创建并初始化新结点s
<1>初始化新结点的数据域
<2>初始化新结点的指针域为NULL
（2）将新结点插入到队尾并更新尾指针

本质就是带头结点的单链表的尾插法操作(注意尾指针的更新)
在这里插入图片描述
（1）

（2）

//3.链队列的入队
//本质为带头结点的单链表的尾插法操作(注意尾指针的更新)
//注意：传入链队列类型的指针，因为入队时要修改 链队列类型中 的尾指针
bool EnQueue(LinkQueue* q, QElemType e)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return false;
	}

	//[1]创建并初始化新结点s
	QNodePtr s = (QNodePtr)malloc(sizeof(QNode));
	
	if (!s)
	{
		return false;//内存分配失败
	}
	//<1>初始化新结点的数据域
	s->data = e;
	//<2>初始化新结点的指针域为NULL
	s->next = NULL;
	
	//[2]将新结点插入到队尾并更新尾指针
	q->rear->next = s;

	q->rear = s;

	return true;
}

2.5链队列的出队（核心2）

注意：传入链队列类型的指针，因为出队时要修改链队列类型中的头指针

bool DeQueue(LinkQueue* q, QElemType* e)

2.5.1算法步骤

（1）排除链式队列不存在以及为空队的情况
（2）定义临时指针p指向待删除的首元结点
（3）弹出首元结点的数据
（4）更新头结点next域的指向
（5）注意链式队列中只存在一个结点时，需要更新尾指针（尾指针指向头结点）
（6）销毁待删除首元结点空间

本质为带头结点的单链表的删除首元结点操作（注意尾指针的更新）
在这里插入图片描述
（2）

（4）

（6）

//4.链队列的出队
//本质为带头结点的单链表的删除首元结点操作（注意尾指针的更新）
//注意：传入链队列类型的指针，因为出队时要修改 链队列类型中 的头指针
bool DeQueue(LinkQueue* q, QElemType* e)
{
	//[1]排除链式队列不存在 以及 为空队 的情况
	if (q->front == NULL||q->front == q->rear)
	{
		return false;
	}

	//[2]定义临时指针p指向待删除的首元结点
	QNodePtr p = q->front->next;

	//[3]弹出首元结点的数据
	*e = p->data;

	//[4]更新头结点next域的指向
	q->front->next = p->next;

	//[5]注意链式队列中只存在一个结点时，需要更新尾指针（尾指针指向头结点）
	if (q->rear == p)
	{
		q->rear = q->front;
	}

	//[6]销毁待删除首元结点空间
	free(p);

	return true;
}

2.6链队列的求队头元素

注意：不用传入链队列类型的指针，因为取队头元素时要不修改链队列类型中的头尾指针

bool GetHead(LinkQueue q,QElemType *e)

2.6.1算法步骤

（1）排除链式队列不存在以及为空队的情况
（2）直接弹出首元结点的数据（即头结点next域结点空间中的数据）

在这里插入图片描述
空队时没有队头元素

//5.链队列的求队头元素
//注意：不用传入链队列类型的指针，因为取队头元素时要不修改 链队列类型中 的头尾指针
bool GetHead(LinkQueue q,QElemType *e)
{
	//[1]排除链式队列不存在 以及 为空队 的情况
	if (q.front == NULL || q.front == q.rear)
	{
		return false;
	}

	//[2]直接弹出首元结点的数据
	*e = q.front->next->data;
	return true;
}

2.7链队列的清空

注意：传入链队列类型的指针,因为释放完队中除头结点外所有空间后，需要重置链队列类型中的头尾指针

bool ClearQueue(LinkQueue* q)

2.7.1算法步骤

（1）定义两个临时指针n和m，
n指向待删除结点
m指向待删除结点的下一个结点
（2）初始化临时指针n指向首元结点
（3）循环删除除头结点以外的所有结点
与单链表一致（这里不能写(m!=NULL),因为在这条语句之前m并未初始化（是一个野指针）
<1>m 记录下一个结点
<2>释放当前结点
<3>n 移动到待删除结点
（4）注意清空完毕后保持空队的状态
将尾指针指向头结点（队空的标志）
确保 front->next 为空（保证头结点next域正确）

//6.链队列的清空
//本质为带头结点的单链表的清空操作（注意尾指针的更新）
bool ClearQueue(LinkQueue* q)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return false;//若不存在,则无法清空
	}

	//[1]定义两个临时指针n和m，
	// n指向待删除结点
	// m指向待删除结点的下一个结点
	QNodePtr n, m;
	
	//[2]初始化临时指针n指向首元结点
	n = q->front->next;

	//[3]循环删除除头结点以外的所有结点
	while (n != NULL) //与单链表一致（这里不能写(m!=NULL),因为在这条语句之前m并未初始化（是一个野指针）
	{
		m = n->next;// m 记录下一个结点

		free(n);//释放当前结点

		n = m;// n 移动到待删除结点
	}

	//[4]注意清空完毕后保持空队的状态
	q->rear = q->front;// 将尾指针指向头结点
	q->front->next = NULL;// 确保 front->next 为空
	return true;
}

2.8链队列的销毁

注意：传入链队列类型的指针,因为释放完队中所有空间后，需要置空链队列类型中的头尾指针

bool DestroyQueue(LinkQueue* q)

2.8.1算法步骤

（1）定义销毁指针p（作用：销毁待删除结点）
（2）循环删除链式队列中所有结点
<1> 头指针记录待删除结点的下一个结点
<2>释放当前待删除结点
<3> 将p指针指向下一个待删除结点
（3）销毁完毕后，置空链式队列的头尾指针

本方法即单链表的销毁操作，但是要注意销毁完毕后置空头尾指针，避免悬挂指针问题
还有一种方法，即p作为记录指针使用，用来记录待删除结点的下一个结点，这里不过多赘述，详见所有操作汇总

//7.0链队列的销毁(法一，定义临时销毁指针)
//注意：传入链队列类型的指针,因为释放完队中所有空间后，需要置空 链队列类型中 的头尾指针
bool DestroyQueue(LinkQueue* q)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return true;//若不存在，直接返回成功
	}

	//[1]定义销毁指针p（作用：销毁待删除结点）
	QNodePtr p=q->front;

	//[2]循环删除链式队列中所有结点
	while (p!= NULL)
	{
		q->front = p->next;//头指针记录待删除结点的下一个结点

		free(p);//释放当前待删除结点

		p = q->front;//将p指针指向下一个待删除结点
	}

	//[3]销毁完毕后，置空链式队列的头尾指针
	q->front = q->rear = NULL;
	return true;
}

2.9链队列的打印（从队头开始打印）

注意：不用传入链队列类型的指针,只进行访问操作，不进行修改操作

bool PrintQueue(LinkQueue q)

2.9.1算法步骤

（1）排除队列为空队的情况
（2）定义临时指针p指向首元结点
（3）循环打印链式队列中的元素

//8.链队列的打印（从队头开始打印）
//注意：不用传入链队列类型的指针,只进行访问操作，不进行修改操作
bool PrintQueue(LinkQueue q)
{
	//[0]排除链式队列不存在 
	if (q.front == NULL )
	{
		return false;
	}

	//[1]排除队列 为空队 的情况
	if (q.front == q.rear)
	{
		printf("空队！\n");
		return false;
	}
	//[2]定义临时指针p指向首元结点
	QNodePtr p = q.front->next;

	//[3]循环打印链式队列中的元素
	while (p != NULL)
	{
		printf("%d ", p->data);

		p = p->next;
	}

	return true;
}

2.10所有操作汇总：

//链式队列的实现（带头结点的 操作受限的单链表；包含头尾指针）
#include<stdio.h>
#include<stdlib.h>


#define bool int
#define true 1
#define false 0


typedef int QElemType;//队列元素类型


//链队列的结构类型定义
//<1>队列结点结构定义
typedef struct QNode
{
	QElemType data;//队结点数据域,用来存储队列元素
	struct QNode* next;//队结点指针域，用来指向下一个队结点
}QNode, *QNodePtr;
//QNode: 链队列结点类型,用来定义队结点
//QNodePtr: 链队列结点指针类型，用来定义队结点指针



//<2>队列链式定义
typedef struct
{
	QNodePtr front, rear;//定义链队的头指针，尾指针
}LinkQueue;
//LinkQueue:通过LinkQueue定义链队列类型；通过 定义出的链队列类型 访问队列的头指针，尾指针


//1.链队列的初始化
//注意：传入链队列类型的指针，因为初始化时要修改 链队列类型中 的头尾指针
bool InitQueue(LinkQueue * q)
{
	//[1]创建头结点 并 将头尾指针指向头结点
	q->front = q->rear = (QNodePtr)malloc(sizeof(QNode));

	if (!q->front)
	{
		return false;//内存分配失败
	}

	//[2]初始化链式队列头结点的指针域
	q->front->next = NULL;

	return true;
}



//2.求链队列的长度
//本质为带头结点的单链表的求长度操作
//注意：不传入链队列类型的指针，因为求长度时只访问 链队列类型中 的头指针
int QueueLength(LinkQueue q)
{
	//[0]判断链式队列是否存在
	if (q.front == NULL)
	{
		return 0;//链式队列不存在
	}

	//[1]定义并初始化临时指针p指向首元结点
	QNodePtr p = q.front->next;

	//[2]定义并初始化计数器为0(因为没有排除空队的情况)
	int count = 0;

	//[3]循环记录链式队的结点个数
	while (p!=NULL)
	{
		count++;

		p = p->next;
	}

	return count;
}



//3.链队列的入队
//本质为带头结点的单链表的尾插法操作(注意尾指针的更新)
//注意：传入链队列类型的指针，因为入队时要修改 链队列类型中 的尾指针
bool EnQueue(LinkQueue* q, QElemType e)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return false;
	}

	//[1]创建并初始化新结点s
	QNodePtr s = (QNodePtr)malloc(sizeof(QNode));
	
	if (!s)
	{
		return false;//内存分配失败
	}
	//<1>初始化新结点的数据域
	s->data = e;
	//<2>初始化新结点的指针域为NULL
	s->next = NULL;
	
	//[2]将新结点插入到队尾并更新尾指针
	q->rear->next = s;

	q->rear = s;

	return true;
}


//4.链队列的出队
//本质为带头结点的单链表的删除首元结点操作（注意尾指针的更新）
//注意：传入链队列类型的指针，因为出队时要修改 链队列类型中 的头指针
bool DeQueue(LinkQueue* q, QElemType* e)
{
	//[1]排除链式队列不存在 以及 为空队 的情况
	if (q->front == NULL||q->front == q->rear)
	{
		return false;
	}

	//[2]定义临时指针p指向待删除的首元结点
	QNodePtr p = q->front->next;

	//[3]弹出首元结点的数据
	*e = p->data;

	//[4]更新头结点next域的指向
	q->front->next = p->next;

	//[5]注意链式队列中只存在一个结点时，需要更新尾指针（尾指针指向头结点）
	if (q->rear == p)
	{
		q->rear = q->front;
	}

	//[6]销毁待删除首元结点空间
	free(p);

	return true;
}




//5.链队列的求队头元素
//注意：不用传入链队列类型的指针，因为取队头元素时要不修改 链队列类型中 的头尾指针
bool GetHead(LinkQueue q,QElemType *e)
{
	//[1]排除链式队列不存在 以及 为空队 的情况
	if (q.front == NULL || q.front == q.rear)
	{
		return false;
	}

	//[2]直接弹出首元结点的数据
	*e = q.front->next->data;
	return true;
}




//6.链队列的清空
//本质为带头结点的单链表的清空操作（注意尾指针的更新）
bool ClearQueue(LinkQueue* q)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return false;//若不存在,则无法清空
	}

	//[1]定义两个临时指针n和m，
	// n指向待删除结点
	// m指向待删除结点的下一个结点
	QNodePtr n, m;
	
	//[2]初始化临时指针n指向首元结点
	n = q->front->next;

	//[3]循环删除除头结点以外的所有结点
	while (n != NULL) //与单链表一致（这里不能写(m!=NULL),因为在这条语句之前m并未初始化（是一个野指针）
	{
		m = n->next;// m 记录下一个结点

		free(n);//释放当前结点

		n = m;// n 移动到待删除结点
	}

	//[4]注意清空完毕后保持空队的状态
	q->rear = q->front;// 将尾指针指向头结点
	q->front->next = NULL;// 确保 front->next 为空
	return true;
}






//7.0链队列的销毁(法一，定义临时销毁指针)
//注意：传入链队列类型的指针,因为释放完队中所有空间后，需要置空 链队列类型中 的头尾指针
bool DestroyQueue(LinkQueue* q)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return true;//若不存在，直接返回成功
	}

	//[1]定义销毁指针p（作用：销毁待删除结点）
	QNodePtr p=q->front;

	//[2]循环删除链式队列中所有结点
	while (p!= NULL)
	{
		q->front = p->next;//头指针记录待删除结点的下一个结点

		free(p);//释放当前待删除结点

		p = q->front;//将p指针指向下一个待删除结点
	}

	//[3]销毁完毕后，置空链式队列的头尾指针
	q->front = q->rear = NULL;
	return true;
}


//7.1链队列的销毁(法二，定义临时记录指针)
//注意：传入链队列类型的指针,因为释放完队中所有空间后，需要置空 链队列类型中 的头尾指针
bool DestroyQueue1(LinkQueue* q)
{
	//[0]判断链式队列是否存在
	if (q->front == NULL)
	{
		return true;//若不存在，直接返回成功
	}

	//[1]定义记录指针p（作用：记录待删除结点下一个结点）
	QNodePtr p;

	//[2]循环删除链式队列中所有结点
	while (q->front != NULL)
	{
		p = q->front->next;//p记录待删除结点下一个结点

		free(q->front);//释放待删除结点

		q->front = p;//将头指针指向下一个待删除结点
	}

	//[3]销毁完毕后，置空链式队列的头尾指针
	q->front = q->rear = NULL;
	return true;
}


//8.链队列的打印（从队头开始打印）
//注意：不用传入链队列类型的指针,只进行访问操作，不进行修改操作
bool PrintQueue(LinkQueue q)
{
	//[0]排除链式队列不存在 
	if (q.front == NULL )
	{
		return false;
	}

	//[1]排除队列 为空队 的情况
	if (q.front == q.rear)
	{
		printf("空队！\n");
		return false;
	}
	//[2]定义临时指针p指向首元结点
	QNodePtr p = q.front->next;

	//[3]循环打印链式队列中的元素
	while (p != NULL)
	{
		printf("%d ", p->data);

		p = p->next;
	}

	return true;
}


// 测试代码
int main() 
{
	LinkQueue q;//定义链式队列q
	QElemType e;

	// 初始化队列
	if (InitQueue(&q)) 
	{
		printf("链式队列初始化成功。\n");
	}

	// 入队
	for (int i = 1; i <= 5; i++) 
	{
		EnQueue(&q, i);
	}
	printf("输出入队后的元素: ");
	PrintQueue(q);

	// 获取队头元素
	if (GetHead(q, &e)) 
	{
		printf("队头元素：%d\n", e);
	}

	// 出队
	if (DeQueue(&q, &e)) 
	{
		printf("出队元素: %d\n", e);
	}
	printf("出队后的队列元素: ");
	PrintQueue(q);

	// 队列长度
	printf("队列长度: %d\n", QueueLength(q));

	// 清空队列
	if (ClearQueue(&q)) 
	{
		printf("队列清空成功！\n");
	}

	// 再次打印队列
	printf("清空后的队列: ");
	PrintQueue(q);


	// 销毁队列
	if (DestroyQueue(&q)) 
	{
		printf("队列销毁成功！\n");
	}

	return 0;
}

在这里插入图片描述

标签：结点,队列,next,实现,链式,front,指针
From： https://blog.csdn.net/2401_82676816/article/details/141750079

1.链式队列与循环顺序队的比较

1.1链式队列

1.2环顺序队列

1.3小结

2.链式队列的整队创建（包含头结点，头尾指针）

2.1链式队列的结构类型定义

2.1.1链式队列的基本操作图解

2.2.链队列的初始化

2.2.1算法步骤

2.3求链队列的长度

2.3.1算法步骤

2.4链队列的入队（核心1）

2.4.1算法步骤

2.5链队列的出队（核心2）

2.5.1算法步骤

2.6链队列的求队头元素

2.6.1算法步骤

2.7链队列的清空

2.7.1算法步骤

2.8链队列的销毁

2.8.1算法步骤

2.9链队列的打印（从队头开始打印）

2.9.1算法步骤

2.10所有操作汇总：

相关文章

赞助商

阅读排行

【链式队列的实现】

1.链式队列 与 循环顺序队的比较

1.1链式队列

1.2环顺序队列

1.3小结

2.链式队列的整队创建（包含头结点，头尾指针）

2.1链式队列的结构类型定义

2.1.1链式队列的基本操作图解

2.2.链队列的初始化

2.2.1算法步骤

2.3求链队列的长度

2.3.1算法步骤

2.4链队列的入队（核心1）

2.4.1算法步骤

2.5链队列的出队（核心2）

2.5.1算法步骤

2.6链队列的求队头元素

2.6.1算法步骤

2.7链队列的清空

2.7.1算法步骤

2.8链队列的销毁

2.8.1算法步骤

2.9链队列的打印（从队头开始打印）

2.9.1算法步骤

2.10所有操作汇总：

相关文章

赞助商

阅读排行

1.链式队列与循环顺序队的比较