一、 队列的概念以及结构
队列：只允许在 一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾 出队列：进行删除操作的一端称为 队头 【一端插入，一端删除，尾插，头删】
栈的使用场景：括号匹配、逆波兰表达式求解等的一些问题。还有把递归改为非递归（第一种方法，循环；第二种方法：栈）
队列的使用场景：公平排队；广度优先遍历；抽号机；
二、 队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。 涉及头删、尾插。所以可以用单链表。但是尾插又需要遍历单链表，可以用一个尾指针来解决这个问题。
Queue.h
1. #pragma once 2. #include <stdio.h> 3. #include <assert.h> 4. #include <stdlib.h> 5. #include <stdbool.h> 6. 7. 8. typedef int QDataType; 9. 10. typedef struct QueueNode 11. { 12. struct QueueNode* next; 13. QDataType data; 14. }QNode; 15. 16. typedef struct Queue 17. { 18. QNode* head; 19. QNode* tail; 20. }Queue; 21. 22. void QueueInit(Queue* pq); 23. void QueueDestory(Queue* pq); 24. void QueuePush(Queue* pq, QDataType x); 25. void QueuePop(Queue* pq); 26. bool QueueEmpty(Queue* pq); 27. size_t QueueSize(Queue* pq); 28. QDataType QueueFront(Queue* pq); 29. QDataType QueueBack(Queue* pq);
Queue.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include "queue.h" 3. 4. void QueueInit(Queue* pq) 5. { 6. assert(pq); 7. pq->head = pq->tail = NULL; 8. } 9. void QueueDestory(Queue* pq) 10. { 11. assert(pq); 12. QNode* cur = pq->head; 13. while (cur) 14. { 15. QNode* next = cur->next; 16. free(cur); 17. cur = next; 18. } 19. pq->head = pq->tail = NULL; 20. } 21. void QueuePush(Queue* pq, QDataType x) 22. { 23. assert(pq); 24. QNode* newnode = (QNode*)malloc(sizeof(QNode)); 25. assert(newnode); 26. newnode->next = NULL; 27. newnode->data = x; 28. if (pq->tail == NULL)//链表为空的情况 29. { 30. assert(pq->head == NULL);//双重保证链表为空 31. pq->head = pq->tail = newnode; 32. } 33. else 34. { 35. QNode* prev = pq->tail; 36. prev->next = newnode; 37. pq->tail = newnode; 38. } 39. } 40. //错误删除代码 41. //void QueuePop(Queue* pq) 42. //{ 43. // assert(pq); 44. // assert(pq->head && pq->tail); 45. // QNode* next = pq->head->next; 46. // free(pq->head);//在这里，如果删除最后一个元素的时候，tail指向的空间释放，tail就会成为野指针 47. // pq->head = next; 48. //} 49. void QueuePop(Queue* pq) 50. { 51. assert(pq); 52. assert(pq->head && pq->tail); 53. QNode* next = pq->head->next; 54. if (next == NULL) 55. { 56. free(pq->head); 57. pq->head =pq->tail = next; 58. } 59. else 60. { 61. free(pq->head); 62. pq->head = next; 63. } 64. } 65. 66. 67. bool QueueEmpty(Queue* pq) 68. { 69. assert(pq); 70. return pq->head == NULL; 71. } 72. 73. size_t QueueSize(Queue* pq) 74. { 75. assert(pq); 76. QNode* cur = pq->head; 77. size_t size = 0; 78. while (cur) 79. { 80. size++; 81. cur = cur->next; 82. } 83. return size; 84. } 85. QDataType QueueFront(Queue* pq) 86. { 87. assert(pq); 88. assert(pq->head); 89. return pq->head->data; 90. } 91. QDataType QueueBack(Queue* pq) 92. { 93. assert(pq); 94. assert(pq->tail); 95. return pq->tail->data; 96. }
注意：（1）size_t 就是unsigned int
（2）当出现a->b->c的时候，就要注意最后面的时候，是否会出现野指针。
三、习题
3.1 选择题
1.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作 后， front=rear=99 ，则循环队列中的元素个数为（ D）
A 1
B 2
C 99
D 0
2.以下( B)不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
3.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N,实际最多可存储N-1个数据。其队内有效长度为？(假设队头不存放数据)(B)
A (rear - front + N) % N + 1
B (rear - front + N) % N 因为rear指向的内容是空
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)
3.2 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
代码如下：
1. //定义一个栈的结构体，栈里面是两个队列 2. typedef struct { 3. Queue q1;//q1和q2分别是结构体 4. Queue q2; 5. } MyStack; 6. 7. //相当于初始化，由于需要返回的是结构体指针，所以不能在函数里创建一个结构体，返回结构体的地址，因为出了这个函数，又被销毁了。所以应该malloc一个结构体。 8. MyStack* myStackCreate() { 9. MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//结构体的地址 10. assert(pst); 11. QueueInit(&pst->q1);//->的优先级>&的优先级 12. QueueInit(&pst->q2);//两个队列初始化完成，就表示栈也初始化完成 13. return pst; 14. } 15. 16. void myStackPush(MyStack* obj, int x) { 17. assert(obj); 18. //在不为空的队列里面插入数， 19. if (!QueueEmpty(&obj->q1)) 20. { 21. QueuePush(&obj->q1,x); 22. } 23. else 24. { 25. QueuePush(&obj->q2,x); 26. } 27. } 28. //删除栈顶的数据，并返回栈顶的数据 29. int myStackPop(MyStack* obj) { 30. assert(obj); 31. Queue* emptyQ = &obj->q1; 32. Queue* nonEmptyQ = &obj->q2; 33. if (!QueueEmpty(&obj->q1)) 34. { 35. emptyQ = &obj->q2; 36. nonEmptyQ = &obj->q1; 37. } 38. while (QueueSize(nonEmptyQ) > 1) 39. { 40. int front = QueueFront(nonEmptyQ); 41. QueuePush(emptyQ, front); 42. QueuePop(nonEmptyQ); 43. } 44. int top = QueueFront(nonEmptyQ); 45. QueuePop(nonEmptyQ); 46. return top; 47. } 48. //栈顶的数据，就是队列的队尾的数据 49. int myStackTop(MyStack* obj) { 50. assert(obj); 51. if (!QueueEmpty(&obj->q1)) 52. { 53. return QueueBack(&obj->q1); 54. } 55. else 56. { 57. return QueueBack(&obj->q2); 58. } 59. } 60. //两个队列都为空，才能证明栈为空 61. bool myStackEmpty(MyStack* obj) { 62. assert(obj); 63. return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 64. } 65. 66. void myStackFree(MyStack* obj) { 67. assert(obj); 68. QueueDestory(&obj->q1); 69. QueueDestory(&obj->q2); 70. free(obj); 71. }
思路：入栈：push数据到不为空的队列；出栈：把不为空的队列数据前N-1导入另一个空队列，把最后一个剩下的删掉。【本质是保持一个队列存储数据，另外一个队列空着，要出栈时，空队列用来导数据】
