当前位置： 首页 > ops >正文

数据结构基础之队列：数组/链表

ops 2025/9/6 12:53:48

一、队列是什么？—— 从生活到技术的 “先进先出” 模型

        队列（Queue）是一种遵循 “先进先出”（First In First Out, FIFO） 规则的线性数据结构，类比生活中 “排队买票” 的场景：先排队的人先买票，后排队的人后处理，不允许 “插队” 或 “提前离开”。

在技术场景中，队列的核心特性可概括为：

  • 两端操作限制：仅允许在 “队头（Front）” 取出元素（出队），在 “队尾（Rear）” 添加元素（入队）；
  • 顺序严格性：元素的处理顺序与添加顺序完全一致，无优先级反转；
  • 抽象数据类型：需支持 初始化（init）、入队（enqueue）、出队（dequeue）、判空（is_empty）、销毁（destroy） 等基础操作。

二、队列的两种经典实现 —— 数组 vs 链表

C/C++ 中无原生队列结构，需基于数组或链表手动实现，两种方式各有优劣，需根据场景选择。

1. 数组实现：循环队列（解决 “假溢出” 问题）

       普通数组队列存在 “假溢出” 缺陷 —— 队尾已达数组末尾，但队头前仍有空闲空间。循环队列通过 “取模运算” 将数组首尾相连，让空间循环利用，是数组队列的最优实现。

（1）数据结构定义
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义队列元素类型（可根据需求修改，如int、结构体）
typedef int QueueData;// 循环队列结构体
typedef struct {QueueData* data;   // 存储元素的数组int front;         // 队头索引（指向第一个元素）int rear;          // 队尾索引（指向最后一个元素的下一个位置）int max_size;      // 队列最大容量
} CircularQueue;

关键设计：数组容量设为 max_size + 1，用 “(rear + 1) % (max_size + 1) == front” 判断队列满，避免与空队列（front == rear）混淆。

