《详解链式队列：原理、操作与销毁方法》

目录

一. 队列的概念

二. 链式队列的结构组成

三. 链式队列的基本操作

1.初始化队列（创建空队列）

2. 入队操作（Enqueue）

3. 出队操作（Dequeue）

4. 取队头元素（GetFront）

5. 取队尾元素（GetEver）

6. 判空操作（IsEmpty）

7. 销毁队列（DestroyQueue）

一. 队列的概念

队列（Queue）是一种常见的线性数据结构，其核心特点是遵循 “先进先出”（First In First Out，FIFO）的原则，即最早进入队列的元素最先被取出，类似于日常生活中排队的场景。

 队列的物理结构（存储实现）

队列的物理实现通常有两种方式：顺序存储（数组）和链式存储（链表）。

下面我们将主要介绍链式存储的队列  因为数组会导致先进先出时数组的集体前移 复杂度为O(n)

而链式存储先进先出时只需要改变头指针的位置 以及释放头指针的内存即可 易于实现

二. 链式队列的结构组成

链式队列通常由节点和队头 / 队尾指针组成：

节点结构：
每个节点包含两部分：

• 数据域：存储元素的值。
• 指针域：指向后一个节点（形成链式关系）。

节点的结构定义（以 C 语言为例）：

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

队列结构：
队列需要两个指针来管理：

• 队头指针（phead）：指向链表的头节点（即队头元素）。
• 队尾指针（ptail）：指向链表的尾节点（即队尾元素）。

队列的结构定义：

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

空队列状态

当队列为空时，phead和ptail均为NULL（无节点）。

三. 链式队列的基本操作

1.初始化队列（创建空队列）

• 操作：将队头和队尾指针均置为NULL。
• 代码示例：

  void InitQueue(LinkQueue* q) {
      q->phead = q->ptail = NULL;  // 空队列
  }
  

2. 入队操作（Enqueue）

• 操作：在队尾插入新元素，步骤如下：
  1. 创建新节点并赋值。
  2. 若队列为空（front和rear均为NULL），则新节点既是队头也是队尾（phead = ptail = 新节点）。
  3. 若队列非空，将新节点链接到当前队尾节点的后面，再更新rear指向新节点。
• 代码示例：

  //入队
  void QueuePush(Queue* pq, QDataType x)
  {
  	assert(pq);
  	//申请新节点
  	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
  	if (newcode == NULL)
  	{
  		perror("malloc fail!");
  		exit(1);
  	}
  	newcode->data = x;
  	newcode->next = NULL;
   
  	//如果队列为空
  	if (pq->phead == NULL)
  	{
  		pq->phead = pq->ptail = newcode;
  		//pq->size++;
  	}
  	else
  	{
  		pq->ptail->next = newcode;
  		pq->ptail = pq->ptail->next;
  		//pq->size++;
  	}
  }

3. 出队操作（Dequeue）

• 操作：从队头删除元素，步骤如下：
  1. 若队列为空（phead == NULL），出队失败（可返回错误信息）。
  2. 保存队头节点的地址（用于释放内存）。
  3. 若队列只有一个节点（phead == ptail），删除后队列变为空（phead = ptail = NULL）。
  4. 若队列有多个节点，更新phead指向后一个节点。
  5. 释放被删除节点的内存。
• 代码示例：

  //出队
  void QueuePop(Queue* pq)
  {
  	assert(!QueueEmpty(pq));
  	//如果队伍中只有一个节点
  	if (pq->phead == pq->ptail)
  	{
  		free(pq->phead);
  		pq->phead = pq->ptail = NULL;
  		//pq->size--||pq->size=0
  	}
  	else
  	{
  		QueueNode* next = pq->phead->next;
  		free(pq->phead);
  		pq->phead = next;
  		//pq->size--;
  	}
  }

4. 取队头元素（GetFront）

• 操作：返回队头元素的值（不删除节点）。
• 代码示例：

  //取队首数据
  QDataType QueueHead(Queue* pq)
  {
  	assert(!QueueEmpty(pq));
  	return pq->phead->data;
  }

5. 取队尾元素（GetEver）

操作：返回队尾元素的值（不删除节点）。

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

6. 判空操作（IsEmpty）

• 操作：判断队列是否为空（phead== NULL 即为空）。
• 代码示例：

  //队列判空
  bool QueueEmpty(Queue* pq)
  {
  	assert(pq);
  	return pq->phead == NULL;
  }

7. 销毁队列（DestroyQueue）

• 操作：释放所有节点的内存，将队列重置为空。
• 代码示例：

  //队列的销毁
  void QueueDestory(Queue* pq)
  {
  	assert(pq);
  	QueueNode* pcur = pq->phead;
  	while (pcur)
  	{
  		QueueNode* next = pcur->next;
  		free(pcur);
  		pcur = next;
  	}
  	pq->phead = pq->ptail = NULL;
  }

总结:

本文介绍了链式队列的基本概念和实现方法。链式队列采用链表结构存储，避免了数组实现时元素移动的开销，具有O(1)时间复杂度的入队和出队操作。文章详细说明了链式队列的结构组成，包括节点定义和队列管理指针（头指针和尾指针），并提供了完整的C语言实现代码，涵盖初始化、入队、出队、取队头/队尾元素、判空和销毁等基本操作。通过链式存储方式，队列可以高效地实现先进先出(FIFO)的特性。