[数据结构——lesson7.队列]-EW帮帮网

队列（Queue）是一种常见的线性数据结构，其核心特点是遵循 “先进先出”（First In, First Out，简称 FIFO）的原则，它只允许在队列的一端（队尾）进行插入（enqueue）操作，而在另一端（队头）进行删除（dequeue）操作，即最早进入队列的元素会最先被取出，类似于日常生活中排队的场景。

1.1队列的基本概念

队头（Front）：队头是指队列中允许删除操作的一端。也就是说，队列中的元素将按照它们被添加到队列中的顺序，从队头开始被逐一移除。

队尾（Rear）：队尾是指队列中允许插入操作的一端。新元素将被添加到队尾，以保持队列的先进先出（FIFO）特性。

入队（Enqueue）：在队尾插入元素的操作。

出队（Dequeue）：从队头删除元素的操作。

空队列：没有任何元素的队列。

队列的图示：

1.2队列的结构

队列的结构可以通过两种方式实现：顺序结构（数组） 和 链式结构（链表）。

1. 链式队列（基于链表）

使用链表存储队列元素，通常需要两个指针：

front：指向队头节点（首节点）。

rear：指向队尾节点（尾节点）。

初始时，front = rear = null（空队列）。

入队：创建新节点，若队列为空，则front和rear均指向新节点；否则，rear的next指向新节点，再更新rear为新节点。

出队：取出front节点的值，将front更新为front.next；若出队后队列为空，则rear也置为null。

如下图：

优势：链式队列无需预先指定容量，避免了溢出问题，适合元素数量不确定的场景。

2. 顺序队列（基于数组）

使用数组存储队列元素，需要两个指针（或索引）分别标记队头（front）和队尾（rear）：

初始时，front = rear = 0（空队列）。

入队：将元素放入rear指向的位置，然后rear向后移动（rear++）。

出队：取出front指向的元素，然后front向后移动（front++）。

问题与优化：
普通顺序队列会出现 “假溢出” 问题（即数组未填满，但rear已达到数组末尾）。解决方法是采用 循环队列：

将数组视为环形，rear和front超出数组长度时，通过取模运算（%）回到起始位置。

循环队列中，通常预留一个位置（不存储元素）来区分 “队满” 和 “队空”：

队空：front == rear

队满：(rear + 1) % maxSize == front

如下图：

2.队列的功能

1.队列的初始化。

2.判断队列是否为空。

3.判断队列是否已满。

4.返回队头元素。

5.返回队尾元素

6.返回队列的大小。

7.元素入队列。

8.元素出队列。

9.打印队列的元素。

10.销毁队列。

2.1队列的定义

1.链式队列

//队列的节点结构
typedef int QDataType;
 
typedef struct QueueNode
{
	struct QueueNode* next; //指向队列中下一个节点的指针
	QDataType val;    //存储节点的数据，类型为QDataType（这里定义为 int）
}QNode;
 
//队列的管理结构
typedef struct Queue
{
	QNode* front;    //指向队头节点的指针
	QNode* rear;    //指向队尾节点的指针
	int size;    //记录队列中元素的个数（这个字段很实用，可以快速获取队列大小）
}Queue;

2.循环队列

typedef int QDataType;
 
#define MAXSIZE 30    //定义队列的最大值
typedef struct
{
	QDataType* data;
	int front;    //头指针
	int rear;     //尾指针
}Queue;

2.2队列的功能实现

1.队列初始化

给队列中的各个元素给定值，以免出现随机值。

(1)链式队列

//初始化
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

(2)循环队列

//初始化
void QueueInit(Queue* q)
{
	// 为队列的数据存储空间分配内存。
	q->data = (QDataType*)malloc(sizeof(QDataType) * MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
	// 初始化队首和队尾指针为0，表示队列为空
	q->front = q->rear = 0;
}

2.判断队列是否为空

(1)链式队列

判断size是否为0即可。

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

(2)循环队列

判断front是否等于rear即可。

//判断队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == q->rear;
}

3.判断队列是否已满

(1)链式队列

