/*
* ==============================================================
* File name: link_queue.c
* Author: 3360652783@qq.com
* Date created: 2026-07-27
* Description: Queue implementation based on singly linked list (with head node).
* Copyright notice: All right Reserved.
* ==============================================================
*/#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>/*
@brief：式队列内结点结构体
*/
typedef struct Node{int data; //结点中存储的数据struct Node *next; //指向下一个结点的指针
}Node;/*
*@brief：链式队列头结点结构体（存储链式队列各参数）
*/
typedef struct LinlQueue{Node *Front; //指向首结点的指针Node *Rear; //指向尾结点的指针
}LinQueue_t;/*
@brief：创建一个链式队列并对它进行初始化
@return：成功返回队列指针，失败退出程序
@note：初始化时会创建一个头结点（哨兵），front 和 rear 都指向它
*/
LinQueue_t *LinkQueue_creat(){LinQueue_t *head = (LinQueue_t *)calloc(1,sizeof(LinQueue_t));Node *q = (Node *)calloc(1,sizeof(Node)); //创建哨兵结点if( head == NULL || q == NULL ){printf("内存空间申请失败");exit(-1);}head->Front = q; //头结点的Front指针、Rear指针都指向哨兵head->Rear = q;return head;
}/*
@brief：入队
@return：成功返回true，失败返回false
@param：@head：链式队列头结点@data：需要入队的数据
@note：链式队列入队不需要判断队列是否已满
*/
bool enQueue(LinQueue_t *head,int data){Node *New = (Node *)calloc(1,sizeof(Node));if( New == NULL ){printf("新结点内存空间申请失败");return false;}New->data = data; //将需要插入的值赋给新结点的dataNew->next = NULL; //新结点要插入链表尾部，所以其next指针指向NULLhead->Rear->next = New; //尾结点的next指针指向新结点head->Rear = New; //头结点的Rear指针指向新结点return true;
}/*
@brief：判断链式队列是否为空
@return：队列为空返回true，否则返回false
@param：@
@note：链式队列入队不需要判断队列是否已满
*/
bool LinKQueue_IsEmpty(LinQueue_t *head){if( head->Rear != head->Front ){ //队列为空，头结点前后指针都指向哨兵return false;}return true;
}/*
@brief：出队
@return：成功返回出队数据，失败返回false
@param：@head：链式队列头结点
@note：链式队列出队需要判断队列是否为空
*/
int DeQueue(LinQueue_t *head){Node *temp = NULL;int data;if( head->Rear == head->Front ){ //队列为空，出队失败printf("队列为空，出队失败");exit(-1);}if( head->Front->next == head->Rear ){ //链式队列中仅有一个结点temp = head->Rear;head->Rear = head->Front;data = temp->data;free(temp);return data;}temp = head->Front->next;head->Front->next = temp->next;temp->next = NULL;data = temp->data;free(temp);return data;
}int main() {printf("========== 链式队列功能测试 ==========\n\n");// 1. 创建队列LinQueue_t *q = LinkQueue_creat();printf("1. 队列创建成功\n");printf(" 队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 2. 入队测试printf("2. 入队测试：\n");int test_data[] = {10, 20, 30, 40, 50};for (int i = 0; i < 5; i++) {if (enQueue(q, test_data[i])) {printf(" 入队 %d 成功\n", test_data[i]);} else {printf(" 入队 %d 失败\n", test_data[i]);}}printf(" 队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 3. 出队测试printf("3. 出队测试：\n");for (int i = 0; i < 3; i++) {int val = DeQueue(q);printf(" 出队：%d\n", val);}printf("\n");// 4. 再次入队printf("4. 再次入队 60, 70：\n");enQueue(q, 60);enQueue(q, 70);printf(" 入队完成\n\n");// 5. 全部出队printf("5. 全部出队：");while (!LinKQueue_IsEmpty(q)) {printf(" %d", DeQueue(q));}printf("\n");printf(" 队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 6. 单结点场景测试（最容易出 bug 的场景）printf("6. 单结点场景测试：\n");enQueue(q, 100);printf(" 入队 100 完成\n");printf(" 队列是否为空？%s\n", LinKQueue_IsEmpty(q) ? "是" : "否");int val = DeQueue(q);printf(" 出队：%d\n", val);printf(" 出队后队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 7. 单结点出队后再次入队（验证 Rear 是否正确重置）printf("7. 单结点出队后再次入队测试：\n");enQueue(q, 200);enQueue(q, 300);printf(" 入队 200, 300 完成\n");printf(" 出队序列：");while (!LinKQueue_IsEmpty(q)) {printf(" %d", DeQueue(q));}printf("\n");printf(" 队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 8. 批量入队出队printf("8. 批量入队出队测试：\n");for (int i = 1; i <= 5; i++) {enQueue(q, i * 10);}printf(" 入队 10, 20, 30, 40, 50 完成\n");printf(" 全部出队：");while (!LinKQueue_IsEmpty(q)) {printf(" %d", DeQueue(q));}printf("\n");printf(" 队列是否为空？%s\n\n", LinKQueue_IsEmpty(q) ? "是" : "否");// 9. 空队列出队测试（会触发 exit(-1)，取消注释以测试）// printf("9. 空队列出队测试（程序将退出）：\n");// DeQueue(q);printf("========== 所有测试通过 ==========\n");return 0;
}
