企业官网建设流程全解析

引入：队列解决的是“按到达顺序服务”

在实际排队买票场景中，先到的人通常先办理；打印机收到多个任务时，也常按提交顺序处理。若后来的人可以随意插队，系统就很难预测，也不公平。队列（queue）把这种规则抽象成一种线性数据结构：先进入的元素先离开，即 FIFO（First In, First Out，先进先出）。

队列有两个操作端：元素从队尾（rear）加入，从队头（front）删除。注意“加入”和“删除”发生在不同位置，这正是它与栈的关键区别。

队列的常见操作包括：

• QueuePush：在队尾入队。
• QueuePop：从队头出队。
• QueueFront：查看队头元素，不删除。
• QueueBack：查看队尾元素，不删除。
• QueueSize：获取有效元素个数。
• QueueEmpty：判断队列是否为空。

队列也只是一个抽象接口，可以用数组实现，也可以用链表实现。本篇采用的是带头尾指针的链队列实现。

一、链队列的结构：节点串起来，两个指针守住两端

本篇同样采用三个文件Queue.h、Queue.c、test.c来实现链队列。

• Queue.h：链队列节点定义以及功能函数声明。
• Queue.c：链队列各功能函数具体实现。
• test.c：测试功能有效性。

定义链队列节点与结构：

typedefintQDataType;//定义队列节点,链式结构typedefstructQueueNode{QDataType data;structQueueNode*next;}QNode;//队列结构（队头队尾）typedefstructQueue{QNode*front;//队头指针QNode*rear;//队尾指针intsize;//元素数量}Queue;

当队列保存10、20、30时，逻辑结构是：

front rear │ │ ▼ ▼ [10 | next] ──▶ [20 | next] ──▶ [30 | NULL] size = 3

front指向第一个要被服务的节点，rear指向最后一个刚进入的节点。因为两端地址都保存着，所以队尾追加不需要从头遍历整条链表，队头删除也能直接定位。

链队列实现时须保证以下规则：

1. 空队列时front == NULL、rear == NULL、size == 0。
2. 非空队列时front和rear都不为空，rear->next == NULL。
3. 只有一个节点时，front == rear，这个节点的next仍为NULL。

二、根据功能使用C语言实现

1. 初始化：三个成员先指向“空状态”

使用QueueInit()函数初始化队列，但不在初始化时申请节点：

//初始化队列voidQueueInit(Queue*q){assert(q);q->front=NULL;q->rear=NULL;q->size=0;}

链队列的空间随入队动态申请，因此空队列本身只需要两个个指针和一个计数器。

2. 入队：首节点和普通节点是两种情况

新节点先写入数据并把next设为NULL，因为它会成为新的队尾：

//队尾入队列voidQueuePush(Queue*q,QDataType x){assert(q);//申请节点QNode*newNode=(QNode*)malloc(sizeof(QNode));if(newNode==NULL){perror("QueuePush()::malloc() fail");return;}newNode->data=x;newNode->next=NULL;//判断当前队列是否有节点if(q->rear==NULL){q->rear=q->front=newNode;}else{q->rear->next=newNode;q->rear=newNode;}q->size++;}

第一次入队时，队头和队尾必须同时指向新节点；之后才是“旧队尾连到新节点，再移动rear”的普通流程。若忘记处理第一次入队，front仍为空，后续QueueFront就无法工作。

3. 出队：真正关键的是只剩一个节点

普通出队只需保存下一个节点、释放旧队头、移动front：

//队头出队列voidQueuePop(Queue*q){assert(q);if(QueueEmpty(q)){printf("当前队列为空，无法出队列！！\n");return;}else{//处理只有单个节点的情况if(q->front->next==NULL){free(q->front);q->front=q->rear=NULL;}//处理多个节点else{QNode*next=q->front->next;free(q->front);q->front=next;}}q->size--;}//检测队列是否为空boolQueueEmpty(Queue*q){assert(q);if(q->front==NULL)returntrue;elsereturnfalse;}

最后一个节点出队后，front变成NULL，此时必须让rear也变成NULL，否则rear会成为悬空指针：它指向已经释放的内存，下一次入队或取队尾都可能出错。

4. 获取队头队尾元素

在获取队头队尾元素值时，仅读队头队尾指针的指向，不执行任何删除插入与改变指向的操作：

//获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);if(QueueEmpty(q)){printf("当前队列为空，无法获取！！\n");return;}else{returnq->front->data;}}//获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);if(QueueEmpty(q)){printf("当前队列为空，无法获取！！\n");return;}else{returnq->rear->data;}}

5. 查看元素数量与销毁链表

