队列(详解)

一.队列的概念

        队列（Queue）是一种常见的数据结构，它按照先进先出的原则管理数据。这意味着最先进入队列的元素将被最先移出队列，类似于现实生活中排队的场景。
在队列中，数据项被添加到队列的一端，称为队尾，而从队列中移除数据项的操作则发生在另一端，称为队首。新元素被添加到队列的尾部，并且从队列中移除元素时，总是从队列的头部开始。
队列的基本操作：

1. 队列的初始化。
2. 入队：将元素添加到队列的尾部。
3. 出队：从队列的头部移除元素。
4. 获取队首元素：查看队列的头部元素，但不移除它。
5. 判断队列是否为空：检查队列是否不包含任何元素。
6. 队列的销毁。

队列常用于需要按顺序处理数据的场景，比如任务调度、缓冲等。

二.队列的特点

        1.先进先出：队列中的元素按照先进先出的原则进行排列和访问。最先进入队列的元素将被最先移出队列。
        2.有限容量：队列通常具有固定的容量限制，即队列中能够容纳的元素数量是有限的。当队列已满时，无法再向其中添加新的元素，除非先移除队列中的一些元素。
        3.受限的访问：队列的访问受到限制，只能在队列的两端进行操作。元素的插入（入队）只能发生在队列的尾部，而元素的移除（出队）只能从队列的头部进行。
        4.动态变化：队列的大小可以动态地扩展或收缩，具体取决于实现队列的数据结构。一些队列的实现允许在需要时动态地增加其容量，以适应更多的元素。
        5.线性结构：队列是一种线性数据结构，元素之间的关系是一对一的。每个元素都有且仅有一个直接前驱和一个直接后继。
        6.适用性：队列常用于需要严格控制元素访问顺序的情况，如任务调度、资源分配等。
        7.高效性：对于队列中的元素添加和移除操作，时间复杂度通常是常数级别的。这使得队列在许多应用中具有高效的性能。
        8.应用广泛：队列是一种常见且重要的数据结构，在计算机科学和软件工程中被广泛应用，例如操作系统中的进程调度、网络数据包传输、消息队列、算法设计等领域。
        9.稳定性：队列的稳定性指的是对于相同的输入，输出结果是确定的，不受其他因素影响，而这一点栈结构是做不到的。这使得队列在许多算法和系统设计中具有可靠性和可预测性。

三.队列的实现

队列是基于链表和顺序表来实现，结合队列的特点使用链表来实现更为便洁。

源码：

Queue.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
#define QueueData inttypedef struct QueueNode
{QueueData val;struct QueueNode* next;
}QueueNode;
typedef struct
{QueueNode* phead;QueueNode* pend;int size;
}Queue;//储存的是链表的头节点和链表的尾节点以及队列的元素个数，更容易维护队列。
void QueueInit(Queue* pQ);//初始化
void QueuePush(Queue* pQ, QueueData x);//队尾入队
void QueuePop(Queue* pQ);//出队
QueueData QueueFront(Queue* pQ);//取队头元素
int QueueSize(Queue* pQ);//获取队列元素个数
bool QueueEmpty(Queue* pQ);//判空
void QueueDestroy(Queue* pQ);//销毁队列

Queue.c

#include"Queue.h"
void QueueInit(Queue* pQ)
{assert(pQ);pQ->pend = pQ->phead = NULL;pQ->size = 0;
}
void QueuePush(Queue* pQ, QueueData x)
{assert(pQ);QueueNode* pnew = (QueueNode*)malloc(sizeof(QueueNode));assert(pnew);pnew->val = x;pnew->next = NULL;if (pQ->size == 0){pQ->pend = pQ->phead = pnew;}else{pQ->pend->next = pnew;pQ->pend = pnew;}pQ->size++;
}
QueueData QueueFront(Queue* pQ)
{assert(pQ);assert(pQ->size);return pQ->phead->val;
}
void QueuePop(Queue* pQ)
{assert(pQ);QueueData ret = pQ->phead->val;if (pQ->size == 1){free(pQ->phead);pQ->pend = pQ->phead = NULL;}else{QueueNode* pn = pQ->phead;pQ->phead = pQ->phead->next;free(pn);}pQ->size--;return ret;
}
int QueueSize(Queue* pQ)
{assert(pQ);return pQ->size;
}
bool QueueEmpty(Queue* pQ)//判空
{assert(pQ);return pQ->size;
}
void QueueDestroy(Queue* pQ)
{assert(pQ);while (pQ->phead){QueueNode* pnext = pQ->phead->next;free(pQ->phead);pQ->phead=pnext;}pQ->pend = pQ->phead = NULL;pQ->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{Queue ps;QueueInit(&ps);int n = 10;while (n--)QueuePush(&ps, n + 1);while (QueueEmpty(&ps)){printf("%d ",QueueFront(&ps));QueuePop(&ps);}QueueDestroy(&ps);return 0;
}