队列的基本概念
1、队列是操作受限的线性表
2、队头：允许删除的一端
3、队尾：允许插入的一端
4、空队列：不含任何元素的空表
5、特点：先进先出、FIFO
6、应用场景：
栈：解决括号匹配；逆波兰表达式求解; 递归改非递归等等
队列：公平排队，广度优先遍历等等
队列的结构：
队列的具体实现结构比较灵活，只要遵循先进先出原则即可。 顺序表的方式实现，如果用数组表示，虽然尾插数据比较方便，但当头删数据时，还要移动剩余元素，代价比较大，故不推荐顺序存储方式。单链表的方式实现，头删数据方便，只要添加一个记录尾节点的指针，进行尾插数据的效率也还可以。
队列的特点
由于队列是FIFO的原则，这就类似于食堂排队打饭，先排队的一定先吃上饭，而队尾的就得等先排队的打完饭了，才有机会打饭。这和栈的LIFO的原则有些不同
队列的代码实现
1、队列的定义
创建队列需要定义两个结构体
1、一个用来保存节点的链式结构，
2、一个用来记录队头和队尾
typedef int elementType;
typedef struct QueueListNode
{elementType value;struct QueueListNode* next;
}QNode;
typedef struct Queue_List
{QNode* head;//队头 QNode* tail;//队尾
}Queue;2、队列的初始化
思路：初始化队列时，把记录队列的队头和队尾的节点地址置为空，记录队头和队尾的结构体不可能为空，需断言
void init_queue(Queue* QueueList)
{assert(QueueList);QueueList->head = NULL;QueueList->tail = NULL;printf("初始化成功\n");
}3、入列 （队尾插入）
思路：首先创建一个新的节点，保存索要插入的数据，然后进行尾插，如果队列为空，则直接把head 和tail指向新节点即可，如果队列不为空，只需将tail的next指向新的节点，然后刷新尾节点，将新节点赋值给tail
void enter_queue(Queue* QueueList)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);memset(newnode, 0, sizeof(QNode));elementType val;printf("请输入要入队的元素值:");scanf(" %d", &val);newnode->value = val;newnode->next = NULL;if (is_empty(*QueueList)){//如果队列是空QueueList->head = newnode;QueueList->tail = newnode;}else{//队列非空，尾插QueueList->tail->next = newnode;//将新节点插到尾部QueueList->tail = newnode;//更新尾节点}printf("入队成功\n");
}4、出列 （队头删除)
思路：想要出队列的前提是队列不为空，这里出队列有两种情况：一般情况下只需要定义一个指针变量next用来保存到head的下一个节点，然后free掉head,将next指针赋值给head,完成head刷新，但是当我们删除到只剩下一个节点时，再删一次。head为空指针,而此时tail就变成了野指针，此时需要把head和tail都置空
void out_queue(Queue* QueueList)
{if (is_empty(*QueueList)){printf("队列为空，无法出列\n");return;}QNode* temp = QueueList->head->next;//保存次头节点if (temp == NULL){//说明队列里面只有一个元素 删完后就为空队列free(QueueList->head);QueueList->head = NULL;QueueList->tail = NULL;}else{free(QueueList->head);QueueList->head = temp;}printf("出列成功\n");
}