链式队列不需要判断队列是否已满。因为是基于链表实现的，其存储空间是动态分配的，只要内存充足，就可以一直添加新的节点来存储元素，不存在固定的容量限制，因此从理论上来说没有队列满的概念

(2)循环队列

循环队列判断是否已满需要进行一些特殊处理。

//判断队列是否已满
bool QueueFull(Queue* q)
{
	assert(q);
    // 取模操作是避免越界
	return q->front == (q->rear + 1) % MAXSIZE;
}

4.返回队头元素

(1)链式队列

//读取队头数据
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->val;
}

(2)循环队列

//读取队头数据
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->data[q->front];
}

5.返回队尾元素

(1)链式队列

//读取队尾数据
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->rear);
	return q->rear->val;
}

(2)循环队列

//读取队尾数据
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
 
	// 当rear为0时，rear-1会导致负数索引，这在数组中是无效的  
	// 通过加上MAXSIZE并取模MAXSIZE，我们可以确保索引始终在有效范围内  
	// 这里(q->rear - 1 + MAXSIZE) % MAXSIZE计算的是队尾元素的索引
	return q->data[(q->rear - 1 + MAXSIZE) % MAXSIZE];
}

6.返回队列大小

(1)链式队列

链式队列求队列大小很简单，直接返回size即可。

//统计队列数据个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

(2)循环队列

这里我们要分析一下：

像这个可以使用[rear-front]求出队列的大小。但是要知道，这是个循环队列，rear时=是可以跑到front之后的，如下图所示：

解决方法：

队列长度 = (rear - front + MAXSIZE) % MAXSIZE

这里加上 MAXSIZE 再取模，是为了处理 rear < front 的情况（即队列 "绕回" 数组起始位置时），确保计算结果为正数

//统计队列数据个数
int QueueSize(Queue* q)
{
	assert(q);
	return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

7.元素入队列

(1)链式队列

链式队列元素入队需要判断队列是否为空的情况。

//队尾插入
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newNode->next = NULL;
	newNode->val = x;
 
	// 如果队列为空 
	if (q->rear == NULL)
	{
		// 新节点既是队首也是队尾
		q->front = q->rear = newNode;
	}
	else
	{
		// 将当前队尾节点的next指向新节点
		q->rear->next = newNode;
		// 更新队尾指针为新节点
		q->rear = newNode;
	}
	q->size++;
}

(2)循环队列

取模操作不能少，确保不会越界。

//队尾插入
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	if (QueueFull)
	{
		printf("队列已满\n");
		return;
	}
	q->data[q->rear] = x;
 
	// rear指针向后移动
	// (q->rear + 1) % MAXSIZE这段代码
	// 确保了rear指针的值始终在0到MAXSIZE-1的范围内循环
	q->rear = (q->rear + 1) % MAXSIZE;
}

8.元素出队列

(1)链式队列

//队头删除
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size != 0);
	// 检查队列中是否只有一个节点
	if (q->front->next == NULL)
	{
		free(q->front);
		// 队列变为空，队首和队尾指针都设置为NULL
		q->front = q->rear = NULL;
	}
	// 多个节点
	else
	{
		// 保存下一个节点的指针
		QNode* next = q->front->next;
		// 释放队首节点
		free(q->front);
		// 更新队首指针为下一个节点
		q->front = next;
	}
	q->size--;
}

(2)循环队列

//队头删除
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	// front指针向后移动
	// (q->front + 1) % MAXSIZE这段代码
	// 确保了front指针的值始终在0到MAXSIZE-1的范围内循环
	q->front = (q->front + 1) % MAXSIZE;
}

9.打印队列元素

(1)链式队列

//打印队列元素
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("队尾\n");
}

(2)循环队列

//打印队列元素
void QueuePrint(Queue* q)
{
	assert(q);
	int cur = q->front;
	printf("队头->");
	while (cur != q->rear)
	{
		printf("%d->", q->data[cur]);
		// 避免越界
		cur = (cur + 1) % MAXSIZE;
	}
	printf("队尾\n");
}