由于我们在设计队列结构时为其设置了记录元素数量的变量size，所以函数QueueSize()可直接返回队列结构中size的值：

//获取队列有效元素个数intQueueSize(Queue*q){assert(q);returnq->size;}//销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*cur=q->front;while(cur){QNode*next=cur->next;free(cur);cur=next;}q->front=q->rear=NULL;q->size=0;}

销毁函数则从队头开始逐个释放：先保存next，再释放当前节点，最后把队头、队尾和数量恢复为空状态。这种“先记住下一跳，再释放当前节点”的顺序与链表中的一样不能颠倒。

三、运行测试

在test.c文件中编写测试代码，初始化队列后入队1， 2， 3， 4，然后依次取出队头元素并打印，同时统计当前的元素个数再出队尾，最后销毁：

voidtest(){Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);while(!QueueEmpty(&q)){printf("队头元素：%d ",QueueFront(&q));printf("元素数量：%d \n",QueueSize(&q));QueuePop(&q);}QueueDestroy(&q);}

运行结果：

四、复杂度与内存代价

链队列不会像固定数组那样因为“容量满”而整体搬迁，元素数量可以按需增长；代价是每个节点多了一个next指针，还要承担多次malloc/free的管理成本。若任务数量已知且频繁访问，连续数组可能有更好的缓存局部性；若数量变化大且需要两端O(1)操作，链队列则更加灵活。

五、扩展练习

1. 手动追踪队列的两端

操作序列为：Push(7)、Push(9)、Pop()、Push(4)、Pop()、Pop()。写出每一步的队头、队尾和size。

思路：入队只改变rear，出队只改变front；删除前要先记住当前队头。

参考答案：

• Push(7)：队头 7，队尾 7，size=1。
• Push(9)：队头 7，队尾 9，size=2。
• Pop()：队头 9，队尾 9，size=1。
• push(4)：队头 9，队尾 4，size=2。
• 两次Pop()后为空：front=NULL、rear=NULL、size=0。

六、完整参考代码

Queue.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintQDataType;//定义队列节点,链式结构typedefstructQueueNode{QDataType data;structQueueNode*next;}QNode;//队列结构（队头队尾）typedefstructQueue{QNode*front;//队头指针QNode*rear;//队尾指针intsize;//元素数量}Queue;//初始化队列voidQueueInit(Queue*q);//队尾入队列voidQueuePush(Queue*q,QDataType x);//队头出队列voidQueuePop(Queue*q);//获取队列头部元素QDataTypeQueueFront(Queue*q);//获取队列队尾元素QDataTypeQueueBack(Queue*q);//获取队列有效元素个数intQueueSize(Queue*q);//检测队列是否为空boolQueueEmpty(Queue*q);//销毁队列voidQueueDestroy(Queue*q);

Queue.c

#include"Queue.h"//初始化队列voidQueueInit(Queue*q){assert(q);q->front=NULL;q->rear=NULL;q->size=0;}//队尾入队列voidQueuePush(Queue*q,QDataType x){assert(q);QNode*newNode=(QNode*)malloc(sizeof(QNode));if(newNode==NULL){perror("QueuePush()::malloc() fail");return;}newNode->data=x;newNode->next=NULL;if(q->rear==NULL){q->rear=q->front=newNode;}else{q->rear->next=newNode;q->rear=newNode;}q->size++;}//队头出队列voidQueuePop(Queue*q){assert(q);if(QueueEmpty(q)){printf("当前队列为空，无法出队列！！\n");return;}else{//处理只有单个节点的情况if(q->front->next==NULL){free(q->front);q->front=q->rear=NULL;}//处理多个节点else{QNode*next=q->front->next;free(q->front);q->front=next;}}q->size--;}//获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);if(QueusEmpty(q)){printf("当前队列为空，无法获取！！\n");return;}else{returnq->front->data;}}//获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);if(QueueEmpty(q)){printf("当前队列为空，无法获取！！\n");return;}else{returnq->rear->data;}}//获取队列有效元素个数intQueueSize(Queue*q){assert(q);returnq->size;}//检测队列是否为空boolQueueEmpty(Queue*q){assert(q);if(q->front==NULL)returntrue;elsereturnfalse;}//销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*cur=q->front;while(cur){QNode*next=cur->next;free(cur);cur=next;}q->front=q->rear=NULL;q->size=0;}

test.c

#include"Queue.h"voidtest(){Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);while(!QueueEmpty(&q)){printf("队头元素：%d ",QueueFront(&q));printf("元素数量：%d \n",QueueSize(&q));QueuePop(&q);}QueueDestroy(&q);}intmain(){test();return0;}