【数据结构】队列的完整实现-EW帮帮网

队列的完整实现

队列的完整实现
github地址
前言
1. 队列的概念及其结构
- 1.1 概念
- 1.2 组织结构
2. 队列的实现
完整代码与功能测试
结语

队列的完整实现

github地址

前言

队列（Queue）作为一种基础且重要的数据结构，在计算机科学中扮演着关键角色。无论是操作系统的任务调度、网络数据包的管理，还是算法中的广度优先搜索（BFS），队列的“先进先出”（FIFO）特性都使其成为不可或缺的工具。理解队列的实现原理，不仅能帮助开发者更高效地处理数据，还能为后续学习复杂的数据结构打下坚实基础。

本文将以 链式结构 为核心，详细介绍队列的完整实现。从结构设计、接口定义到功能测试，一步步剖析如何用C语言实现一个高效、健壮的队列。文章重点讲解入队（push）、出队（pop）、获取队头/队尾元素等核心操作，并通过清晰的代码示例和测试案例，帮助读者深入理解队列的内部机制。此外，所有代码已在GitHub开源，方便读者参考和扩展。

1. 队列的概念及其结构

1.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的特性

入队列：进行插入操作的一端称为队尾，入队常被称为push
出队列：进行删除操作的一端称为队头，出队常被称为pop
如下图所示

1.2 组织结构

队列可以使用数组和链表的结构实现，使用链表的结构实现更优一些。
因为如果使用数组的结构，出队列时，在数组头上出数据，效率会比较低
而对于链表实现的队列来说，入队对应尾插操作，出队对应头删操作。在链表中，头删和尾插操作只需要O(1)时间复杂度，因此队列更适合使用链表来实现，本文我们采用单链表来实现。

在这里插入图片描述

2. 队列的实现

接口一览

//初始化 与 销毁队列
void QueueInit(Queue* pQueue);
void QueueDestroy(Queue* pQueue);

// 队尾入队列    队头出队列
void QueuePush(Queue* pQueue, QDataType data);
void QueuePop(Queue* pQueue);

// 获取队列头部元素   /获取队列尾部元素
QDataType QueueFront(Queue* pQueue);
QDataType QueueBack(Queue* pQueue);

//获取队列中有效元素个数	检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueSize(Queue* pQueue);
bool QueueEmpty(Queue* pQueue);

结构定义与架构

结构：

//队列，先进先出，数组的话在头部出数据不方便，因此用链表来实现，单链表
typedef int QDataType;

typedef struct QNode {		//链式队列，用单链表实现
	struct QNode* next;
	QDataType data;
}QNode;

//队列中 用两个指针来指示 队头和队尾，方便入队和出队
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;

使用typedef int QDataType方便队列中存放不同的数据类型
QNode表示我们链表中一个个的结点，内部包含next指针和数据data
使用struct Queue结构来表示整个队列，其中：
- 规定两个QNode*的指针，分别保存链表第一个结点和尾结点的地址(分别指向第一个结点和最后一个结点)
- 定义int size来保存队列中的有效元素个数。

架构图如下：
在这里插入图片描述

初始化和销毁

初始化：

//初始化 与 销毁队列
void QueueInit(Queue* pQueue) {
	assert(pQueue);
	pQueue->head = pQueue->tail = NULL;
	pQueue->size = 0;
}

通过Queue结构体的指针pQueue，来访问结构体中的成员head和tail，通过head和tail指针和链表的特性，可以访问到链表中的每个结点。head和tail指针主要是为了方便访问队头结点和队尾结点。
assert(pQueue)保证Queue结构存在
初始化队列：
- 链表中无节点时，head和tail指针都置为NULL
- 初始化size为0

销毁：

//销毁
void QueueDestroy(Queue* pQueue) {
	assert(pQueue);
    // 空链表也可以销毁，因此无需断言链表非空
	QNode* cur = pQueue->head;
	while (cur != NULL) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pQueue->head = pQueue->tail = NULL;
	pQueue->size = 0;
}