10.销毁队列

(1)链式队列

//销毁
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}

(2)循环队列

//销毁
void QueueDestroy(Queue* q)
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 0;
}

3.链式队列和循环队列的细节对比

	链式队列	循环队列
存储结构	采用链式存储，由节点组成，每个节点包含数据元素和指向下一个节点的指针，节点在内存中位置不连续。	通常基于数组实现，将数组空间想象成一个首尾相接的圆环，通过队头和队尾指针在数组中移动来操作元素，元素存储在连续的内存空间中
内存使用	无需预先分配固定空间，可根据元素数量动态分配内存，只要系统有足够内存，就能容纳任意数量元素。但每个节点需额外存储指针，会增加内存开销。	需要预先指定容量，在固定内存空间中操作，内存使用紧凑，无额外指针存储空间。若容量设置不当，可能导致溢出或内存浪费，且扩展容量复杂耗时。
操作效率	插入和删除操作只需调整指针，时间复杂度为 O (1)，但由于节点内存不连续，缓存命中率低，访问速度可能较慢。	插入和删除操作复杂度也是 O (1)，但环绕操作时需计算位置，可能影响效率。因元素存储连续，能提高缓存命中率，访问速度较快。
实现复杂度	需要处理指针管理，易出现指针相关错误，多线程环境下更复杂，实现难度较高。	实现相对简单，无需处理复杂指针操作，单线程环境下管理更容易。
适用场景	适合元素数量不可预知或频繁变化，需要动态扩展，且对内存消耗不敏感的场景。	适用于元素数量相对固定、对内存有严格限制的场景，能有效利用缓存提高访问速度，如内存紧张的嵌入式系统。

4.完整代码

1.链式队列

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int QDataType;
 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;
 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;
 
//初始化
void QueueInit(Queue* q);
//销毁
void QueueDestroy(Queue* q);
 
//队尾插入
void QueuePush(Queue* q, QDataType x);
//队头删除
void QueuePop(Queue* q);
 
//读取队头数据
QDataType QueueFront(Queue* q);
//读取队尾数据
QDataType QueueBack(Queue* q);
 
//统计队列数据个数
int QueueSize(Queue* q);
//判断队列是否为空
bool QueueEmpty(Queue* q);
 
//打印队列元素
void QueuePrint(Queue* q);

#define _CRT_SECURE_NO_WARNINGS 1
 
#include"Queue.h"
 
//初始化
void QueueInit(Queue* q)
{
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
 
//销毁
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}
 
//队尾插入
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newNode->next = NULL;
	newNode->val = x;
 
	// 如果队列为空 
	if (q->rear == NULL)
	{
		// 新节点既是队首也是队尾
		q->front = q->rear = newNode;
	}
	else
	{
		// 将当前队尾节点的next指向新节点
		q->rear->next = newNode;
		// 更新队尾指针为新节点
		q->rear = newNode;
	}
	q->size++;
}
 
//队头删除
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size != 0);
	// 检查队列中是否只有一个节点
	if (q->front->next == NULL)
	{
		free(q->front);
		// 队列变为空，队首和队尾指针都设置为NULL
		q->front = q->rear = NULL;
	}
	// 多个节点
	else
	{
		// 保存下一个节点的指针
		QNode* next = q->front->next;
		// 释放队首节点
		free(q->front);
		// 更新队首指针为下一个节点
		q->front = next;
	}
	q->size--;
}
 
//读取队头数据
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->val;
}
 
//读取队尾数据
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->rear);
	return q->rear->val;
}
 
//统计队列数据个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
 
//打印队列元素
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	QNode* tail = q->rear;
	printf("队头->");
	while (cur != tail->next)
	{
		printf("%d->", cur->val);
		cur = cur->val;
	}
	printf("队尾\n");
}

2.循环队列

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int QDataType;
 
#define MAXSIZE 30
typedef struct
{
	QDataType* data;
	int front;
	int rear;
}Queue;
 
//初始化
void QueueInit(Queue* q);
//销毁
void QueueDestroy(Queue* q);
 
