一、队列的介绍
① 队列： 一种线性存储结构，允许在一端（队尾）插入数据，在另一端（队头）删除数据。
② 队列主要特点：
- 插入操作（入队）在队尾进行
- 删除操作（出队）在队头进行
- 先进先出（FIFO，First In First Out）
③ 用处：一般用于缓存数据
二、队列的两种存储结构
2.1 顺序队列（基于数组实现）
2.1.1普通顺序队列（线性队列）
① 底层结构：采用线性存储结构，一段连续的内存空间（数组），需要预分配内存空间。
② 核心属性：通过两个指针/下标进行管理——head（队头）和 tail（队尾）。
③ 操作逻辑：
- 入队（队尾）：先存储数据，再移动 tail 指针
- 出队（队头）：先取出数据，再移动 head 指针
④ 缺点：存在“假溢出”问题——当 tail 到达数组末尾时，即使 head 之前的位置已空闲（队尾已满但队头还有空位，因出队操作仅移动 head 而不调整数据），队列仍无法继续入队。
⑤ 解决方案：采用循环队列，将数组逻辑上首尾相连。当 tail 到达数组末端时，自动跳转至数组头部继续利用空闲空间，从而提升存储效率。
2.1.2循环顺序队列
① 循环队列：是顺序队列的一种具体实现方案，目的是解决普通顺序队列的“假溢出”问题。
② 在循环队列中，
head和tail的约定：
head：指向队头元素的位置
tail：指向队尾元素的下一个位置
③ 特点：逻辑上将数组首尾相连，通过取模运算（
%）让指针循环移动。
- 入队（存入数据）：tail
= (tail+ 1) %容量- 出队（取出数据）：head
= (head+ 1) % 容量- 空队列：队头和队尾在同一位置
- 满队列：队列少存储一个数据，当队尾+1跟上队头
④ 两种判空/判满实现方式：
实现方式 判空条件 判满条件 空间利用率 牺牲单元法 head ==tail （ tail + 1 ）% 容量==head 浪费 1 个空间 计数器法 size == 0 size ==容量 100% 利用
2.2 链式队列（基于链表实现）
① 底层结构：采用单链表实现（内存空间非连续分配）。
② 核心属性：维护两个指针——phead（指向队头元素节点）和 ptail（指向队尾元素节点）。
③ 操作逻辑：
- 入队操作：在链表尾部追加新节点，并更新 ptail 指针指向新节点
- 出队操作：移除链表头部节点，并将 phead 指针后移指向下一节点
④ 优点：支持动态扩容，避免"假溢出"现象；入队/出队操作时间复杂度均为 O(1)
⑤ 缺点：每个节点需额外存储指针，存在内存开销
三、链式队列实现
3.1 链式队列的对象和节点声明
typedef int DataType_t; //声明链式队列节点 typedef struct node { DataType_t data; struct node *pnext; }LQNode_t; //声明链式队列对象 typedef struct linkqueue { LQNode_t *phead; LQNode_t *ptail; int clen; }LQueue_t;
3.2 创建链式队列对象
//创建链式队列对象 LQueue_t *create_linkqueue() { //在堆区动态分配一个 LQueue_t 类型结构体的内存空间 LQueue_t *pque = malloc(sizeof(LQueue_t)); if (NULL == pque) //检查 malloc 是否成功 { printf("malloc error\n"); return NULL; } pque->phead = NULL; //头指针置空，表示队列无节点 pque->ptail = NULL; //尾指针置空，表示队列无节点 pque->clen = 0;//队列长度为0 return pque; }
3.3 创建链式队列节点
//创建链式队列节点 LQNode_t *create_node(DataType_t data) { LQNode_t *pnode = malloc(sizeof(LQNode_t)); if (NULL == pnode) { printf("malloc error\n"); return NULL; } //将传入的数据存储到节点的 data 字段 pnode->data = data; //值传递，数据被复制到节点中 pnode->pnext = NULL; //将下一个节点指针置 NULL return pnode; }
3.4 判断链式队列为空
//链式队列判空 int is_empty_linkqueue(LQueue_t *pque) { //返回 1（真），队列为空； 返回 0（假），队列非空 return NULL == pque->phead; }
3.5 链式队列入队（尾插）
- 空队列状态：头指针和尾指针均指向同一节点
- 非空队列状态：将新节点插入当前尾节点之后，并将尾指针移至新节点（采用尾插法）
//链式队列入队，在队尾插入新元素 int push_linkqueue(LQueue_t *pque, DataType_t data) { LQNode_t *pnode = create_node(data); //调用 create_node 创建新节点 if (NULL == pnode) { return -1; } if (is_empty_linkqueue(pque)) //判空并插入 { //如果是空队列，头尾指针都指向同一个节点 pque->phead = pnode; // 头指针指向新节点 pque->ptail = pnode; // 尾指针指向新节点 } else //非空队列 { pque->ptail->pnext = pnode; // 当前尾节点指向新节点 pque->ptail = pnode; // 更新尾指针 } pque->clen++; //更新队列长度 return 0; }
3.6 链式队列出队（头删）
- 队列中有多个数据节点：删除头节点后需要正确更新头指针
- 队列中只有一个数据节点：删除后头指针变为
NULL，说明队列已经空了，此时需要将尾指针也置为NULL//从链式队列头部移除一个节点，并将节点中的数据通过指针参数返回。 int pop_linkqueue(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) //判断队列是否为空 { return -1; } LQNode_t *ptmp = pque->phead; //用临时指针 ptmp 保存队头节点的地址 pque->phead = ptmp->pnext;//更新头指针，将头指针指向第二个节点 //如果删除后头指针变为 NULL，说明队列已经空了 if (NULL == pque->phead) { pque->ptail = NULL; //将尾指针也置为 NULL } if (pdata != NULL) { //如果 pdata 不为 NULL，将节点数据复制到 pdata 指向的内存 //如果调用者不需要数据，可以传入 NULL（只删除不出队） *pdata = ptmp->data; } free(ptmp); //释放已移除节点的内存，防止内存泄漏 ptmp = NULL; // 置空，防止野指针 pque->clen--; //更新队列长度 return 0; }
3.7 遍历链式队列
//遍历链式队列，用于打印队列中所有元素 void show_linkqueue(LQueue_t *pque) { //创建临时指针 ptmp，指向队头节点，遍历的起点 LQNode_t *ptmp = pque->phead; while (ptmp != NULL) //未到达队尾 { printf("%d ", ptmp->data); ptmp = ptmp->pnext; } printf("\n"); }
3.8 获取链式队列队头元素的数据
//获取链式队列队头元素的数据，但不删除该节点（只读操作） int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) //判断队列是否为空 { return -1; } if (pdata != NULL) { //如果 pdata 不为 NULL，将队头节点的数据复制到 pdata 指向的内存 *pdata = pque->phead->data; } return 0; }
3.9 销毁链式队列
使用一级指针，只修改了局部变量，调用者的指针不变！
//完全销毁一个链式队列，释放所有节点和队列结构体的内存，并将指针置空 void destroy_linkqueue(LQueue_t **ppque) //二级指针（指向队列指针的指针） { while (!is_empty_linkqueue(*ppque)) //队列不为空 { //每次删除一个节点，直到队列为空，传入 NULL 表示不返回数据，只删除 pop_linkqueue(*ppque, NULL); //反复调用 pop_linkqueue 删除队头节点 } free(*ppque); //释放队列控制结构体（LQueue_t）占用的内存 *ppque = NULL; //将调用者的队列指针置为 NULL } //调用 destroy_linkqueue(&pque);
3.10 附件代码
① linkqueue.h
#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ typedef int DataType_t; typedef struct node { DataType_t data; struct node *pnext; }LQNode_t; typedef struct linkqueue { LQNode_t *phead; LQNode_t *ptail; int clen; }LQueue_t; extern LQueue_t *create_linkqueue(); extern LQNode_t *create_node(DataType_t data); extern int is_empty_linkqueue(LQueue_t *pque); extern int push_linkqueue(LQueue_t *pque, DataType_t data); extern void show_linkqueue(LQueue_t *pque); extern int pop_linkqueue(LQueue_t *pque, DataType_t *pdata); extern int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata); extern void destroy_linkqueue(LQueue_t **ppque); #endif② linkqueue.c
#include "linkqueue.h" #include <stdio.h> #include <stdlib.h> LQueue_t *create_linkqueue() { LQueue_t *pque = malloc(sizeof(LQueue_t)); if (NULL == pque) { printf("malloc error\n"); return NULL; } pque->phead = NULL; pque->ptail = NULL; pque->clen = 0; return pque; } LQNode_t *create_node(DataType_t data) { LQNode_t *pnode = malloc(sizeof(LQNode_t)); if (NULL == pnode) { printf("malloc error\n"); return NULL; } pnode->data = data; pnode->pnext = NULL; return pnode; } int is_empty_linkqueue(LQueue_t *pque) { return NULL == pque->phead; } int push_linkqueue(LQueue_t *pque, DataType_t data) { LQNode_t *pnode = create_node(data); if (NULL == pnode) { return -1; } if (is_empty_linkqueue(pque)) { pque->phead = pnode; pque->ptail = pnode; } else { pque->ptail->pnext = pnode; pque->ptail = pnode; } pque->clen++; return 0; } void show_linkqueue(LQueue_t *pque) { LQNode_t *ptmp = pque->phead; while (ptmp != NULL) { printf("%d ", ptmp->data); ptmp = ptmp->pnext; } printf("\n"); } int pop_linkqueue(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } LQNode_t *ptmp = pque->phead; pque->phead = ptmp->pnext; if (NULL == pque->phead) { pque->ptail = NULL; } if (pdata != NULL) { *pdata = ptmp->data; } free(ptmp); pque->clen--; return 0; } int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } if (pdata != NULL) { *pdata = pque->phead->data; } return 0; } void destroy_linkqueue(LQueue_t **ppque) { while (!is_empty_linkqueue(*ppque)) { pop_linkqueue(*ppque, NULL); } free(*ppque); *ppque = NULL; }③ main.c
#include "linkqueue.h" #include <stdio.h> int main(int argc, const char *argv[]) { LQueue_t *pque = NULL; DataType_t data; pque = create_linkqueue(); if (NULL == pque) { return -1; } push_linkqueue(pque, 1); push_linkqueue(pque, 2); push_linkqueue(pque, 3); push_linkqueue(pque, 4); push_linkqueue(pque, 5); show_linkqueue(pque); int ret = pop_linkqueue(pque, &data); if (0 == ret) { printf("pop data : %d\n", data); } show_linkqueue(pque); ret = get_linkqueue_head(pque, &data); if (0 == ret) { printf("head data : %d\n", data); } destroy_linkqueue(&pque); return 0; }
四、循环队列实现
4.1 循环队列的对象声明
//声明循环队列的对象 typedef int DataType_t; //将 int 类型重命名为 DataType_t typedef struct sque { DataType_t *pbase; // 指向动态数组的指针（存储数据） int head; // 队头索引 int tail; // 队尾索引 }SQueue_t;
4.2 创建循环队列对象
//创建一个循环队列，分配结构体内存和存储数据的内存，并初始化为空队列 SQueue_t *create_sysqueue() { SQueue_t *psque = malloc(sizeof(SQueue_t));//在堆区为队列结构体分配内存 if (NULL == psque) { printf("malloc error\n"); return NULL; } //为数据存储区分配动态数组 psque->pbase = malloc(sizeof(DataType_t) * MAX_QUEUE_LEN); if (NULL == psque->pbase) { printf("malloc error\n"); return NULL; } psque->head = 0; //队头索引初始化为 0 psque->tail = 0; //队尾索引初始化为 0 return psque; } //分配数据区后 栈：psque → 0x1000 堆：0x1000 [SQueue_t结构体] ├─ pbase: 0x2000 ├─ head: 0 └─ tail: 0 堆：0x2000 [数据区] ← 可存储 MAX_QUEUE_LEN 个元素
4.3 循环队列判满
//判断顺序循环队列是否已满，返回1表示已满，0表示未满。 int is_full_sysqueue(SQueue_t *psque) { //在循环队列中，当尾指针的下一个位置等于头指针时，表示队列已满 if (((psque->tail + 1) % MAX_QUEUE_LEN) == psque->head) { return 1; } return 0; }
4.4 循环队列判空
//判断顺序循环队列是否为空，返回1表示为空，0表示非空。 int is_empty_sysqueue(SQueue_t *psque) { //当头指针和尾指针重合时，表示队列中没有元素 if (psque->head == psque->tail) { return 1; } return 0; }
4.5 循环队列入队
//向顺序循环队列中插入一个元素（入队操作），如果队列已满则返回错误 int push_sysqueue(SQueue_t *psque, DataType_t data) { if (is_full_sysqueue(psque)) //判断队列是否已满，防止数据覆盖或缓冲区溢出 { return -1; } //使用 tail 作为索引，将数据存入数组，tail 指向当前队尾的下一个位置（空闲位置） psque->pbase[psque->tail] = data; //更新尾指针（循环） psque->tail = (psque->tail+1) % MAX_QUEUE_LEN; return 0; } //psque->tail = (psque->tail+1) % MAX_QUEUE_LEN; 核心操作：tail 后移一位 (tail + 1) % MAX_QUEUE_LEN：实现循环 当 tail 到达数组末尾时，自动回到开头 // 1.初始状态 （空队列，容量为8） 索引: 0 1 2 3 4 5 6 7 [ ][ ][ ][ ][ ][ ][ ][ ] ↑ head=0, tail=0 2.入队元素10 pbase[tail] = 10; // pbase[0] = 10 tail = (0+1) % 8; // tail = 1 索引: 0 1 2 3 4 5 6 7 [10][ ][ ][ ][ ][ ][ ][ ] ↑ ↑ head=0 tail=1
4.6 循环队列出队
//从顺序循环队列头部移除一个元素，并通过指针参数返回其数据。 int pop_sysqueue(SQueue_t *psque, DataType_t *pdata) { //判断队列是否为空，防止对空队列进行操作 if (is_empty_sysqueue(psque)) { return -1; } if (pdata != NULL) //检查输出指针是否有效 { //如果 pdata 不为 NULL，将队头数据复制到 pdata 指向的内存 *pdata = psque->pbase[psque->head]; } //更新头指针（循环） psque->head = (psque->head + 1) % MAX_QUEUE_LEN; return 0; } //psque->head = (psque->head + 1) % MAX_QUEUE_LEN; 核心操作：head 后移一位 (head + 1) % MAX_QUEUE_LEN：实现循环 当 head 到达数组末尾时，自动回到开头 1.初始状态（3个元素，容量为8） 索引: 0 1 2 3 4 5 6 7 [10][20][30][ ][ ][ ][ ][ ] ↑ ↑ head=0 tail=3 2.出队元素10 // 如果 pdata != NULL，返回 pbase[0] = 10 head = (0 + 1) % 8; // head = 1 索引: 0 1 2 3 4 5 6 7 [10][20][30][ ][ ][ ][ ][ ] ↑ ↑ head=1 tail=3 (逻辑上10已被删除)
4.7 遍历循环队列
//遍历顺序循环队列，从头到尾打印所有有效元素。 void show_sysqueue(SQueue_t *psque) { for (int i = psque->head; i != psque->tail; i = (i+1)%MAX_QUEUE_LEN) { printf("%d ", psque->pbase[i]); } printf("\n"); } 初始化：i = psque->head - 从队头开始 循环条件：i != psque->tail - 未到达队尾 迭代：i = (i+1) % MAX_QUEUE_LEN - 循环后移
4.8 清空循环队列
//清空顺序循环队列，使队列回到初始空状态。 void clear_sysqueue(SQueue_t *psque) { psque->head = psque->tail = 0; }
4.9 销毁循环队列
void destroy_sysqueue(SQueue_t **ppsque) //二级指针（指向队列指针的指针） { //(*ppsque)解引用得到队列结构体指针 free((*ppsque)->pbase); //释放动态分配的数据存储区（数组） free(*ppsque); //释放队列结构体本身 *ppsque = NULL; //将调用者的队列指针置为 NULL，防止野指针 } //调用 destroy_sysqueue(&psque);
4.10 附件代码
① sysqueue.h
#ifndef __SYSQUEUE_H__ #define __SYSQUEUE_H__ typedef int DataType_t; typedef struct sque { DataType_t *pbase; int head; int tail; }SQueue_t; #define MAX_QUEUE_LEN 6 extern SQueue_t *create_sysqueue(); extern int is_full_sysqueue(SQueue_t *psque); extern int push_sysqueue(SQueue_t *psque, DataType_t data); extern void show_sysqueue(SQueue_t *psque); extern int pop_sysqueue(SQueue_t *psque, DataType_t *pdata); extern void destroy_sysqueue(SQueue_t **ppsque); extern void clear_sysqueue(SQueue_t *psque); #endif② sysqueue.c
#include "sysqueue.h" #include <stdio.h> #include <stdlib.h> SQueue_t *create_sysqueue() { SQueue_t *psque = malloc(sizeof(SQueue_t)); if (NULL == psque) { printf("malloc error\n"); return NULL; } psque->pbase = malloc(sizeof(DataType_t) * MAX_QUEUE_LEN); if (NULL == psque->pbase) { printf("malloc error\n"); return NULL; } psque->head = 0; psque->tail = 0; return psque; } int is_full_sysqueue(SQueue_t *psque) { if (((psque->tail + 1) % MAX_QUEUE_LEN) == psque->head) { return 1; } return 0; } int is_empty_sysqueue(SQueue_t *psque) { if (psque->head == psque->tail) { return 1; } return 0; } int push_sysqueue(SQueue_t *psque, DataType_t data) { if (is_full_sysqueue(psque)) { return -1; } psque->pbase[psque->tail] = data; psque->tail = (psque->tail+1) % MAX_QUEUE_LEN; return 0; } void show_sysqueue(SQueue_t *psque) { for (int i = psque->head; i != psque->tail; i = (i+1)%MAX_QUEUE_LEN) { printf("%d ", psque->pbase[i]); } printf("\n"); } int pop_sysqueue(SQueue_t *psque, DataType_t *pdata) { if (is_empty_sysqueue(psque)) { return -1; } if (pdata != NULL) { *pdata = psque->pbase[psque->head]; } psque->head = (psque->head + 1) % MAX_QUEUE_LEN; return 0; } void clear_sysqueue(SQueue_t *psque) { psque->head = psque->tail = 0; } void destroy_sysqueue(SQueue_t **ppsque) { free((*ppsque)->pbase); free(*ppsque); *ppsque = NULL; }③ main.c
#include "sysqueue.h" #include <stdio.h> int main(int argc, const char *argv[]) { SQueue_t *psque = NULL; DataType_t data; psque = create_sysqueue(); if (NULL == psque) { return -1; } push_sysqueue(psque, 1); push_sysqueue(psque, 2); push_sysqueue(psque, 3); push_sysqueue(psque, 4); push_sysqueue(psque, 5); show_sysqueue(psque); pop_sysqueue(psque, &data); push_sysqueue(psque, 6); show_sysqueue(psque); clear_sysqueue(psque); destroy_sysqueue(&psque); return 0; }