assert(pQueue)保证Queue结构存在
QNode* cur = pQueue->head：cur保存当前头结点的地址
- while循环依次释放每一个结点
- 保存cur的下一个节点cur->next
- free(cur)释放当前结点，cur移动指向下一个节点，直到NULL时结束
pQueue->head = pQueue->tail = NULL：将head和tail指针各自置NULL
pQueue->size = 0最后将size置0

入队和出队

入队：

// 队尾入队列    队头出队列
void QueuePush(Queue* pQueue, QDataType data) {
	assert(pQueue);
    // 开辟新结点，并将数据置于新结点中
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL) {
		perror("malloc failed\n");
		return;
	}
	newNode->data = data;
	newNode->next = NULL;
	// 初始化后，head 和 tail 都为NULL
	if (pQueue->head == NULL) {
		assert(pQueue->tail == NULL);	// head为NULL时，tail必须也为NULL
		pQueue->head = pQueue->tail = newNode;
	}
	else {
		pQueue->tail->next = newNode;
		pQueue->tail = newNode;
	}
	pQueue->size++;
}

assert(pQueue)保证Queue结构存在
QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc failed\n"); return; }开辟一个新结点，并进行初始化。
初始化QNode后，push 一个结点本质是单链表的尾插，有两种情况：
- 队列为空(队列中无节点)时：新开辟的QNode应当成为链表中的第一个节点，pQueue->head = pQueue->tail = newNode操作调整首尾指针即可。
- 队列中已有其他结点时：此时是单链表的尾插。
  - pQueue->tail->next = newNode：新结点链入原链表
  - pQueue->tail = newNode：更改尾指针指向
push过后，pQueue->size++，队列的size应当++

出队：

v1版本仅实现：

void QueuePop(Queue* pQueue) {
	assert(pQueue);
	assert(pQueue->head != NULL);

	//if(pQueue->head->next == NULL){}	//考虑只剩一个结点的情况
    if (pQueue->head == pQueue->tail) {	
        free(pQueue->head);
        pQueue->head = pQueue->tail = NULL;
    }
    else {
        QNode* cur = pQueue->head;
        pQueue->head = pQueue->head->next;
        free(cur);
        cur = NULL;
    }
    pQueue->size--;
}

assert(pQueue)：断言队列存在，assert(pQueue->head != NULL)，确保pop时队列内有元素
pop出队时，销毁第一个结点，确保队列存在且有元素后，此处存在两种情况
- 当前仅剩一个结点时：pQueue->head == pQueue->tail，直接free当前头结点，将head和tail指针置NULL即可
- 当前存在多个节点时(else)：
  - QNode* cur = pQueue->head：记录下当前的头结点
  - pQueue->head = pQueue->head->next：头指针向后移动
  - free(cur)后cur = NULL释放之前的头结点的空间，并将cur置NULL
pop后size应当--

v2版本优化：

可以看到，上述的代码中存在多次free，且都是对要被删除的结点进行free，那么是否可以优化为一次free呢

void QueuePop(Queue* pQueue) {
	assert(pQueue);
	assert(pQueue->head != NULL);
	//优化版本
	QNode* cur = pQueue->head;
	if (pQueue->head == pQueue->tail)
		pQueue->head = pQueue->tail = NULL;
	else
		pQueue->head = pQueue->head->next;

	free(cur);
    cur = NULL;
	pQueue->size--;
}

assert(pQueue)：断言队列存在，assert(pQueue->head != NULL)，确保pop时队列内有元素
QNode* cur = pQueue->head：不管队列中剩余几个结点，最终都要free头结点，那么cur直接保存头结点的地址，方便进行操作
pQueue->head == pQueue->tail仅剩一个结点时：仅需对head和tail指针做修改。有多个节点时，pQueue->head = pQueue->head->next，head指针向后移动。
最终cur内保存了要被删除的结点的地址，直接free(cur)并置NULL
pop后size应当--

取队头队尾数据

获取队头数据：

// 获取队列头部元素   获取队列尾部元素
QDataType QueueFront(Queue* pQueue) {
	assert(pQueue);
	//确保队列非空
	assert(!QueueEmpty(pQueue));
	return pQueue->head->data;
}

