深入理解队列：从概念到实现
·
一、队列
(1) 、基本概念
- 概念：队列是最常见的概念，日常生活经常需要排队，仔细观察队列会发现，队列是一种逻辑结构，是一种特殊的线性表，特殊在只能在固定的两端操作线性表，只要满足上述特性，那么这种特殊的线性表就会呈现一种"先进先出"的逻辑，这种逻辑就被称为队列
- 图解
- 说明1：从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分队列中的满队和空队
- 说明2：由于约定了只能在线性表固定的两端进行操作，于是给队列这种特殊的线性表的插入删除，起了个特殊的名称：
- 队头：可以删除节点的一端
- 队尾：可以插入节点的一端
- 入队：将节点插入到队尾之后，函数名通常为EnQueue() --- 增加数据
- 出队：将队头节点从队列中删除，函数名通常为OutQueue() --- 删除数据
- 取队头：取得队头元素，但不出队，函数名通常为front() --- 查改数据
(2) 、队列的储存方式
- 说明：与其他的逻辑结构类似，队列可以采用顺序存储形成的循环队列，也可以采用链式存储形成的链式队列。顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地利用整个数组，出队入队时也不必移动当中地数据
(3)、顺序队列的基本操作
1、顺序队列的管理结构体设计
- 说明：顺序队列通常使用数组实现，核心结构体包含三个关键成员：一个固定大小的数组存储元素，两个整型变量分别记录队头（front）和队尾（rear）位置。数组大小需预先定义或动态分配。
- 图解
- 示例代码
// 顺序队列的管理结构体
typedef struct sequential_queue
{
datatype_p data_p; // 指向顺序队列内存的指针
int capacity; // 顺序队列的容量
int front; // 顺序队列的队头的元素下标
int rear; // 顺序队列的队尾的元素下标
}sq_queue_t, *sq_queue_p;
2、初始化顺序队列
- 说明：顺序队列是一种基于数组实现的队列结构，通过固定大小的连续内存空间存储元素，包含队头（front）和队尾（rear）指针。初始化时需分配数组空间，并将 front 和 rear 均置为 -1 或 0（视实现方式而定），表示队列为空。
- 图解：
- 示例代码
/**
* @brief： 初始化顺序队列
* @note： None
* @param： cap_size： 顺序队列的容量
* @retval: 成功：返回指向这个顺序队列的内存的指针
* 失败：返回NULL
*/
sq_queue_p SEQUENTIAL_QUEUE_Init(int cap_size)
{
// 1、申请顺序队列的堆内存空间
sq_queue_p p = malloc(sizeof(sq_queue_t));
bzero(p, sizeof(sq_queue_t));
// 2、给该内存空间(堆区1)进行赋值操作
if (p!=NULL)
{
// 指向顺序队列内存(堆区2)的指针
p->data_p = malloc(sizeof(datatype)*cap_size);
if (p->data_p == NULL)
{
free(p);
return NULL;
}
// 顺序队列的容量
p->capacity = cap_size;
// 顺序队列的队头的元素下标
p->front = 0;
// 顺序队列的队尾的元素下标
p->rear = 0;
}
else
{
return NULL;
}
// 3、成功返回指向这个顺序队列管理结构体的内存指针
return p;
}
3、判断顺序队列是否为空
- 说明：顺序队列通常由数组实现，需要维护队头（front）和队尾（rear）两个指针。队列为空的条件是队头指针和队尾指针指向同一位置。
- 图解：
- 示例代码
/**
* @brief： 判断顺序队列是否为空
* @note： None
* @param： p: 指向这个顺序队列的内存的指针
* @retval: 如果顺序队列为空：返回true
* 如果顺序队列非空：返回false
*/
bool SEQUENTIAL_QUEUE_IfEmpty(sq_queue_p p)
{
return (p->front == p->rear);
}
4、判断顺序队列是否满了
- 说明：检查顺序队列的队尾指针
rear是否等于队列的最大容量减一（基于数组索引从0开始）。若rear == capacity - 1或判断(rear + 1) % capacity == front，则队列已满。 - 图解
- 示例代码
/**
* @brief： 判断顺序队列是否为满
* @note： None
* @param： p: 指向这个顺序队列的内存的指针
* @retval: 如果顺序队列为满：返回true
* 如果顺序队列非满：返回false
*/
bool SEQUENTIAL_QUEUE_IfFull(sq_queue_p p)
{
return ((p->rear+1)%(p->capacity) == p->front);
}
5、入队(增加数据)
- 说明：入队是队列数据结构中的核心操作，用于在队列的尾部添加新元素。队列遵循先进先出原则，即最早入队的元素会最先被移除。
- 图解
- 示例代码：
/**
* @brief： 入队 --- 增加数据
* @note： None
* @param： p: 指向这个顺序队列的内存的指针
* data：要入队的数据
* @retval: 成功：返回0
* 失败：返回-1
*/
int SEQUENTIAL_QUEUE_EnQueue(sq_queue_p p, datatype data)
{
// 1、判断队列是否是满的
if (SEQUENTIAL_QUEUE_IfFull(p))
return -1;
// 2、在队列的队尾插入数据
p->data_p[p->rear] = data;
// 3、队尾标志+1
p->rear = (p->rear+1)%(p->capacity); // 因为是循环队列，因此需要取余操作
// 4、成功返回0
return 0;
}
6、出队(删除数据)
- 说明：出队是队列的基本操作之一，用于删除队列的队首元素并返回该元素。队列遵循原则，因此出队操作总是针对最早进入队列的数据。
- 图解
- 示例代码
/**
* @brief： 出队 --- 删除数据
* @note： None
* @param： p: 指向这个顺序队列管理结构体内存的指针
* @retval: 成功：返回0
* 失败：返回-1
*/
int SEQUENTIAL_QUEUE_OutQueue(sq_queue_p p)
{
// 1、判断队列是否是空的
if (SEQUENTIAL_QUEUE_IfEmpty(p))
return -1;
// 2、在队列的队头删除数据
bzero(&p->data_p[p->front], sizeof(datatype)); // 清空数据(这一步可以不用，看你的)
p->front = (p->front+1)%(p->capacity); // 因为是循环队列，因此需要取余操作,控制其范围
// 3、成功返回0
return 0;
}
7、遍历队列
- 说明：队列是一种先进先出的数据结构，遍历队列通常指按顺序访问队列中的所有元素
- 图解
- 示例代码
/**
* @brief： 遍历队列数据 --- 查找数据
* @note： None
* @param： p: 指向这个顺序队列管理结构体内存的指针
* @retval: 成功：返回0
* 失败：返回-1
*/
int SEQUENTIAL_QUEUE_Show(sq_queue_p p)
{
if (SEQUENTIAL_QUEUE_IfEmpty(p))
return -1;
// 遍历整个顺序队列
printf("=====================顺序栈里面的数据======================\n");
for (int i = p->front; i!=p->rear; i=(i+1)%(p->capacity))
{
printf("顺序队列里面的第[%d]个数据为 == %d\n", i, p->data_p[i].data);
}
return 0;
}
8、获取队头的数据 --- 查找数据
- 说明：队列是一种先进先出的数据结构，队头数据是第一个被插入的元素，也是第一个被访问或删除的元素。
- 图解
- 示例代码
/**
* @brief： 获取队头的数据 --- 查找数据
* @note： None
* @param： p: 指向这个顺序队列管理结构体内存的指针
* @retval: 成功：返回队头的数据
* 失败：返回NULL
*/
datatype_p SEQUENTIAL_QUEUE_GetFrontData(sq_queue_p p)
{
if (SEQUENTIAL_QUEUE_IfEmpty(p))
return NULL;
// 将队头的数据返回
return &(p->data_p[p->front]);
}
9、销毁队列
- 说明：通过循环逐个取出队列中的元素，直到队列为空。
- 图解
- 示例代码
/**
* @brief： 销毁队列
* @note： None
* @param： p: 指向这个顺序队列管理结构体内存的指针
* @retval: None
*/
void SEQUENTIAL_QUEUE_UnInit(sq_queue_p p)
{
free(p->data_p); // 先释放堆区2的资源
free(p); // 再释放堆区1的资源
}
10、顺序队列的使用
/**
******************************************************************************
* @file main.c
* @author MChine慕青
* @version V0.0.1
* @date 2025.09.22
* @brief 使用顺序队列实现数据的增删查改功能
* 环境：ubuntu22.04
* 编译：gcc main.c sequential_queue.c
* 执行：./a.out
*
******************************************************************************
* @attention
*
* 本文档只供学习使用，不得商用，违者必究
*
* 个人博客： https://blog.csdn.net/2402_83622972?type=blog
* 有疑问或者建议：3211735057@qq.com
*
******************************************************************************
*/
#include "sequential_queue.h"
int main(int argc, char const *argv[])
{
// (1)、初始化顺序队列
sq_queue_p p = SEQUENTIAL_QUEUE_Init(10);
if (p == NULL)
{
printf("初始化顺序队列失败!\n");
return -1;
}
// (2)、选择功能(增删查改、退出(销毁顺序队列))
int select = 0;
datatype new_data = {0};
datatype_p get_data = NULL;
datatype change_data = {0};
while (1)
{
// 1、显示整个顺序队列的数据
SEQUENTIAL_QUEUE_Show(p);
// 2、显示功能选项
printf("请选择以下功能!\n");
printf("1、入队(增加数据)\n");
printf("2、出队(删除数据)\n");
printf("3、取队头数据\n");
printf("4、修改队头数据\n");
printf("5、退出!\n");
// 3、选择要做的功能
scanf("%d", &select);
while(getchar()!='\n');
switch (select)
{
case 1:
// 提示
printf("请输入要插入的数据:\n");
// 输入数据
scanf("%d", &new_data.data);
while(getchar()!='\n');
// 添加数据到顺序队列中
SEQUENTIAL_QUEUE_EnQueue(p, new_data);
break;
case 2:
// 删除顺序队列中的数据(队头)
SEQUENTIAL_QUEUE_OutQueue(p);
break;
case 3:
// 提示
printf("正在获取队头数据\n");
// 获取队头的数据
get_data = SEQUENTIAL_QUEUE_GetFrontData(p);
if (get_data != NULL)
printf("get_data.data == %d\n", get_data->data);
break;
case 4:
// 提示
printf("请输入要修改的队头数据\n");
// 输入数据
scanf("%d", &change_data.data);
while(getchar()!='\n');
// 修改队头的数据
SEQUENTIAL_QUEUE_ChangeFrontData(p, change_data);
break;
case 5:
SEQUENTIAL_QUEUE_UnInit(p);
printf("系统已退出!\n");
goto exit_sys_label;
break;
}
}
exit_sys_label:
return 0;
}
(4)、链式队列的基本操作
1、链式队列的管理结构体设计
- 说明：链式队列通常由两个指针（
front和rear）和一个节点结构体组成。front指向队首节点，rear指向队尾节点，节点结构体包含数据域和指向下一节点的指针。 - 图解
- 示例代码
// 节点设计
typedef struct node
{
// 数据域
datatype data;
// 指针域
struct node *next_p;
}node_t, *node_p;
// 链式队列管理结构体设计
typedef struct link_cir_queue
{
// 链式队列的队头指针
node_p front_p;
// 链式队列的队尾指针
node_p rear_p;
// 链式队列的当前的元素个数
int num;
}lc_queue_t, *lc_queue_p;
2、初始化链式队列
- 说明：链式队列通过动态分配内存创建头节点，并设置队头（front）和队尾（rear）指针指向该节点。头节点的
next指针初始化为NULL，表示队列为空。 - 图解
- 示例代码
/**
* @brief： 初始化链式队列管理结构体(里面有初始化头节点)
* @note： None
* @param： None
* @retval: 成功：返回指向这个链式队列管理结构体内存的指针
* 失败：返回NULL
*/
lc_queue_p LINK_CIR_QUEUE_Init(void)
{
// 1、申请管理结构体堆内存空间
lc_queue_p p = malloc(sizeof(lc_queue_t));
bzero(p, sizeof(lc_queue_t));
// 2、申请成功，给堆内存空间进行赋值
if ( p != NULL )
{
// a、申请头节点内存
node_p head_node = malloc(sizeof(node_t));
bzero(head_node, sizeof(node_t));
if (head_node != NULL)
{
// 数据域
// 指针域
head_node->next_p = head_node;
}
else
{
free(p);
return NULL;
}
// b、队头指针
p->front_p = head_node;
// c、队尾指针
p->rear_p = head_node;
// d、链式队列当前元素个数
p->num = 0;
}
else
{
return NULL;
}
// 3、成功返回指向链式队列管理结构体的指针
return p;
}
3、初始化数据节点
- 说明：队列是一种先进先出（FIFO）的线性数据结构，初始化数据节点是构建队列的基础操作。数据节点通常包含存储的数据和指向下一个节点的指针。
- 图解
- 示例代码
/**
* @brief： 初始化数据节点
* @note： None
* @param： data：要赋值的数据
* @retval: 成功：返回指向这个数据节点的指针
* 失败：返回NULL
*/
node_p LINK_CIR_QUEUE_InitDataNode(datatype data)
{
// 1、给数据节点申请堆内存空间
node_p p = malloc(sizeof(node_t));
bzero(p, sizeof(node_t));
// 2、给堆内存空间赋值
if (p!=NULL)
{
// 数据域
p->data = data;
// 指针域
p->next_p = p;
}
// 3、成功返回指向这个数据节点的指针
return p;
}
4、判断队列是否为空
- 说明：循环队列为空的条件是队头指针（front）等于队尾指针（rear）。此时队列中没有元素，两个指针指向同一位置。
- 图解
- 示例代码
/**
* @brief： 判断链式队列是否为空
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* @retval: 如果链式队列为空：返回true
* 如果链式队列非空：返回false
*/
bool LINK_CIR_QUEUE_IfEmpty(lc_queue_p p)
{
// 方法一：
// 管理结构体里面的front_p
node_p head_node = p->front_p;
return head_node->next_p == head_node;
/*
// 方法二：
// 管理结构体里面的rear_p
node_p head_node = p->rear_p;
return head_node->next_p == head_node;
*/
/*
// 方法三：利用管理结构体里面的num
return p->num == 0
*/
}
5、入队(增加数据)
- 说明：链式队列的入队操作需动态申请新节点，存储数据后插入队尾；创建新节点，存入待插入数据，其
next指针置空。若队列为空，新节点同时作为队头和队尾。若队列非空，将队尾节点的next指向新节点，并更新队尾指针。 - 图解
- 示例代码
/**
* @brief： 入队 --- 插入数据(尾插法)
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* new_node：要插入的数据节点
* @retval: None
*/
void LINK_CIR_QUEUE_EnQueue(lc_queue_p p, node_p new_node)
{
// 让队头指针赋值为head_node
node_p head_node = p->front_p;
// 1、让p->rear_p的next_p指向新节点
p->rear_p->next_p = new_node;
// 2、再让new_node的next_p指向head_node
new_node->next_p = head_node;
// 3、让p->rear_p指向最后一个数据节点
p->rear_p = new_node;
// 4、将管理结构体的num+1
p->num++;
}
6、出队(删除数据)
- 说明：队列的出队操作遵循先进先出（FIFO）原则，从队列前端移除元素。在数组实现中，移动队首指针；链表实现中，调整头节点指针。若队列为空，则触发下溢错误。
- 图解
- 示例代码
/**
* @brief： 出队 --- 删除数据
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* @retval: 成功：返回0
* 失败：返回-1
*/
int LINK_CIR_QUEUE_OutQueue(lc_queue_p p)
{
// 1、判断链式队列是否为空，是的话，返回-1
if (LINK_CIR_QUEUE_IfEmpty(p))
return -1;
// 管理结构体里面的队头指针给赋值为head_node
node_p head_node = p->front_p;
// 2、相关中间变量赋值
node_p last_node = head_node;
node_p del_node = head_node->next_p;
node_p next_node = del_node->next_p;
// 3、绕过原链表要删除的节点
last_node->next_p = next_node;
// 4、释放要删除节点的资源
del_node->next_p = NULL;
free(del_node);
// 5、管理结构体中的num需要-1
p->num--;
// 6、删除到链式栈最后一个数据节点时，需要将rear_p指针指向头节点
if (p->num == 0)
{
p->rear_p = p->front_p;
}
// 6、成功返回0
return 0;
}
7、遍历数据
- 说明：从头到尾遍历一遍，将数据打印输出出来即可
- 图解
- 示例代码
/**
* @brief： 遍历整个链式队列并打印出里面的数据
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* @retval: 成功：返回0
* 失败：返回-1
*/
int LINK_CIR_QUEUE_Show(lc_queue_p p)
{
// 1、判断链式栈是否为空，是的话，返回-1
if (LINK_CIR_QUEUE_IfEmpty(p))
return -1;
// 2、遍历整个链式栈，并逐个打印里面的数据
node_p tmp_p = NULL;
int i = 0;
printf("=====================链式栈中的数据===================\n");
for (tmp_p = p->front_p->next_p; tmp_p!=p->rear_p->next_p; tmp_p=tmp_p->next_p)
{
printf("链式栈中的第%d的节点，数据为：%d\n", i, tmp_p->data.data);
i++;
}
printf("====================================================\n");
// 3、成功返回0
return 0;
}
8、获取和修改队头数据
- 说明：在循环队列中，队头数据通常存储在
front指针指向的位置。若队列非空，直接返回该位置的元素即可。 - 图解
- 示例代码
/**
* @brief： 获取队头数据
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* @retval: 成功：返回指向队列队头的数据节点的指针
* 失败：返回NULL
*/
datatype_p LINK_CIR_QUEUE_GetFrontData(lc_queue_p p)
{
// 1、判断链式队列是否为空，是的话，返回-1
if (LINK_CIR_QUEUE_IfEmpty(p))
return NULL;
// 将管理结构体里面的front_p指针进行赋值
node_p head_node = p->front_p;
// 2、获取栈顶数据
return &(head_node->next_p->data);
}
/**
* @brief： 修改队头数据
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* data: 要修改的数据
* @retval: 成功：返回0
* 失败：返回-1
*/
int LINK_CIR_QUEUE_ChangeFrontData(lc_queue_p p, datatype data)
{
// 1、判断链式队列是否为空，是的话，返回-1
if (LINK_CIR_QUEUE_IfEmpty(p))
return -1;
// 将管理结构体里面的front_p指针进行赋值
node_p head_node = p->front_p;
// 2、修改队头数据
head_node->next_p->data = data;
// 3、成功返回0
return 0;
}
9、销毁队列
- 说明：
在循环队列中，队头数据通常存储在
front指针指向的位置。若队列非空，直接返回该位置的元素即可。 - 图解
- 示例代码
/**
* @brief： 销毁链式队列
* @note： None
* @param： p： 指向链式队列管理结构体的指针
* @retval: None
*/
void LINK_CIR_QUEUE_UnInit(lc_queue_p p)
{
// 1、如果链式队列为空，那么直接释放管理结构体内存即可
if (LINK_CIR_QUEUE_IfEmpty(p))
{
free(p->front_p); // 释放堆区2(释放头节点数据)
free(p); // 释放堆区1
return;
}
// 将管理结构体里面的front_p指针进行赋值
node_p head_node = p->front_p;
// 2、销毁链式栈中的数据节点
node_p tmp_p = NULL;
node_p tmp2_p = NULL;
for (tmp_p=head_node->next_p; tmp_p!=head_node; tmp_p=tmp2_p)
{
tmp2_p = tmp_p->next_p;
free(tmp_p);
}
// 3、释放堆区2(释放头节点数据)
free(head_node);
// 4、释放堆区1
free(p);
}
10、循环队列的使用
/**
******************************************************************************
* @file main.c
* @author R.慕青
* @version V0.0.1
* @date 2025.09.25
* @brief 使用链式队列实现数据的增删查改功能
* 前提：需要设置link_cir_queue.h里面的参数
* 环境：ubuntu16.04
* 编译：gcc main.c link_cir_queue.c
* 执行：./a.out
*
******************************************************************************
* @attention
*
* 本文档只供学习使用，不得商用，违者必究
*
* 个人博客网： https://blog.csdn.net/2402_83622972?spm=1010.2135.3001.5343
* 有疑问或者建议：3211735057@qq.com
*
******************************************************************************
*/
#include "link_cir_queue.h"
int main(int argc, char const *argv[])
{
// (1)、初始化管理结构体
lc_queue_p p = LINK_CIR_QUEUE_Init();
if ( p == NULL)
{
printf("初始化链式队列管理结构体失败！\n");
return -1;
}
// (2)、选择功能(增删查改、退出(销毁链式队列))
node_p new_node = NULL;
int select = 0;
datatype new_data = {0};
datatype_p get_data = NULL;
datatype change_data = {0};
while (1)
{
// 1、显示整个链式队列的数据
LINK_CIR_QUEUE_Show(p);
// 2、显示功能选项
printf("请输入以下功能：\n");
printf("1、入队(增加数据)\n");
printf("2、出队(删除数据)\n");
printf("3、获取队头数据\n");
printf("4、修改队头数据\n");
printf("5、退出!\n");
// 3、选择要做的功能
scanf("%d", &select);
while(getchar()!='\n');
switch (select)
{
case 1:
// 提示
printf("请输入要入队的数据：\n");
// 输入数据
scanf("%d", &new_data.data);
while(getchar()!='\n');
// 生成一个数据节点
new_node = LINK_CIR_QUEUE_InitDataNode(new_data);
// 将新生成的数据节点添加到链式队列中
LINK_CIR_QUEUE_EnQueue(p, new_node);
break;
case 2:
// 删除链式队列中的数据(队头)
LINK_CIR_QUEUE_OutQueue(p);
break;
case 3:
// 提示
printf("正在获取队头数据\n");
// 获取队头数据
get_data = LINK_CIR_QUEUE_GetFrontData(p);
if (get_data != NULL)
printf("get_data.data == %d\n", get_data->data);
break;
case 4:
// 提示
printf("请输入要修改的队头数据\n");
// 输入数据
scanf("%d", &change_data.data);
while(getchar()!='\n');
// 修改队头的数据
LINK_CIR_QUEUE_ChangeFrontData(p, change_data);
break;
case 5:
LINK_CIR_QUEUE_UnInit(p);
printf("系统已退出!\n");
goto exit_sys_label;
break;
}
}
exit_sys_label:
return 0;
}
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
31
0- 0
已为社区贡献3条内容
所有评论(0)