引言：
在之前的文章中，我们探讨了栈（Stack）这种“后进先出”的结构，它像是一个只有一个口的箱子。而队列则完全不同，它更像是一条单行道的隧道：入口在一端，出口在另一端。
栈：最后进去的最先出来（LIFO）。
队列：最先进去的最先出来（FIFO, First In First Out）。
一、顺序队列基础概念
1.1 队列的定义与特性
队列是一种遵循**先进先出（FIFO）**原则的线性表，允许在表的一端（队尾）插入元素，在另一端（队头）删除元素。这种特性使得队列在需要按顺序处理元素的场景中尤为重要，如电影院售票窗口排队、公交站候车等。
1.2 顺序队列的实现方式
顺序队列通常采用一维数组作为存储结构，通过两个指针（front和rear）分别指示队头元素位置和队尾元素的后一位置。初始化时，front和rear均指向数组的起始位置（通常为0）。
1.3管理顺序队列的结构体设计
typedef char ElemType;
#define STACKINITSIZE 10 //初始容量
#define STACKINCREMENT 2 //每次扩容的倍数
typedef struct SeqStack {
ElemType* front; //队头指针
ElemType* rear; //队尾指针
size_t stacksize; //当前容量
}SeqQueue, * PSeqQueue;
元素指针类型的队头指针和队尾指针分别指向，申请空间的首元素地址，和有效节点的下一位置，下图是顺序队列的入队出队示意图，帮助读者理解：
二、核心函数操作的实现
2.1 初始化、判空、判满、获取队中的元素个数
void InitSeqQueue(PSeqQueue pq)； //初始化
bool IsEmpty(PSeqQueue pq)； //判空
bool IsFull(PSeqQueue pq)； //判满
size_t GetSize(const PSeqQueue pq)； //获取队中的元素个数
初始化：在堆区申请一片空间，将这片空间的地址给到队列的头尾指针，然后初始化队列容量即可
判空：若是头尾指针相同，则队列为空（return pq->front == pq->rear）
判满：若是头尾指针的差值等于队列当前的容量，则队列为满（return pq->rear – pq->front == pq->stacksize）
获取队中的元素个数：头尾指针的差值就是队列元素的个数（对于指针的用法不清楚的读者，可以看我C语言篇的文章，这是链接-》C语言：指针及其用法-CSDN博客）这里就不过多解释了
//1.初始化
void InitSeqQueue(PSeqQueue pq) {
assert(pq != NULL);
ElemType* p = (ElemType*)malloc(sizeof(ElemType) * STACKINITSIZE);
if (p == NULL)return;
pq->front = pq->rear = p; //初始化时，头尾指针指向相同
pq->stacksize = STACKINITSIZE; //设置队列容量
}
//2.判空
bool IsEmpty(PSeqQueue pq) {
assert(pq != NULL);
return pq->front == pq->rear; //头尾指针相同则为空
}
//3.判满
bool IsFull(PSeqQueue pq) {
assert(pq != NULL);
return pq->rear – pq->front == pq->stacksize; //头尾指针差值为队列当前容量则为满
}
//4.获取队中的元素个数
size_t GetSize(const PSeqQueue pq) {
assert(pq != NULL);
return pq->rear – pq->front; //头尾指针差值即为元素个数
}
2.2 扩容、入队
bool IncRea(const PSeqQueue pq)； //扩容
bool Push(PSeqQueue pq, ElemType val)； //入队
扩容：入队之前，要先判满，若是队列满了，就要进行扩容（realloc），然后才能入队
入队：在队尾进行入队，入队之后，尾指针就要进行后移操作（*pq->rear++ = val），队尾指针处是没有元素的，指向队尾元素的下一个位置
//1.扩容
bool IncRea(const PSeqQueue pq) {
assert(pq != NULL);
size_t newSize = pq->stacksize * STACKINCREMENT; //新容量 = 旧容量*宏定义的扩容倍数
ElemType* p = (ElemType*)realloc(pq->front, newSize * sizeof(ElemType));
if (p == NULL)return false;
pq->front = p; //让头指针指向新空间的地址
pq->rear = pq->front + pq->stacksize; //尾指针就是头指针+之前的容量
pq->stacksize = newSize; //重置队列的容量
return true;
}
//2.入队
bool Push(PSeqQueue pq, ElemType val) {
assert(pq != NULL);
if (IsFull(pq)) {
if (IncRea(pq) == false) { //扩容可能会失败，要判断一下
return false;
}
}
*pq->rear++ = val; //后置加加：先解应用并进行赋值操作，然后指针自增
return true;
}
2.3 出队、打印
bool Pop(PSeqQueue pq, ElemType* pval)； //出队
void PrintfQueue(const PSeqQueue pq)； //打印
出队：元素出队列，只能从队头出去，队头指针不能移动，因为它保存的是队列整片空间的地址，要安全出队，可以将除了第一个元素外的所有元素，向前覆盖一个元素位置（memmove实现），同时，队尾指针自减操作一次（将元素个数减少了1）即可
打印：从队头开始，用一元素指针（ElemType* p == pq->front）p开始循环遍历，p<pq->rear，然后解应用p，输出数据即可
//1.出队并获取队头元素
bool Pop(PSeqQueue pq, ElemType* pval) { //传入一元素指针用于接收队头元素
assert(pq != NULL);
if (IsEmpty(pq))return false;
*pval = *pq->front; //解引用指针接收队头元素
memmove(pq->front, pq->front + 1, (pq->rear – pq->front) – 1); //覆盖队头元素
pq->rear–; //尾指针自减
return true;
}
//2.打印
void PrintfQueue(const PSeqQueue pq) {
assert(pq != NULL);
if (IsEmpty(pq))return;
for (ElemType* p = pq->front; p < pq->rear; p++) { //p从头指针开始
printf("%d ", *p); //*p：解引用指针输出数据
}
printf("\\n");
}
函数测试：
2.4 获取队头元素、获取队尾元素
bool GetFront(PSeqQueue pq, ElemType* pval)； //获取队头元素
bool GetRear(PSeqQueue pq, ElemType* pval)； //获取队尾元素
获取队头元素：通过解引用，传入的元素地址，来接收队头元素即可（*pval = *pq->front）
获取队尾元素：通过解应用，传入的元素地址，来接收队尾元素即可（*pval = *(pq->rear-1)）
//1.获取队头元素
bool GetFront(PSeqQueue pq, ElemType* pval) {
assert(pq != NULL);
if (IsEmpty(pq))return false; //判空操作
*pval = *pq->front; //接收元素
return true;
}
//2.获取队尾元素
bool GetRear(PSeqQueue pq, ElemType* pval) {
assert(pq != NULL);
if (IsEmpty(pq))return false; //判空
*pval = *(pq->rear – 1); //接收尾元素，pq->rear指向的地址是没有元素的
return true;
}
2.5 清空、销毁
void ClearQueue(PSeqQueue pq)； //清空
void DestroyQueue(PSeqQueue pq)； //销毁
清空：将顺序队列的尾指针置与头指针相同，队列元素即可清空
销毁：在清空的基础上，将申请的队列的空间释放即可
//1.清空
void ClearQueue(PSeqQueue pq) {
assert(pq != NULL);
if (IsEmpty(pq))return;
pq->rear = pq->front; //尾指针置与头指针相同
}
//2.销毁
void DestroyQueue(PSeqQueue pq) {
assert(pq != NULL);
pq->rear = pq->front;
free(pq->front); //释放空间
pq->front = pq->rear = NULL; //置空指针
pq->stacksize = 0; //容量置为0
}
三、结语
夫队列者，线性之属，循序而进， FIFO 是其魂也。
纵观本次实践，始于结构体之定义，终于销毁函数之释放。其间种种，如履薄冰：判空判满，乃审时度势之智；入队出队，似行云流水之姿。尤叹扩容之举，犹如筑堤蓄水，未雨绸缪，方得始终。虽无链表之灵动变幻，却有数组之质朴厚重，于连续内存之间，尽显严谨法度。
代码虽短，意蕴悠长。此次重构顺序队列，非仅技艺之操练，实乃逻辑之修行。以此微末之功，冀望未来能驾驭更浩瀚之算法汪洋，心向往之。
