数据结构——队列-EW帮帮网

1. 概念与结构

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，即最先被插入队列的数据会最先被删除。队列广泛应用于计算机科学中，特别是在任务调度、缓冲区管理、网络数据传输等领域。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2. 队列的底层结构分析

使用数组以及队列来实现队列的对比

1. 数组实现队列的基本原理

使用数组来实现队列时，可以借用一个固定大小的数组，维护两个指针：front 和 rear。

front：指向队列的头部，表示第一个元素。
rear：指向队列的尾部，表示下一个插入元素的位置。

当队列为空时，front == rear，而当队列满时，rear 达到数组的末尾。

Array: [  1,  2,  3,  4,  5]
Front: 0, Rear: 5 (Queue is full)

2. 链表实现队列的基本原理

使用链表实现队列时，我们可以通过 头指针（front） 和 尾指针（rear） 来维护队列。

front：指向队列的头部（即第一个元素）。
rear：指向队列的尾部（即最后一个元素）。

链表的每个节点包含数据部分和指向下一个节点的指针。队列的入队操作将元素添加到链表的尾部，出队操作从链表的头部移除元素。

Head → [Data|Next] → [Data|Next] → [Data|Next] → NULL
Front →      ↑
Rear  →  指向尾部

3. 数组队列与链表队列的对比

4.对比数组队列和链表队列的时间复杂度

总结

数组实现队列：

适用于队列大小已知或变化不大的情况，尤其在内存空间有限的情况下，简单且高效。但如果队列频繁增长，或者存在大量空间浪费，则不适合。
常见操作的时间复杂度为 O(1)，但在扩容时会有 O(n) 的时间复杂度，因为需要重新分配和复制数组。

链表实现队列：

适用于队列大小动态变化的场景，链表不需要预先分配大小，不会发生空间浪费，插入和删除操作高效。但链表实现需要更多的内存用于存储指针，操作也相对复杂。
常见操作的时间复杂度都是 O(1)，不涉及扩容问题，因此性能在这些操作上更加稳定。

综上使用链表来实现队列

3. 队列的实现

//定义结点的结构
typedef int QDataTpe;
typedef struct QueueNode
{
	QDataTpe data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;//记录有效数据个数
}Queue;

3.1 入队列

1. 创建新节点

每当我们将一个新的元素加入队列时，需要首先创建一个新的节点。这个节点会存储数据并且需要指向链表中的下一个节点。
需要分配内存来存储新节点，并将其 data 字段设置为要入队的数据，next 字段设置为 NULL（因为它是当前链表的最后一个节点）。

2. 检查队列是否为空

在进行入队操作之前，我们需要检查队列是否为空。队列为空时，新节点将成为队列的唯一元素，它既是头部节点也是尾部节点。
如果队列不为空，新节点将被添加到队列的尾部。

3. 将新节点添加到队列尾部

如果队列为空，直接将新节点赋给队列的 pq->phead 和 pq->ptail（即头指针和尾指针都指向新节点）。
如果队列不为空：
- 更新当前队列尾部节点的 next 指针，指向新节点。
- 更新队列的 pq->ptail 指针，指向新的尾部节点（新加入的节点）。

4. 确保尾指针正确更新

入队后，新的节点成为队列的尾部，因此需要更新队列的 pq->ptail 指针，确保它指向新的尾部节点。

//入队---队尾
void QueuePush(Queue* pq, QDataTpe x)
{
	assert(pq);
	//newnode
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空，newnode是队头也是队尾
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		//队列非空，直接插入到队尾
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

3.2 出队列

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == 0;
}

pq->phead == 0：这部分代码在检查 phead 是否为空。0 在 C 语言中等价于 NULL，即表示指针没有指向任何有效的内存地址。

如果 phead 为 NULL，意味着队列为空，函数将返回 true（队列为空）。
如果 phead 不为 NULL，说明队列中至少有一个元素，函数将返回 false（队列非空）。

步骤说明：

假设我们有一个队列 Queue，它是通过链表实现的，其中 phead 指向队列的头部，ptail 指向队列的尾部。每个节点包含数据和指向下一个节点的指针。

1. 检查队列是否为空：

在进行出队操作之前，我们需要检查队列是否为空。如果队列为空，则不能出队，因为没有元素可供删除。

2. 保存头部元素的数据：

我们需要保存 phead 指针指向的元素数据，因为在删除节点时，我们将失去对该数据的引用。如果要返回出队的元素数据，必须先保存它。

3. 更新 phead 指针：

将 phead指向队列的下一个节点，即 phead = phead->next。这样，队列头部的元素就被“删除”了。phead 指针现在指向新的队头元素。

4. 处理队列为空的情况：

如果 phead 变为 NULL，即队列中没有元素时，需要将 ptail 指针也设置为 NULL，因为队列为空时，phead 和 ptail 都应该为 NULL。

5. 释放已删除节点的内存：

如果我们使用动态内存分配（例如 malloc），需要释放 phead 指向的节点的内存，以避免内存泄漏。

//出队---队头
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//只有一个结点的情况
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

3.3 取队头数据

在确定队列不为空的情况下，取队头数据非常简单。

检查队列是否为空：
在访问队头元素之前，我们需要检查队列是否为空。如果队列为空（即 phead == NULL），表示没有元素可以访问，此时应返回一个错误信息或者错误值。
访问队头数据：
如果队列不为空，可以直接访问 phead 节点的数据。队列的头部数据就是 phead->data。
返回队头数据：
返回 phead 节点中的数据，这个数据是队列头部的元素，且队列结构不发生变化。

//取队头数据
QDataTpe QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

3.4 取队尾数据

检查队列是否为空：
在访问队尾元素之前，我们需要检查队列是否为空。如果队列为空（即 ptail == NULL），表示没有元素可以访问，此时应返回一个错误信息或者错误值。
访问队尾数据：
如果队列不为空，可以直接访问 rear 节点的数据。队列的尾部数据就是 ptail->data。
返回队尾数据：
返回 ptail 节点中的数据，这个数据是队列尾部的元素，且队列结构不发生变化。

QDataTpe QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

3.5 队列有效元素个数

通常情况下，使用计数器（方法一）更加高效，即在每次入队列和出队列时，都会对pq->size进行改变，在入队列时则 pq->size++，在出队列时则 pq->size--。

这使我们可以直接得出队列的有效元素个数，避免了遍历链表（这种方法在计算队列大小时需要遍历整个链表，因此时间复杂度是 O(n)。在每次查询时，性能较差）。

//队列有效元素个数
int QueueSize(Queue* pq)
{
	return pq->size;
}

完整代码：

Queue.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义结点的结构
typedef int QDataTpe;
typedef struct QueueNode
{
	QDataTpe data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;//记录有效数据个数
}Queue;

void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);

//入队---队尾
void QueuePush(Queue* pq, QDataTpe x);
//出队---队头
void QueuePop(Queue* pq);

//取队头数据
QDataTpe QueueFront(Queue* pq);
//取队尾数据
QDataTpe QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

Queue.c：

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}
//入队---队尾
void QueuePush(Queue* pq, QDataTpe x)
{
	assert(pq);
	//newnode
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空，newnode是队头也是队尾
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		//队列非空，直接插入到队尾
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == 0;
}
//出队---队头
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//只有一个结点的情况
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}
//取队头数据
QDataTpe QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
//取队尾数据
QDataTpe QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq)
{
    return pq->size;
}

以上为队列结构的介绍，感谢敢看！

数据结构——队列