队列
一、队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出FIFO（First In First Out）的原则；
入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出FIFO（First In First Out）的原则；
入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
答案：B 队列只能删除队头的数据。
二、队列的实现
1、队列的结构
和栈一样，队列既可以使用顺序表实现，也可以使用链表实现，这里我们使用单链表实现，原因如下：
1、队列需要删除头部的元素，单链表头删的效率为O(1)；
2、使用链表可以按需申请空间，避免了空间的浪费；
但是我们发现使用单链表实现队列存在一个问题，那就是单链表尾插以及计算链表长度的效率都为O(N)，不符合我们的预期，那么我们需要把单链表改造为循环链表吗？可以是可以，但是这样又把队列的结构搞复杂了；所以综合考虑，这里我们增加三个变量，一个用于记录队尾，一个用于记录队头，还有一个用于记录队列的长度。
结构的定义
//符号和结构的定义 typedef int QEDataType; typedef struct QueueNode //队列的一个节点 { QEDataType data; struct QueueNode* next; }QENode; typedef struct Queue //队列 { QENode* head; //记录队列的头 QENode* tail; //记录队列的尾 int size; //记录队列的长度 }Queue;
2、初始化队列
//初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
3、从队尾入队列
由于我们使用了一个结构体来记录队列的头和尾，那么这里我们改变队列的头和尾时只需要改变结构体即可，所以只需要传递一级指针；
另外，队列也只能从队尾入数据，所以我们也没有必要单独封装一个 BuyNode 函数。
//队尾入队列 void QueuePush(Queue* pq, QEDataType x) { assert(pq); //创建一个新节点 QENode* newnode = (QENode*)malloc(sizeof(QENode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; //当入第一个元素时，需要改变队列的头 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; }
4、从队头出队列
这里我们除了正常的对队列进行判空之外，还有一个需要特别注意的地方：当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，会形成野指针，所以我们这里需要单独判断。
//队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断 if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail = NULL; } else { QENode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; }
5、获取队头元素
//返回队头元素 QEDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
6、获取队尾元素
//返回队尾元素 QEDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
7、获取队列长度
//返回队列长度 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
8、判断队列是否为空
//判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
9、销毁队列
//销毁队列 void QueueDestory(Queue* pq) { assert(pq); QENode* cur = pq->head; while (cur) { QENode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; }
注意：和栈一样，队列也不需要定义 print 函数，因为队列也不能遍历，要想取出队头后面的元素，我们必须先 pop 掉之前的元素，让该元素成为队头。
三、完整代码
1、Queue.h
#pragma once //防止头文件重复包含 //头文件的包含 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //符号和结构的定义 typedef int QEDataType; typedef struct QueueNode //队列的一个节点 { QEDataType data; struct QueueNode* next; }QENode; typedef struct Queue //队列 { QENode* head; //记录队列的头 QENode* tail; //记录队列的尾 int size; //记录队列的长度 }Queue; //函数的声明 //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestory(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QEDataType x); //队头出队列 void QueuePop(Queue* pq); //返回队头元素 QEDataType QueueFront(Queue* pq); //返回队尾元素 QEDataType QueueBack(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //返回队列长度 int QueueSize(Queue* pq);
2、Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } //销毁队列 void QueueDestory(Queue* pq) { assert(pq); QENode* cur = pq->head; while (cur) { QENode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QEDataType x) { assert(pq); //创建一个新节点 QENode* newnode = (QENode*)malloc(sizeof(QENode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; //当入第一个元素时，需要改变队列的头 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断 if (pq->head == pq->tail) { free(pq->head); pq->head = pq->tail = NULL; } else { QENode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } //返回队头元素 QEDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } //返回队尾元素 QEDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //返回队列长度 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h" int main() { Queue q; //初始化队列 QueueInit(&q); //队尾入队列 QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //队列也不能遍历，取出一个元素即代表从队头出一个元素 while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } //销毁队列 QueueDestory(&q); return 0; }
大家也可以去我的 Gitee 仓库中获取完整代码：Queue/Queue · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
