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

【数据结构与算法】数据结构初阶：详解栈和队列（下）——队列

作者头像
艾莉丝努力练剑
发布于 2025-11-13 10:13:50
发布于 2025-11-13 10:13:50
1110
举报
文章被收录于专栏：C / C++C / C++

🔥个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题 🍉学习方向：C/C++方向 ⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

再次提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。 因此，不同的场景我们选择不同的数据结构。

​

前言：本篇文章，我们继续来看栈和队列相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的栈和队列部分内容啦。

回顾：

目录

正文

二、队列

（一）队列的概念和结构

1、概念

2、结构

（二）队列结构各种方法的实现（链表实现）

1、队列结构体的定义

2、队列的初始化

3、队列的入队（插入）——队尾

4、队列判空

5、队列的出队（删除）——队头

6、取队头数据和取队尾数据

（1）取队头数据

（2）取队尾数据

（3）同时取

7、获取队列有效元素个数

8、销毁队列

（三）队列结构实现的完整代码

（四）代码优化

1、优化方案

2、优化后的完整代码

（1）Queue.h：

（2）Queue.c：

（3）test.c：

结尾

正文

二、队列

（一）队列的概念和结构
1、概念

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

入队列：进行插入操作的一端称为队尾； 出队列：进行删除操作的一端称为队头。

2、结构

为了节省记忆成本，我们可以把队列理解为饮水机。

用数组来实现队列，还是用链表来实现队列？

那么有uu就要问了，双向链表所有的复杂度都是O(1)啊，用双向链表不是更高效吗？

代码语言：javascript
复制
int  data
*nest
*prev

在结构体里面，像单链表只有上图中前两个成员，大概是8个字节，如果是双向链表就是三个成员，3*4有12个字节，这里空间就更大了！因此一般情况下，我们轻易不会用双向链表这种数据结构，要用也是用单链表，所以这里我们就不进一步分析双向链表了。

所以接下来我们还是要在数组和链表里面去二选一。

从上图可以看出，这里单纯从复杂度角度我们没有办法做到两全其美。如果我们使用当前两种数据结构的任意一个，我们发现要么删除时间复杂度是O(N)，要么插入时间复杂度是O(N)。

那么我们能不能做一些优化呢？

（1）假如用数组进行时间复杂度优化

比如说我们要用数组来实现队列，我们能不能去优化一下，哪怕我额外增加一些成本，但是这个成本非常低，我也能实现删除数据时间复杂度为O(1)，行不行呢？

（1）像删除数据，比如我们在队头删除数据，所有的数据都要往前（队头）移，你能不能说我们删除数据但是不往前移呢？是不是也不行的呀，如果你不往前移，会影响我们后面插入数据； （2）如果把队头和队尾互换一下呢？也不能。这是头插呀，前面如果不留位置，怎么头插呀。

这样看来，用数组来进行时间复杂度的优化好像不太现实。

（2）假如用链表进行时间复杂度优化

链表就可以了——

我们可不可以再定义一个指针，这个成本可以接受吧，我们直接在ptail后面去插入，插入的时间复杂度就变成O(1)了，是不是解决了这个问题。

（3）注意事项

我们这里知道用链表实现队列更好是不是说用数组无法实现队列啊？话可不能这么说哦！数组的底层一定是链表吗？不一定，要看你怎么实现，只不过我们用链表来实现成本更低一些。

（二）队列结构各种方法的实现（链表实现）
1、队列结构体的定义

我们队列结构体的定义需要两个结构体——

Queue.h：

代码语言：javascript
复制
struct ListNode //节点的结构
{
	STDataType data;
	struct ListNode* Next;
}

struct Queue //队列
{
	struct ListNode* phead;//指向队头节点的指针
	struct ListNode* ptail;//指向队尾节点的指针
}
2、队列的初始化

Queue.h：

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

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

 //定义队列的结构
typedef struct Queue 
{
	QueueNode* phead;//指向队头节点的指针
	QueueNode* ptail;//指向队尾节点的指针
}Queue;

//初始化
void QueueInit(Queue* pq);

Queue.c：

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

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

test.c：

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

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

int main()
{
	test01();
	return 0;
}
3、队列的入队（插入）——队尾

我们初步来写一下代码——

Queue.c：

代码语言：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;

	pq->ptail->next = newnode;
	pq->ptail = pq->ptail->next;
}

但是，还有一种情况我们没有考虑：队列为空。

（1）队列不为空：

（2）队列为空：

我们把队列为空考虑进去，判断如果为空，newnode插入进空指针会怎么样——