assert(pQueue)确保队列存在，assert(!QueueEmpty(pQueue))确保队列非空，非空队列内才有数据
头部数据：return pQueue->head->data，通过头指针head访问队列内第一个结点的数据

获取队尾数据：

//获取队列尾部元素
QDataType QueueBack(Queue* pQueue) {
	assert(pQueue);
	//确保队列非空
	assert(!QueueEmpty(pQueue));
	return pQueue->tail->data;
}

assert(pQueue)确保队列存在，assert(!QueueEmpty(pQueue))确保队列非空，非空队列内才有数据
尾部数据：return pQueue->tail->data，通过尾指针tail访问队列内最后一个结点的数据

获取size和判空

获取size：

int QueueSize(Queue* pQueue) {
	assert(pQueue);
	return pQueue->size;
}

assert(pQueue)：断言指针非空，确保Queue结构体存在
直接返回size即可得到元素个数
- 这里就体现出我们在Queue结构中添加一个size成员的好处，只需在每次Push/Pop后对size进行加减，即可方便的得到队列的size
- 如果Queue结构内不维护一个size变量的话，由于我们的队列是基于单链表实现的，每次获取队列的大小时都只能遍历链表来得到size，遍历的时间复杂度较高。

判空：

bool QueueEmpty(Queue* pQueue) {
	assert(pQueue);
	//return (pQueue->head == NULL && pQueue->tail == NULL);
	return pQueue->size == 0;	// size为0时为空
}

assert(pQueue)：断言指针非空，确保Queue结构体存在
pQueue->size == 0或pQueue->head == NULL && pQueue->tail == NULL，两个条件均可以标识队列为空

完整代码与功能测试

完整代码如下：

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

//队列，先进先出，数组的话在头部出数据不方便，因此用链表来实现，单链表
typedef int QDataType;

typedef struct QNode {		//链式队列，用单链表实现
	struct QNode* next;
	QDataType data;
}QNode;

//队列中 用两个指针来指示 队头和队尾，方便入队和出队
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化 与 销毁队列
void QueueInit(Queue* pQueue);
void QueueDestroy(Queue* pQueue);

// 队尾入队列    队头出队列
void QueuePush(Queue* pQueue, QDataType data);
void QueuePop(Queue* pQueue);

// 获取队列头部元素   /获取队列尾部元素
QDataType QueueFront(Queue* pQueue);
QDataType QueueBack(Queue* pQueue);

//获取队列中有效元素个数	检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueSize(Queue* pQueue);
bool QueueEmpty(Queue* pQueue);

// #include "Queue.h" 多文件编译时，需正确包含头文件

//初始化 与 销毁队列
void QueueInit(Queue* pQueue) {
	assert(pQueue);
	pQueue->head = pQueue->tail = NULL;
	pQueue->size = 0;
}
//销毁
void QueueDestroy(Queue* pQueue) {
	assert(pQueue);
	QNode* cur = pQueue->head;
	while (cur != NULL) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pQueue->head = pQueue->tail = NULL;
	pQueue->size = 0;
}

// 队尾入队列    队头出队列
void QueuePush(Queue* pQueue, QDataType data) {
	assert(pQueue);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL) {
		perror("malloc failed\n");
		return;
	}
	newNode->data = data;
	newNode->next = NULL;
	// 初始化后，head 和 tail 都为NULL
	if (pQueue->head == NULL) {
		assert(pQueue->tail == NULL);	// head为NULL时，tail必须也为NULL
		pQueue->head = pQueue->tail = newNode;
	}
	else {
		pQueue->tail->next = newNode;
		pQueue->tail = newNode;
	}
	pQueue->size++;
}
//队列的头删法
void QueuePop(Queue* pQueue) {
	assert(pQueue);
	assert(pQueue->head != NULL);

	if(pQueue->head->next == NULL){}	//考虑只剩一个结点的情况
	//if (pQueue->head == pQueue->tail) {	
	//	free(pQueue->head);
	//	pQueue->head = pQueue->tail = NULL;
	//}
	//else {
	//	QNode* cur = pQueue->head;
	//	pQueue->head = pQueue->head->next;
	//	free(cur);
	//	cur = NULL;
	//}
	//pQueue->size--;

	//优化版本
	QNode* cur = pQueue->head;
	if (pQueue->head == pQueue->tail)
		pQueue->head = pQueue->tail = NULL;
	else
		pQueue->head = pQueue->head->next;

	free(cur);
	cur = NULL;
	pQueue->size--;
}

