文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构初阶】--栈与队列（队列）

【数据结构初阶】--栈与队列（队列）

作者头像
用户11915063
发布于 2025-11-19 19:08:29
发布于 2025-11-19 19:08:29
1120
举报

前言：上篇博客我们学习了栈的相关知识，掌握了栈的结构与特性，这篇博客将带着大家学习队列的相关知识，希望大家继续坚持下去🌹🌹🌹

一、队列的概念与结构

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

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

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

队列既可以用数组来实现也可以用链表来实现，但是用数组进行插入操作的时间复杂度为O(N)，虽然链表的插入时间复杂度也为O(N)，但是我们可以定义个尾节点来方便我们插入操作

队列结构：

代码语言：javascript
复制
typedef int QDataType;
//定义节点结构
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

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

二、队列的入队和出队

因为我们定义了尾节点，所以入队出队操作会很简单

入队：

代码语言：javascript
复制
//入队列--队尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建值为x的节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
}

入队列首先还是要创建一个节点结构，判断队列是否为空，若为空，直接让头节点和尾节点都指向新节点，若不为空，则新节点的尾部->next指向新节点，再让尾节点走到新节点的位置

在实现出队之前，我们首先要判断队列是否为空，队列不为空我们才可以进行出队

代码语言：javascript
复制
//队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

出队：

代码语言：javascript
复制
//出队列--对头
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;
	}
}

当队列中只有一个节点时，直接free，然后置为NULL，如果有多个，先定义个next节点指针指向头节点的下一个节点，free头节点，再让头节点走到next位置就可以了

三.队列取队头数据和队尾数据

取队首数据：

代码语言：javascript
复制
//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

队头就是phead，直接返回就可以

取队尾数据 ：

代码语言：javascript
复制
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

队尾就是ptail，直接返回就可以

test.c:

代码语言：javascript
复制
#include"Queue.h"
 
void test1()
{
	Queue q;
	QueueInit(&q);
 
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
 
	printf("队首元素:%d\n",QueueHead(&q));
	printf("队尾元素:%d\n",QueueTail(&q));
}
 
int main()
{
	test1();
}

测试结果：

四.队列的有效数据个数和队列的销毁

队列的有效数据个数：

代码语言：javascript
复制
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
	//return pq->size; 
}

这里涉及到了循环，时间复杂度为O(N)，如果这里在队列定义了一个size，就可以直接返回pq->size

销毁队列：

代码语言：javascript
复制
//销毁
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;
}

遍历队列，每次销毁前存下下一个节点，销毁当前节点后来到下一个节点的位置，最后遍历结束后把pq->phead和pq->ptail都置为空

五、全部代码展示

Queue.h：

代码语言：javascript
复制
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
//定义节点结构
typedef struct QueueNode
{
	QDataType 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, QDataType x);
//队列是否为空
bool QueueEmpty(Queue* pq);
//出队列--对头
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

Queue.c：

代码语言：javascript
复制
#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}

//入队列--队尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建值为x的节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
}

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

//出队列--对头
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;
	}
}

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

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
	//return pq->size; 
}

//销毁
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;
}

test.c：

代码语言：javascript
复制
#include"Queue.h"

void test01()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);//1 2 3 4 

	/*QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);*/

	printf("队头元素:%d\n", QueueFront(&q));
	printf("队尾元素:%d\n", QueueBack(&q));
	printf("size:%d\n", QueueSize(&q));
}

int main()
{
	test01();
	return 0;
}

测试结果：

往期回顾：

【数据结构初阶】--双向链表（一）

【数据结构初阶】--双向链表（二）

【数据结构初阶】--栈与队列（栈）

总结：这篇博客带着大家实现了队列的相关接口，那么接下来我还会带着大家继续学习二叉树、堆等相关出街数据结构，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持🌹🌹🌹

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除
队列
链表
数据
数据结构
queue

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

队列
链表
数据
数据结构
queue
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、队列的概念与结构
  • 二、队列的入队和出队
    • 入队：
    • 出队：
  • 三.队列取队头数据和队尾数据
    • 取队首数据：
    • 取队尾数据 ：
  • 四.队列的有效数据个数和队列的销毁
    • 队列的有效数据个数：
    • 销毁队列：
  • 五、全部代码展示
    • Queue.h：
    • Queue.c：
    • test.c：
    • 测试结果：
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论