数据结构之队列
目录
- 队列的概念与结构
-
- 基本概念
- 核心特性
- 队列的实现
-
- 链表实现队列
-
- 队列结构的定义
- 队列基本操作的实现
- 数组实现循环队列
-
- 队列结构的定义
- 队列基本操作的实现
- 两种实现的比较
- 总结与选择建议
-
- 队列的核心价值
- 实现选择建议
- 应用领域总结
队列的概念与结构
基本概念
队列是一种先进先出(FIFO: First-In-First-Out
)的线性数据结构,只允许在固定的一端进行插入(入队),在另一端进行删除(出队)。队列的操作特性可类比现实生活中的排队:
- 入队 (Enqueue):将元素添加到队列尾部
- 出队 (Dequeue):从队列头部移除元素
- 队头 (Front):队列中最早添加的元素位置
- 队尾 (Rear):队列中最新添加的元素位置
核心特性
- FIFO原则:最先入队的元素最先出队
- 受限访问:只能访问队头和队尾元素
- 动态大小:大小随操作变化(除固定大小队列)
- 操作高效:所有操作时间复杂度为O(1)
队列的实现
链表实现队列
队列结构的定义
- 定义存储的数据类型。
- 定义每一个节点,节点里面存储数据和下一个节点的指针
- 定义队列,队列里存储头结点和尾结点以及队列中存储数据的个数
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;}
数组实现循环队列
队列结构的定义
- 需要指定循环队列的大小,可以存储的数据量是
MAX_SIZE-1
- 定义存储的数据类型
- 定义循环队列,包括用于存储数据的数组,和两个下标分别指向头部位置和尾部的下一个位置
#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)
实现选择建议
应用领域总结
- 操作系统:进程调度、I/O请求管理
- 网络通信:数据包缓冲、流量控制
- 实时系统:事件处理、消息传递
- 算法实现:BFS、缓存算法
- 分布式系统:任务队列、消息队列
- 图形处理:渲染队列、事件处理
⚠️ 写在最后:以上内容是我在学习以后得一些总结和概括,如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流!!!