// 获取队列头部元素   获取队列尾部元素
QDataType QueueFront(Queue* pQueue) {
	assert(pQueue);
	//确保队列非空
	assert(!QueueEmpty(pQueue));
	return pQueue->head->data;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pQueue) {
	assert(pQueue);
	//确保队列非空
	assert(!QueueEmpty(pQueue));
	return pQueue->tail->data;
}

//获取队列中有效元素个数	检测队列是否为空，如果为空返回非零结果，如果非空返回0
// 双向链表中，不能用 哨兵位的数据  来存储 链表的长度
// 之前的实现中，结点内存放的数据是int，导致哨兵位内的数据位类型也是int,
int QueueSize(Queue* pQueue) {
	assert(pQueue);
	return pQueue->size;
}
bool QueueEmpty(Queue* pQueue) {
	assert(pQueue);
	//return (pQueue->head == NULL && pQueue->tail == NULL);
	return pQueue->size == 0;	// size为0时为空
}

功能测试：

// 需正确包含头文件
#include "Queue.h"

void TestQueue() {
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, 1);
	QueuePush(&queue, 2);
	QueuePush(&queue, 3);
	QueuePush(&queue, 4);
	QueuePush(&queue, 6);

	// 遍历的代码
	/*while (!QueueEmpty(&queue)) {
		printf("%d ", QueueFront(&queue));
		QueuePop(&queue);
	}*/
	
	printf("队尾：%d  有效元素个数：%d\n", QueueBack(&queue), QueueSize(&queue));
	printf("队头：%d  有效元素个数：%d\n", QueueFront(&queue), QueueSize(&queue));

	QueuePop(&queue);
	printf("队尾：%d  有效元素个数：%d\n", QueueBack(&queue), QueueSize(&queue));
	printf("队头：%d  有效元素个数：%d\n", QueueFront(&queue), QueueSize(&queue));

	QueuePop(&queue);
	printf("队尾：%d  有效元素个数：%d\n", QueueBack(&queue), QueueSize(&queue));
	printf("队头：%d  有效元素个数：%d\n", QueueFront(&queue), QueueSize(&queue));

	QueuePop(&queue);
	QueuePop(&queue);
	printf("队列有效元素个数：%d\n", QueueSize(&queue));
	while (!QueueEmpty(&queue)) {
		printf("%d ", QueueFront(&queue));
		QueuePop(&queue);
	}

	QueueDestroy(&queue);
}

//函数调用的栈帧  和  数据结构的栈
// 函数调用的栈帧  是操作系统层面对内存区域的划分
// 和  数据结构的栈

int main() {

	TestQueue();
	return 0;
}

在这里插入图片描述

结语

通过本文的学习，我们完成了队列的完整实现：从结构体设计到核心接口的实现，再到功能验证。关键点包括：

链式结构的优势：使用单链表实现队列，确保入队（尾插）和出队（头删）操作的时间复杂度均为 O(1)。
双指针的妙用：通过 head 和 tail 指针分别标记队头和队尾，避免了遍历链表的性能损耗。
健壮性保障：通过断言（assert）确保操作合法性，并结合 size 字段快速判断队列状态。

希望本文能帮助你彻底掌握队列的实现原理，并激发对数据结构更深层次的探索。

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎点赞⭐收藏支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！

你的每一次互动，都是对作者最大的鼓励！

征程尚未结束，让我们在广阔的世界里继续前行！ 🚀

【数据结构】队列的完整实现

队列的完整实现

队列的完整实现

github地址

前言

1. 队列的概念及其结构

1.1 概念

1.2 组织结构

2. 队列的实现

接口一览

结构定义与架构

初始化和销毁

入队和出队

取队头队尾数据

获取size和判空

完整代码与功能测试

结语

网站公告

今日签到

热门文章

最新发布