前言：
我们前面已经学习了栈，今天我们来学习队列，队列和栈一样，相对来说比较简单，随后，会为大家准备OJ练习题，敬请期待！
一、什么是队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一 端称为队头
这里简单给大家解释一下：
大家肯定都排过队（别说没有，我不信），大家在排好队先前前进时，是不是先站到队伍里的先走。队列的原理何其类似。因为，你可以猜一猜它为什么叫队列。可用下面图片帮助大家理解。 
明白了，基础知识，那就一起来实现一下队列吧。
二、队列的实现
2.1 队列结构
和栈一样，我们队列的结构该如何设计呢？
队列一共有两种结构，分为：顺序结构和链式结构
- 队列的顺序结构
入队，不需要移动任何元素，时间复杂度为O(1)
出队，所有元素需要往前移动，时间复杂度为O(N)
- 队列的链式结构
首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点
入队（尾插），时间复杂度为O(1)
出队（头删），时间复杂度为O(1)
这里，我们将采取链式结构，如若对顺序结构感兴趣可结合之前的栈进行实现。
我们要采用链式难道要用二级指针吗？一级已经够麻烦了，使用二级会更晕。所以，为了避免这种轻快，我们可采取结构体，如下代码：
1. typedef int QDataType; 2. // 链式结构：表示队列 3. typedef struct QListNode 4. { 5. struct QListNode* next; 6. QDataType data; 7. }QNode; 8. 9. // 队列的结构 10. typedef struct Queue 11. { 12. QNode* phead; 13. QNode* ptatil; 14. int size; 15. }Queue;
这样即可避免二级指针。
2.2 队列初始化
1. // 初始化队列 2. void QueueInit(Queue* q) 3. { 4. assert(q); 5. q->phead = q->ptatil = NULL; 6. q->size = 0; 7. }
初始化只用将头和尾置为空即可。队列还未建立，所以，先不管。
2.3 队列销毁
1. // 销毁队列 2. void QueueDestroy(Queue* q) 3. { 4. assert(q); 5. QNode* cur = q->phead; 6. while (cur) 7. { 8. QNode* next = cur->next; 9. free(cur); 10. cur = next; 11. } 12. q->phead = q->ptatil = NULL; 13. q->size = 0; 14. }
销毁时我们要释放的是指针所指向开辟空间，而不是指针本身。所以，使用一个while循来释放。
2.4 入队列
1. // 队尾入队列 2. void QueuePush(Queue* q, QDataType data) 3. { 4. assert(q); 5. QNode* newnode = (QNode*)malloc(sizeof(QNode)); 6. if (newnode == NULL) 7. { 8. perror("malloc fail"); 9. return; 10. } 11. newnode->next = NULL; 12. newnode->data = data; 13. if (q->phead == NULL)//这里使用头节点，尾节点判断均可 14. { 15. q->phead = q->ptatil = newnode; 16. } 17. else 18. { 19. q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！ 20. q->ptatil = newnode; 21. } 22. q->size++; 23. }
入队列时，我们要为其开辟一块空间也就是QNode，这就是队列的元素。要分为两种情况讨论，队列为空和队列不为空。
2.5 出队列
1. // 队头出队列 2. void QueuePop(Queue* q) 3. { 4. assert(q); 5. assert(q->size != 0); 6. if (q->phead->next == NULL) 7. { 8. q->phead = q->ptatil = NULL; 9. } 10. else 11. { 12. QNode* next = q->phead->next; 13. free(q->phead); 14. q->phead = next; 15. } 16. q->size--; 17. }
要注意：分两种情况进行讨论。
2.6 获取队列头部元素
1. // 获取队列头部元素 2. QDataType QueueFront(Queue* q) 3. { 4. assert(q); 5. assert(q->phead); 6. return q->phead->data; 7. }
这里，直接用头指针返回值即可。
2.7 获取队列尾部元素
1. // 获取队列队尾元素 2. QDataType QueueBack(Queue* q) 3. { 4. assert(q); 5. assert(q->ptatil); 6. return q->ptatil->data; 7. }
和上面一样，运用指针获取值即可。
2.8 获取队列中有效元素个数
1. int QueueSize(Queue* q) 2. { 3. assert(q); 4. return q->size; 5. }
2.9 检测队列是否为空
1. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 2. bool QueueEmpty(Queue* q) 3. { 4. assert(q); 5. return q->size == 0; 6. }
三、 代码总览
Queue.h
1. #pragma once 2. #include<stdio.h> 3. #include<stdlib.h> 4. #include<stdbool.h> 5. #include<assert.h> 6. 7. typedef int QDataType; 8. // 链式结构：表示队列 9. typedef struct QListNode 10. { 11. struct QListNode* next; 12. QDataType data; 13. }QNode; 14. 15. // 队列的结构 16. typedef struct Queue 17. { 18. QNode* phead; 19. QNode* ptatil; 20. int size; 21. }Queue; 22. 23. // 初始化队列 24. void QueueInit(Queue* q); 25. // 队尾入队列 26. void QueuePush(Queue* q, QDataType data); 27. // 队头出队列 28. void QueuePop(Queue* q); 29. // 获取队列头部元素 30. QDataType QueueFront(Queue* q); 31. // 获取队列队尾元素 32. QDataType QueueBack(Queue* q); 33. // 获取队列中有效元素个数 34. int QueueSize(Queue* q); 35. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 36. bool QueueEmpty(Queue* q); 37. // 销毁队列 38. void QueueDestroy(Queue* q); 39.
Queue.c
1. #include"Queue.h" 2. 3. // 初始化队列 4. void QueueInit(Queue* q) 5. { 6. assert(q); 7. q->phead = q->ptatil = NULL; 8. q->size = 0; 9. } 10. // 队尾入队列 11. void QueuePush(Queue* q, QDataType data) 12. { 13. assert(q); 14. QNode* newnode = (QNode*)malloc(sizeof(QNode)); 15. if (newnode == NULL) 16. { 17. perror("malloc fail"); 18. return; 19. } 20. newnode->next = NULL; 21. newnode->data = data; 22. if (q->phead == NULL) 23. { 24. q->phead = q->ptatil = newnode; 25. } 26. else 27. { 28. q->ptatil->next = newnode;//记住这里是尾节点，不是头节点！！！ 29. q->ptatil = newnode; 30. } 31. q->size++; 32. } 33. // 队头出队列 34. void QueuePop(Queue* q) 35. { 36. assert(q); 37. assert(q->size != 0); 38. if (q->phead->next == NULL) 39. { 40. q->phead = q->ptatil = NULL; 41. } 42. else 43. { 44. QNode* next = q->phead->next; 45. free(q->phead); 46. q->phead = next; 47. } 48. q->size--; 49. } 50. // 获取队列头部元素 51. QDataType QueueFront(Queue* q) 52. { 53. assert(q); 54. assert(q->phead); 55. return q->phead->data; 56. } 57. // 获取队列队尾元素 58. QDataType QueueBack(Queue* q) 59. { 60. assert(q); 61. assert(q->ptatil); 62. return q->ptatil->data; 63. } 64. // 获取队列中有效元素个数 65. int QueueSize(Queue* q) 66. { 67. assert(q); 68. return q->size; 69. } 70. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 71. bool QueueEmpty(Queue* q) 72. { 73. assert(q); 74. return q->size == 0; 75. } 76. // 销毁队列 77. void QueueDestroy(Queue* q) 78. { 79. assert(q); 80. QNode* cur = q->phead; 81. while (cur) 82. { 83. QNode* next = cur->next; 84. free(cur); 85. cur = next; 86. } 87. q->phead = q->ptatil = NULL; 88. q->size = 0; 89. }
test.c
1. #include"Queue.h" 2. 3. int main() 4. { 5. Queue q; 6. QueueInit(&q); 7. QueuePush(&q, 1); 8. QueuePush(&q, 2); 9. QueuePush(&q, 3); 10. QueuePush(&q, 4); 11. while (!QueueEmpty(&q)) 12. { 13. printf("%d ", QueueFront(&q)); 14. QueuePop(& q); 15. } 16. printf("\n"); 17. QueueDestroy(&q); 18. return 0; 19. }
四、例题
来一道例题来练一练吧！
现有队列Q与栈S，初始时Q中的元素依次是 1,2,3,4,5,6(1在队头)，S 为空。若仅允许下列3种操作:①出队并输出出队元素;②出队并将出队元素入栈;③出栈并输出出栈元素，则不能得到的输出序列是()。
A. 1,2,5,6,4,3 B. 2,3,4,5,6,1 C. 3,4,5,6,1,2 D. 6.5.4.3.2.1
可得：答案为：C。
如果还有什么问题，可以私信也可在评论区留言！
完！
