> 技术文档 > 数据结构之队列

数据结构之队列


欢迎拜访:雾里看山-CSDN博客
本篇主题数据结构之队列
发布时间:2025.7.9
隶属专栏:数据结构

在这里插入图片描述

目录

  • 队列的概念与结构
    • 基本概念
    • 核心特性
  • 队列的实现
    • 链表实现队列
      • 队列结构的定义
      • 队列基本操作的实现
    • 数组实现循环队列
      • 队列结构的定义
      • 队列基本操作的实现
  • 两种实现的比较
  • 总结与选择建议
    • 队列的核心价值
    • 实现选择建议
    • 应用领域总结

队列的概念与结构

基本概念

队列是一种先进先出FIFO: First-In-First-Out)的线性数据结构,只允许在固定的一端进行插入(入队),在另一端进行删除(出队)。队列的操作特性可类比现实生活中的排队:

  • 入队 (Enqueue):将元素添加到队列尾部
  • 出队 (Dequeue):从队列头部移除元素
  • 队头 (Front):队列中最早添加的元素位置
  • 队尾 (Rear):队列中最新添加的元素位置

核心特性

  • FIFO原则:最先入队的元素最先出队
  • 受限访问:只能访问队头和队尾元素
  • 动态大小:大小随操作变化(除固定大小队列)
  • 操作高效:所有操作时间复杂度为O(1)

数据结构之队列

队列的实现

链表实现队列

队列结构的定义

  1. 定义存储的数据类型。
  2. 定义每一个节点,节点里面存储数据和下一个节点的指针
  3. 定义队列,队列里存储头结点和尾结点以及队列中存储数据的个数
typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode;typedef struct Queue{QNode* head;QNode* tail;int size;}Que;

队列基本操作的实现

队列的基本操作包括:初始化,销毁,入队列,出队列,获取头部节点数据,获取尾部节点数据,队列判空,队列存储数据个数。

初始化:

void QueueInit(Que* pq){assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}

销毁:

void QueueDestroy(Que* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* tmp = cur;cur = cur->next;free(tmp);}pq->head = pq->tail = NULL;pq->size = 0;}

入队列:

void QueuePush(Que* pq, QDataType x){assert(pq);QNode* newnode = (QNode* )malloc(sizeof(QNode));if (newnode == NULL){perror(\"malloc fail\");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL)// Ϊ{pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}

出队列:

void QueuePop(Que* pq){assert(pq);assert(!QueueEmpty(pq));QNode* temp = pq->head;if (pq->head->next == NULL){pq->head = pq->tail = NULL;}else{pq->head = pq->head->next;}pq->size--;free(temp);}

获取队列头部数据:

QDataType QueueFront(Que* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}

获取队列尾部数据:

QDataType QueueBack(Que* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

队列判空:

bool QueueEmpty(Que* pq){assert(pq);return pq->size == 0;}

队列中存储元素个数:

int QueueSize(Que* pq){assert(pq);return pq->size;}

数组实现循环队列

队列结构的定义

  1. 需要指定循环队列的大小,可以存储的数据量是MAX_SIZE-1
  2. 定义存储的数据类型
  3. 定义循环队列,包括用于存储数据的数组,和两个下标分别指向头部位置和尾部的下一个位置
#define MAX_SIZE 10typedef int CirQueueDataType;typedef struct cir_queue{CirQueueDataType data[MAX_SIZE];int front;int rear;}CirQueue;

队列基本操作的实现

队列的基本操作包括:初始化,队列判空,队列判满,入队列,出队列,获取头部节点数据,获取尾部节点数据,队列存储数据个数。

初始化:

void CirQueueInit(CirQueue* pcq){assert(pcq);pcq->front = pcq->rear = 0;}

队列判空:

bool CirQueueIsEmpty(CirQueue* pcq){assert(pcq);return pcq->front == pcq->rear;}

队列判满:

bool CirQueueIsFull(CirQueue* pcq){assert(pcq);return (pcq->rear + 1) % MAX_SIZE == pcq->front;}

入队列:

void CirQueuePush(CirQueue* pcq, CirQueueDataType x){if (CirQueueIsFull(pcq)){printf(\"队列已满\\n\");return;}pcq->data[pcq->rear] = x;pcq->rear = (pcq->rear + 1) % MAX_SIZE;}

出队列:

void CirQueuePop(CirQueue* pcq){if (CirQueueIsEmpty(pcq)){printf(\"队列为空\\n\");return;}pcq->front = (pcq->front + 1) % MAX_SIZE;}

获取队列头部数据:

CirQueueDataType CirQueueFront(CirQueue* pcq){if (CirQueueIsEmpty(pcq)){printf(\"队列为空\\n\");return;}return pcq->data[pcq->front];}

获取队列尾部数据:

CirQueueDataType CirQueueBack(CirQueue* pcq){if (CirQueueIsEmpty(pcq)){printf(\"队列为空\\n\");return;}return pcq->data[((pcq->rear - 1)+MAX_SIZE)%MAX_SIZE];}

队列存储数据个数:

int CirQueueSize(CirQueue* pcq){return (pcq->rear - pcq->front + MAX_SIZE) % MAX_SIZE;}

两种实现的比较

特性 循环队列 链式队列 内存分配 静态/固定大小 动态分配/无固定大小 空间效率 无额外指针开销 每个节点额外指针开销 时间效率 所有操作O(1) 所有操作O(1) 扩容能力 有限(固定大小) 无限(除非内存耗尽) 假溢出 不存在 不存在 缓存友好 高(连续内存) 低(非连续内存) 适用场景 元素数量固定/可预测 元素数量变化大/不可预测

总结与选择建议

队列的核心价值

  • 先进先出:保证元素处理顺序的公平性
  • 缓冲机制:平衡生产者和消费者的速度差异
  • 解耦系统:分离任务的产生和处理
  • 高效操作:所有基本操作时间复杂度O(1)

实现选择建议

场景 推荐实现 理由 元素数量固定/可预测 循环队列 内存紧凑,无额外开销 元素数量变化大/不可预测 链式队列 动态扩展,无容量限制 高频访问/内存敏感 循环队列 缓存友好,访问速度快 需要精确控制内存 循环队列 预分配固定大小内存 需要实现复杂队列类型 链式队列 灵活性高,易于扩展

应用领域总结

  • 操作系统:进程调度、I/O请求管理
  • 网络通信:数据包缓冲、流量控制
  • 实时系统:事件处理、消息传递
  • 算法实现:BFS、缓存算法
  • 分布式系统:任务队列、消息队列
  • 图形处理:渲染队列、事件处理

⚠️ 写在最后:以上内容是我在学习以后得一些总结和概括,如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流!!!