//队尾插入
void QueuePush(Queue* q, QDataType x);
//队头删除
void QueuePop(Queue* q);
 
//读取队头数据
QDataType QueueFront(Queue* q);
//读取队尾数据
QDataType QueueBack(Queue* q);
 
//统计队列数据个数
int QueueSize(Queue* q);
//判断队列是否为空
bool QueueEmpty(Queue* q);
 
//打印队列元素
void QueuePrint(Queue* q);
 
//判断队列是否已满
bool QueueFull(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
 
//初始化
void QueueInit(Queue* q)
{
	// 为队列的数据存储空间分配内存。
	q->data = (QDataType*)malloc(sizeof(QDataType) * MAXSIZE);
	if (q->data == NULL)
	{
		perror("malloc fail:");
		return;
	}
	// 初始化队首和队尾指针为0，表示队列为空
	q->front = q->rear = 0;
}
 
//销毁
void QueueDestroy(Queue* q)
{
	assert(q);
	free(q->data);
	q->data = NULL;
	q->front = q->rear = 0;
}
 
//队尾插入
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	if (QueueFull(q))
	{
		printf("队列已满\n");
		return;
	}
	q->data[q->rear] = x;
 
	// rear指针向后移动
	// (q->rear + 1) % MAXSIZE这段代码
	// 确保了rear指针的值始终在0到MAXSIZE-1的范围内循环
	q->rear = (q->rear + 1) % MAXSIZE;
}
 
//队头删除
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	// front指针向后移动
	// (q->front + 1) % MAXSIZE这段代码
	// 确保了front指针的值始终在0到MAXSIZE-1的范围内循环
	q->front = (q->front + 1) % MAXSIZE;
}
 
//读取队头数据
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->data[q->front];
}
//读取队尾数据
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
 
	// 当rear为0时，rear-1会导致负数索引，这在数组中是无效的  
	// 通过加上MAXSIZE并取模MAXSIZE，我们可以确保索引始终在有效范围内  
	// 这里(q->rear - 1 + MAXSIZE) % MAXSIZE计算的是队尾元素的索引
	return q->data[(q->rear - 1 + MAXSIZE) % MAXSIZE];
}
 
//统计队列数据个数
int QueueSize(Queue* q)
{
	assert(q);
	return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
 
//判断队列是否为空
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == q->rear;
}
 
//判断队列是否已满
bool QueueFull(Queue* q)
{
	assert(q);
	return q->front == (q->rear + 1) % MAXSIZE;
}
 
//打印队列元素
void QueuePrint(Queue* q)
{
	assert(q);
	int cur = q->front;
	printf("队头->");
	while (cur != q->rear)
	{
		printf("%d->", q->data[cur]);
		// 避免越界
		cur = (cur + 1) % MAXSIZE;
	}
	printf("队尾\n");
}

结束语

本节我们承接上文[数据结构——栈] 的话题引入本节数据结构——队列的内容。

感谢大佬的点赞收藏和关注！！！

[数据结构——lesson7.队列]

引言

1.队列的概念及结构

1.1队列的基本概念

1.2队列的结构

1. 链式队列（基于链表）

2. 顺序队列（基于数组）

2.队列的功能

2.1队列的定义

1.链式队列

2.循环队列

2.2队列的功能实现

1.队列初始化

(1)链式队列

(2)循环队列

2.判断队列是否为空

(1)链式队列

(2)循环队列

3.判断队列是否已满

(1)链式队列

(2)循环队列

4.返回队头元素

(1)链式队列

(2)循环队列

5.返回队尾元素

(1)链式队列

(2)循环队列

6.返回队列大小

(1)链式队列

(2)循环队列

7.元素入队列

(1)链式队列

(2)循环队列

8.元素出队列

(1)链式队列

(2)循环队列

9.打印队列元素

(1)链式队列

(2)循环队列

10.销毁队列

(1)链式队列

(2)循环队列

3.链式队列和循环队列的细节对比

4.完整代码

1.链式队列

2.循环队列

结束语

网站公告

今日签到

热门文章

最新发布