（2）核心操作实现
① 初始化队列
// 初始化循环队列，max_size为最大容量
CircularQueue* queue_init(int max_size) {// 申请队列结构体内存CircularQueue* q = (CircularQueue*)malloc(sizeof(CircularQueue));if (q == NULL) {printf("队列内存分配失败！\n");return NULL;}// 申请元素数组内存（预留1个空位区分空/满）q->data = (QueueData*)malloc(sizeof(QueueData) * (max_size + 1));if (q->data == NULL) {printf("元素数组内存分配失败！\n");free(q);  // 释放已分配的结构体return NULL;}q->front = 0;q->rear = 0;q->max_size = max_size;return q;
}
② 判空与判满
// 判断队列是否为空
bool queue_is_empty(CircularQueue* q) {if (q == NULL) return true;return q->front == q->rear;  // 空队列标志：队头=队尾
}// 判断队列是否已满
bool queue_is_full(CircularQueue* q) {if (q == NULL) return false;// 满队列标志：队尾下一个位置=队头（取模实现循环）return (q->rear + 1) % (q->max_size + 1) == q->front;
}
③ 入队（添加元素）
// 入队：将data添加到队尾，成功返回true，失败（满）返回false
bool queue_enqueue(CircularQueue* q, QueueData data) {if (q == NULL || queue_is_full(q)) {printf("队列已满或未初始化，入队失败！\n");return false;}q->data[q->rear] = data;                // 元素存入队尾q->rear = (q->rear + 1) % (q->max_size + 1);  // 队尾循环后移return true;
}
④ 出队（取出元素）
// 出队：从队头取出元素存入*data，成功返回true，失败（空）返回false
bool queue_dequeue(CircularQueue* q, QueueData* data) {if (q == NULL || queue_is_empty(q) || data == NULL) {printf("队列为空、未初始化或指针无效，出队失败！\n");return false;}*data = q->data[q->front];              // 取出队头元素q->front = (q->front + 1) % (q->max_size + 1);  // 队头循环后移return true;
}
⑤ 销毁队列（避免内存泄漏）
// 销毁队列，释放所有内存
void queue_destroy(CircularQueue* q) {if (q != NULL) {if (q->data != NULL) {free(q->data);  // 先释放元素数组}free(q);  // 再释放队列结构体}
}
（3）使用示例
int main() {CircularQueue* q = queue_init(5);  // 初始化容量为5的队列if (q == NULL) return 1;// 入队：10、20、30queue_enqueue(q, 10);queue_enqueue(q, 20);queue_enqueue(q, 30);// 出队并打印QueueData val;while (!queue_is_empty(q)) {queue_dequeue(q, &val);printf("出队元素：%d\n", val);  // 输出：10 → 20 → 30}queue_destroy(q);  // 销毁队列return 0;
}

2. 链表实现：动态队列（无容量限制）

链表队列用节点存储元素，通过指针连接节点，容量可动态扩展，无需提前指定大小，适合元素数量不确定的场景。

（1）数据结构定义
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int QueueData;// 链表节点结构体
typedef struct QueueNode {QueueData data;          // 节点存储的元素struct QueueNode* next;  // 指向后一个节点的指针
} QueueNode;// 链表队列结构体
typedef struct {QueueNode* front;  // 队头指针（指向第一个节点）QueueNode* rear;   // 队尾指针（指向最后一个节点）int size;          // 队列元素个数（可选，方便快速查询）
} LinkedQueue;
（2）核心操作实现
① 初始化队列

c

运行

LinkedQueue* linked_queue_init() {LinkedQueue* q = (LinkedQueue*)malloc(sizeof(LinkedQueue));if (q == NULL) {printf("队列内存分配失败！\n");return NULL;}q->front = NULL;q->rear = NULL;q->size = 0;return q;
}
② 入队（创建新节点）
bool linked_queue_enqueue(LinkedQueue* q, QueueData data) {if (q == NULL) {printf("队列未初始化，入队失败！\n");return false;}// 1. 创建新节点QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));if (new_node == NULL) {printf("节点内存分配失败，入队失败！\n");return false;}new_node->data = data;new_node->next = NULL;  // 队尾节点next为NULL// 2. 插入队列（空队列 vs 非空队列）if (q->size == 0) {q->front = new_node;  // 空队列：队头=队尾=新节点q->rear = new_node;} else {q->rear->next = new_node;  // 非空队列：队尾next指向新节点q->rear = new_node;        // 更新队尾}q->size++;return true;
}
③ 出队（删除队头节点）
bool linked_queue_dequeue(LinkedQueue* q, QueueData* data) {if (q == NULL || q->size == 0 || data == NULL) {printf("队列为空、未初始化或指针无效，出队失败！\n");return false;}// 1. 保存队头节点和数据QueueNode* temp = q->front;*data = temp->data;// 2. 更新队头（仅一个节点 vs 多个节点）if (q->front == q->rear) {q->front = NULL;  // 仅一个节点：出队后队列为空q->rear = NULL;} else {q->front = q->front->next;  // 多个节点：队头后移}// 3. 释放原队头节点内存free(temp);q->size--;return true;
}
④ 销毁队列（遍历释放节点）
void linked_queue_destroy(LinkedQueue* q) {if (q == NULL) return;// 遍历所有节点，逐个释放QueueNode* current = q->front;while (current != NULL) {QueueNode* temp = current;current = current->next;free(temp);}free(q);  // 释放队列结构体
}

三、两种实现方式对比 —— 如何选择？

对比维度数组队列（循环）链表队列（动态）
容量限制固定容量（需提前指定）动态扩展（无限制）
时间复杂度入队 / 出队均为 O (1)入队 / 出队均为 O (1)
空间复杂度O (n)（预分配数组）O (n)（仅存储实际元素）
访问效率随机访问快（数组特性）需遍历访问（指针跳转）
适用场景已知最大容量、高频访问容量不确定、频繁增减元素

四、队列的典型应用场景

队列的 FIFO 特性使其在 “顺序处理”“缓冲平衡” 场景中不可或缺，常见应用包括：

1. 任务调度（操作系统）

  • 操作系统的 “进程调度”“线程池任务队列”：按任务提交顺序依次执行，避免优先级反转（普通队列）；
  • 打印队列：多任务共享打印机时，按请求顺序排队打印，防止文档混乱。

2. 数据缓冲（通信 / IO）

  • 串口 / 网络通信：接收端用队列暂存流式数据，平衡 “数据接收速率” 与 “解析速率”，避免数据丢失；
  • 磁盘 IO 缓冲：将多次小 IO 请求合并为一次大请求，用队列暂存请求，提升 IO 效率。

3. 算法辅助（BFS / 层次遍历）

  • 广度优先搜索（BFS）：在图 / 树的遍历中，用队列存储 “待访问节点”，确保按层次顺序遍历（如迷宫最短路径、二叉树层次遍历）；
  • 滑动窗口：用队列维护窗口内的元素，实现窗口滑动时的快速添加 / 删除（如 “无重复字符的最长子串” 问题）。

4. 生产者 - 消费者模型

  • 多线程编程中，“生产者” 线程生产数据并入队，“消费者” 线程从队列取数据并处理，队列作为 “数据枢纽”，解耦生产者与消费者，平衡两者速率。

五、常见问题与注意事项

  1. 内存泄漏风险：

    • 数组队列：销毁时需先释放 data 数组，再释放队列结构体；
    • 链表队列：必须遍历所有节点释放内存，避免仅释放结构体导致节点内存泄漏。

  2. 循环队列的 “空 / 满” 判断：

    • 务必预留 1 个空位，用 (rear+1)%(max_size+1) == front 判断满，否则无法区分空和满。

  3. 线程安全问题：

    • 多线程环境下，队列的入队 / 出队操作需加互斥锁（如 C++ 的 std::mutex），避免并发访问导致的数据错乱。

五、进阶示例：

基础字符串链表队列（动态内存管理 + 安全操作）

1. 数据结构定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>// 链表节点：存储动态字符串
typedef struct StrQueueNode {char* str;                  // 动态分配的字符串（需手动释放）struct StrQueueNode* next;  // 指向下一节点的指针
} StrQueueNode;// 队列结构体：维护队头、队尾及元素个数
typedef struct {StrQueueNode* front;  // 队头指针StrQueueNode* rear;   // 队尾指针int size;             // 队列元素个数（O(1)获取长度）
} StrLinkedQueue;

2. 核心操作实现

（1）队列初始化
// 初始化空队列，返回队列指针（失败返回NULL）
StrLinkedQueue* str_queue_init() {StrLinkedQueue* q = (StrLinkedQueue*)malloc(sizeof(StrLinkedQueue));if (q == NULL) {perror("str_queue_init: 队列内存分配失败");return NULL;}q->front = NULL;q->rear = NULL;q->size = 0;return q;
}
（2）入队（动态拷贝字符串，避免野指针）
// 字符串入队（str：待入队字符串，非NULL/非空串）
bool str_queue_enqueue(StrLinkedQueue* q, const char* str) {// 入参合法性检查if (q == NULL || str == NULL || strlen(str) == 0) {fprintf(stderr, "str_queue_enqueue: 入参无效\n");return false;}// 1. 拷贝字符串（动态分配内存，独立于原字符串生命周期）int str_len = strlen(str);char* str_copy = (char*)malloc(sizeof(char) * (str_len + 1));if (str_copy == NULL) {perror("str_queue_enqueue: 字符串内存分配失败");return false;}strcpy(str_copy, str);// 2. 创建新节点StrQueueNode* new_node = (StrQueueNode*)malloc(sizeof(StrQueueNode));if (new_node == NULL) {perror("str_queue_enqueue: 节点内存分配失败");free(str_copy);  // 释放已分配的字符串，避免泄漏return false;}new_node->str = str_copy;new_node->next = NULL;// 3. 插入队尾if (q->size == 0) {  // 空队列：队头=队尾=新节点q->front = new_node;q->rear = new_node;} else {  // 非空队列：队尾next指向新节点，更新队尾q->rear->next = new_node;q->rear = new_node;}q->size++;return true;
}
（3）出队（安全拷贝 + 内存释放）
// 字符串出队（out_buf：输出缓冲区，buf_len：缓冲区长度）
bool str_queue_dequeue(StrLinkedQueue* q, char* out_buf, int buf_len) {// 入参合法性检查if (q == NULL || q->size == 0 || out_buf == NULL || buf_len <= 0) {fprintf(stderr, "str_queue_dequeue: 入参无效或队空\n");return false;}// 1. 取出队头节点数据StrQueueNode* temp_node = q->front;char* temp_str = temp_node->str;int str_len = strlen(temp_str);// 2. 检查缓冲区是否足够（需容纳字符串+'\0'）if (buf_len < str_len + 1) {fprintf(stderr, "str_queue_dequeue: 缓冲区不足（需%d字节，仅%d字节）\n", str_len + 1, buf_len);return false;}strcpy(out_buf, temp_str);  // 拷贝到输出缓冲区// 3. 更新队列状态if (q->size == 1) {  // 仅一个节点：出队后队空q->front = NULL;q->rear = NULL;} else {  // 多个节点：队头后移q->front = q->front->next;}// 4. 释放队头节点内存（避免泄漏）free(temp_str);free(temp_node);q->size--;return true;
}
（4）辅助操作
// 获取队列长度
int str_queue_get_size(StrLinkedQueue* q) {return (q == NULL) ? -1 : q->size;
}// 判断队列是否为空
bool str_queue_is_empty(StrLinkedQueue* q) {return (q == NULL || q->size == 0);
}// 清空队列（释放所有节点，保留队列结构体）
void str_queue_clear(StrLinkedQueue* q) {if (q == NULL) return;StrQueueNode* current = q->front;while (current != NULL) {StrQueueNode* temp = current;current = current->next;free(temp->str);  // 先释放字符串free(temp);       // 再释放节点}q->front = NULL;q->rear = NULL;q->size = 0;
}// 销毁队列（释放所有资源，队列不可再用）
void str_queue_destroy(StrLinkedQueue** q) {if (q == NULL || *q == NULL) return;str_queue_clear(*q);free(*q);*q = NULL;  // 置空外部指针，避免野指针
}// 打印队列所有元素（调试用）
void str_queue_print(StrLinkedQueue* q) {if (q == NULL) {fprintf(stderr, "str_queue_print: 队列未初始化\n");return;}if (q->size == 0) {printf("队列空\n");return;}printf("队列元素（%d个）：", q->size);StrQueueNode* current = q->front;while (current != NULL) {printf("\"%s\"", current->str);current = current->next;if (current != NULL) printf(", ");}printf("\n");
}

3. 使用示例

int main() {// 初始化队列StrLinkedQueue* q = str_queue_init();if (q == NULL) return 1;// 入队str_queue_enqueue(q, "hello");str_queue_enqueue(q, "string queue");str_queue_enqueue(q, "advanced");str_queue_print(q);  // 输出：队列元素（3个）："hello", "string queue", "advanced"// 出队char out_buf[32];str_queue_dequeue(q, out_buf, sizeof(out_buf));printf("出队元素：%s\n", out_buf);  // 输出：hellostr_queue_print(q);  // 输出：队列元素（2个）："string queue", "advanced"// 清空+销毁str_queue_clear(q);str_queue_destroy(&q);printf("队列销毁后指针：%s\n", q == NULL ? "NULL" : "非NULL");  // 输出：NULLreturn 0;
}

更高级常用的队列形式

1. 带锁的线程安全字符串队列（多线程场景）

（1）数据结构扩展（增加互斥锁）
#include <pthread.h>typedef struct {StrQueueNode* front;StrQueueNode* rear;int size;pthread_mutex_t mutex;  // 互斥锁：保护队列操作原子性
} ThreadSafeStrQueue;
（2）核心操作（加锁保证线程安全）
// 初始化线程安全队列
ThreadSafeStrQueue* ts_str_queue_init() {ThreadSafeStrQueue* q = (ThreadSafeStrQueue*)malloc(sizeof(ThreadSafeStrQueue));if (q == NULL) {perror("ts_str_queue_init: 队列内存分配失败");return NULL;}q->front = NULL;q->rear = NULL;q->size = 0;// 初始化互斥锁if (pthread_mutex_init(&q->mutex, NULL) != 0) {perror("ts_str_queue_init: 互斥锁初始化失败");free(q);return NULL;}return q;
}// 线程安全入队（加锁+解锁）
bool ts_str_queue_enqueue(ThreadSafeStrQueue* q, const char* str) {if (q == NULL) return false;pthread_mutex_lock(&q->mutex);  // 加锁：独占访问队列// 核心入队逻辑（同基础队列，略）bool ret = false;int str_len = strlen(str);char* str_copy = (char*)malloc(str_len + 1);if (str_copy != NULL) {strcpy(str_copy, str);StrQueueNode* new_node = (StrQueueNode*)malloc(sizeof(StrQueueNode));if (new_node != NULL) {new_node->str = str_copy;new_node->next = NULL;if (q->size == 0) {q->front = new_node;q->rear = new_node;} else {q->rear->next = new_node;q->rear = new_node;}q->size++;ret = true;} else {free(str_copy);}}pthread_mutex_unlock(&q->mutex);  // 解锁：释放队列访问权return ret;
}// 线程安全出队（加锁+解锁）
bool ts_str_queue_dequeue(ThreadSafeStrQueue* q, char* out_buf, int buf_len) {if (q == NULL || out_buf == NULL || buf_len <= 0) return false;pthread_mutex_lock(&q->mutex);bool ret = false;if (q->size > 0) {// 核心出队逻辑（同基础队列，略）StrQueueNode* temp_node = q->front;char* temp_str = temp_node->str;int str_len = strlen(temp_str);if (buf_len >= str_len + 1) {strcpy(out_buf, temp_str);if (q->size == 1) {q->front = NULL;q->rear = NULL;} else {q->front = q->front->next;}free(temp_str);free(temp_node);q->size--;ret = true;}}pthread_mutex_unlock(&q->mutex);return ret;
}// 销毁线程安全队列（需销毁互斥锁）
void ts_str_queue_destroy(ThreadSafeStrQueue** q) {if (q == NULL || *q == NULL) return;pthread_mutex_lock(&(*q)->mutex);// 释放所有节点（同基础队列clear逻辑）StrQueueNode* current = (*q)->front;while (current != NULL) {StrQueueNode* temp = current;current = current->next;free(temp->str);free(temp);}pthread_mutex_unlock(&(*q)->mutex);pthread_mutex_destroy(&(*q)->mutex);  // 销毁互斥锁free(*q);*q = NULL;
}

2. 带超时的阻塞队列（多线程同步场景）

（1）数据结构扩展（增加条件变量）
typedef struct {StrQueueNode* front;StrQueueNode* rear;int size;int max_size;         // 队列最大容量（避免无限扩容）pthread_mutex_t mutex;pthread_cond_t not_empty;  // 非空条件：出队等待pthread_cond_t not_full;   // 非满条件：入队等待
} BlockingStrQueue;
（2）核心操作（条件变量等待 / 唤醒）
// 初始化阻塞队列（max_size：队列最大容量）
BlockingStrQueue* bk_str_queue_init(int max_size) {if (max_size <= 0) return NULL;BlockingStrQueue* q = (BlockingStrQueue*)malloc(sizeof(BlockingStrQueue));if (q == NULL) return NULL;q->front = NULL;q->rear = NULL;q->size = 0;q->max_size = max_size;// 初始化互斥锁和条件变量if (pthread_mutex_init(&q->mutex, NULL) != 0 ||pthread_cond_init(&q->not_empty, NULL) != 0 ||pthread_cond_init(&q->not_full, NULL) != 0) {perror("bk_str_queue_init: 同步对象初始化失败");// 清理已初始化的资源if (pthread_mutex_destroy(&q->mutex) == 0) {pthread_cond_destroy(&q->not_empty);pthread_cond_destroy(&q->not_full);}free(q);return NULL;}return q;
}// 阻塞入队（队列满时等待，超时返回失败，timeout_ms：超时时间（毫秒））
bool bk_str_queue_enqueue(BlockingStrQueue* q, const char* str, int timeout_ms) {if (q == NULL || str == NULL) return false;pthread_mutex_lock(&q->mutex);// 1. 队列满时等待（直到非满或超时）struct timespec ts;if (timeout_ms > 0) {clock_gettime(CLOCK_REALTIME, &ts);ts.tv_sec += timeout_ms / 1000;ts.tv_nsec += (timeout_ms % 1000) * 1000000;if (ts.tv_nsec >= 1000000000) {ts.tv_sec++;ts.tv_nsec -= 1000000000;}}while (q->size >= q->max_size) {int ret;if (timeout_ms <= 0) {// 无限等待：直到not_full条件被唤醒ret = pthread_cond_wait(&q->not_full, &q->mutex);} else {// 超时等待ret = pthread_cond_timedwait(&q->not_full, &q->mutex, &ts);}if (ret != 0) {  // 等待失败（超时或信号中断）pthread_mutex_unlock(&q->mutex);return false;}}// 2. 核心入队逻辑（同基础队列，略）bool ret = false;int str_len = strlen(str);char* str_copy = (char*)malloc(str_len + 1);if (str_copy != NULL) {strcpy(str_copy, str);StrQueueNode* new_node = (StrQueueNode*)malloc(sizeof(StrQueueNode));if (new_node != NULL) {new_node->str = str_copy;new_node->next = NULL;if (q->size == 0) {q->front = new_node;q->rear = new_node;} else {q->rear->next = new_node;q->rear = new_node;}q->size++;ret = true;// 唤醒等待"非空"的出队线程pthread_cond_signal(&q->not_empty);} else {free(str_copy);}}pthread_mutex_unlock(&q->mutex);return ret;
}// 阻塞出队（队列空时等待，超时返回失败）
bool bk_str_queue_dequeue(BlockingStrQueue* q, char* out_buf, int buf_len, int timeout_ms) {if (q == NULL || out_buf == NULL || buf_len <= 0) return false;pthread_mutex_lock(&q->mutex);// 1. 队列空时等待（直到非空或超时）struct timespec ts;if (timeout_ms > 0) {clock_gettime(CLOCK_REALTIME, &ts);ts.tv_sec += timeout_ms / 1000;ts.tv_nsec += (timeout_ms % 1000) * 1000000;if (ts.tv_nsec >= 10000000

六、总结 —— 队列的核心价值

队列作为基础线性数据结构，核心价值在于：

  1. 顺序保证：严格遵循 FIFO，确保数据处理的时序一致性；
  2. 缓冲平衡：解决生产与消费速率不匹配的问题，防止数据丢失或资源浪费；
  3. 解耦模块：在多组件 / 多线程场景中，作为 “中间层” 隔离数据生产者与消费者，提升系统灵活性。

        无论是嵌入式开发中的串口数据处理，还是后端服务的任务调度，队列都是提升系统稳定性和效率的关键工具。掌握其实现原理与应用场景，是理解复杂系统设计的基础。

http://www.xdnf.cn/news/20046.html

相关文章：

  • 【C++】 list 容器模拟实现解析
  • 富文本编辑器：主流插件简介与wangEditor深度配置指南
  • 【c++】c++输入和输出的简单介绍
  • Mac M4环境下基于VMware Fusion虚拟机安装Ubuntu24.04 LTS ARM版
  • 在 CentOS 9 上安装 Docker 的完整指南
  • 蚂蚁 S21 XP+ HYD 500T矿机评测：SHA-256算法与高效冷却技术的结合
  • 数字隔离器，新能源汽车PTC中的“电气安全卫士”
  • git命令解析
  • 家庭网络异常降速问题排查处理方案
  • 查找算法 -- 二分查找 O(log n)
  • 前端笔记2025
  • 快速了解迁移学习
  • Jupyter Notebook的交互式开发环境方便py开发
  • 一文看懂什么是GaN HEMT以及其工艺流程（氮化镓高电子迁移率晶体管）
  • 数据结构之双向链表
  • Nginx 配置详解与虚拟主机实战指南
  • 嵌入式|Linux中打开视频流的两种方式V4l2和opencv
  • Python的语音配音软件，使用edge-tts进行文本转语音，支持多种声音选择和语速调节
  • MySQL 主从复制详解：部署与进阶配置
  • NGUI--三大基础控件
  • VBA 中的 Excel 工作表函数
  • 新后端漏洞（上）- Java RMI Registry反序列化漏洞
  • Struts2 工作总结
  • B树，B+树，B*树（无代码）
  • React JSX 语法讲解
  • bat脚本- 将jar 包批量安装到 Maven 本地仓库
  • Highcharts 数据源常见问题解析：连接方式、格式处理与性能优化指南
  • React 样式隔离核心方法和最佳实践
  • 【展厅多媒体】AI虚拟数字人在展厅互动中的应用
  • [VF2] Boot Ubuntu和Debian发行版