Queue.c：

代码语言：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;
	}
}

test.c：

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

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

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
}

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

一个一个插入——

4、队列判空

Queue.c：

代码语言：javascript
复制
//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead = NULL;
}
5、队列的出队（删除）——队头

我们写出根据上图，写出代码——

这样代码写完了吗？我都这么问了，肯定没有嘛。那还缺少什么呢？

还有一种特殊情况上面的代码没有考虑到——

Queue.c：

代码语言：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;
	}
}

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);
	QueuePop(&q);

}

int main()
{
	test01();
	return 0;
}
6、取队头数据和取队尾数据
（1）取队头数据

Queue.c：

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

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);
	//QueuePop(&q);

	printf("队头：%d\n", QueueFront(&q));
}

int main()
{
	test01();
	return 0;
}
（2）取队尾数据

Queue.c：

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

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);
	//QueuePop(&q);

	printf("队尾：%d\n", QueueBack(&q));
}

int main()
{
	test01();
	return 0;
}
（3）同时取

Queue.c：

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

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

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);
	//QueuePop(&q);

	printf("队头：%d\n", QueueFront(&q));
	printf("队尾：%d\n", QueueBack(&q));
}

int main()
{
	test01();
	return 0;
}
7、获取队列有效元素个数

Queue.c：

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

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);
	//QueuePop(&q);

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

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

运行一下——

8、销毁队列

Queue.c：

代码语言：javascript
复制
//销毁
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;//防止phead、ptail变野指针
}

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);
	//QueuePop(&q);

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

	QueueDestory(&q);
}

int main()
{
	test01();
	return 0;
}
（三）队列结构实现的完整代码

Queue.h：

代码语言：javascript
复制
#pragma once
#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;//指向队尾节点的指针
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestory(Queue* pq);

//入队列，队尾
void QueuePush(Queue* pq, QDataType x);

// 出队列，队头
void QueuePop(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

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

Queue.c：

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#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);
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur = pcur->next;
	}
	return size;
}

test.c：

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1
#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);
	//QueuePop(&q);

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

int main()
{
	test01();
	return 0;
}
（四）代码优化
1、优化方案

前面所有的方法的实现，时间复杂度都是O(1)，唯独最后【获取队列有效元素个数】这里时间复杂度变成了O(N)，试想一下：如果存在大量的队列有效元素个数——一万个、五万个、十万个数据，那我们每次调用这个方法都要把队列给遍历一遍，这个对于程序的性能来说是不是非常非常差啊，本身这就是一个底层的代码，一个底层的代码时间复杂度都降不到O(1)，我们自己的程序里面如果还涉及到循环，那这里程序的执行效率就会非常的低。

我们有没有什么办法可以把队列中的有效元素个数给处理一下呢？可以。

我们定义一个size，用来记录队列中有效数据个数。

对于插入数据的地方，size++；对于删除数据的地方，size--。

2、优化后的完整代码
（1）Queue.h：
代码语言：javascript
复制
#pragma once
#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 QueueDestory(Queue* pq);

//入队列，队尾
void QueuePush(Queue* pq, QDataType x);

// 出队列，队头
void QueuePop(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq);
（2）Queue.c：
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"Queue.h"

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

//销毁队列
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;//防止phead、ptail变野指针
	pq->size = 0;//销毁后元素个数重置为0
}

//入队列,队尾
void QueuePush(Queue* pq, QDataType x)
{
	int size = 0;
	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;
	}
	pq->size++;//入队后元素个数+1
}

//队列判空
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;
	}
	pq->size--;//出队后元素个数-1
}

//取队头数据
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)
{
	return pq->size;
}
（3）test.c：
代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#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);
	//QueuePop(&q);

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

	QueueDestory(&q);
}

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

运行一下——

成功了！现在我们把【获取队列有效元素个数】部分的时间复杂度也降到O(1)了。

结尾

往期回顾：

【数据结构与算法】数据结构初阶：详解栈和队列（上）——栈

【数据结构与算法】数据结构初阶：详解顺序表和链表（五）——双向链表

【数据结构与算法】数据结构初阶：详解顺序表和链表（四）——单链表（下）

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。 大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的栈和队列知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！

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

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

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

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

数据
数据结构与算法
数据结构
队列
链表
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 目录
  • 正文
    • 二、队列
      • （一）队列的概念和结构
      • （二）队列结构各种方法的实现（链表实现）
      • （三）队列结构实现的完整代码
      • （四）代码优化
  • 结尾
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

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. 腾讯云 版权所有

登录 后参与评论