队列的概念
队列：只允许在一端插入数据，在另一端删除数据的特殊线性表，队列具有先进先出（First In First Out）的性质
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
可以使用数组和链表的结构实现队列，使用链表的结构实现更优一些，因为如果使用数组的结构实现队列，那么删除数据在队头进行，效率比较低，队列为空时，front=rear=NULL。
队列的实现
头文件 040-Queue.h
1. #pragma once 2. #include<stdio.h> 3. #include<stdbool.h> 4. #include<assert.h> 5. #include<stdlib.h> 6. 7. typedef int QDataType; 8. typedef struct QueueNode 9. { 10. struct QueueNode* next; 11. QDataType data; 12. }QueueNode; 13. 14. typedef struct Queue 15. { 16. QueueNode* head; 17. QueueNode* tail; 18. }Queue; 19. 20. //初始化 21. void QueueInit(Queue* pq); 22. 23. //销毁 24. void QueueDestroy(Queue* pq); 25. 26. //插入数据 27. void QueuePush(Queue* pq, QDataType x); 28. 29. //删除数据 30. void QueuePop(Queue* pq); 31. 32. //取队头数据 33. QDataType QueueFront(Queue* pq); 34. 35. //取队尾数据 36. QDataType QueueRear(Queue* pq); 37. 38. //判断队是否已满 39. bool QueueEmpty(Queue* pq); 40. 41. //求队列元素个数 42. int QueueSize(Queue* pq);
源文件 040-Queue.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include "040-Queue.h" 3. 4. //初始化 5. void QueueInit(Queue* pq) 6. { 7. pq->head = pq->tail = NULL; 8. } 9. 10. //销毁 11. void QueueDestroy(Queue* pq) 12. { 13. QueueNode* cur = pq->head; 14. while (cur) 15. { 16. QueueNode* next = cur->next; 17. free(cur); 18. cur = next; 19. } 20. pq->head = pq->tail = NULL; 21. } 22. 23. //插入数据 24. void QueuePush(Queue* pq, QDataType x) 25. { 26. assert(pq); 27. QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); 28. if (newNode == NULL) 29. { 30. printf("malloc fail\n"); 31. exit(-1); 32. } 33. 34. newNode->data = x; 35. newNode->next = NULL; 36. 37. //插入一个数据，尾指针+1，当尾指针为空时，队列为空 38. if (pq->tail == NULL) 39. { 40. pq->head = pq->tail = newNode; 41. } 42. else 43. { 44. pq->tail->next = newNode; 45. pq->tail = newNode; 46. } 47. } 48. 49. //删除数据 50. void QueuePop(Queue* pq) 51. { 52. assert(pq); 53. assert(!QueueEmpty(pq)); 54. if (pq->head->next == NULL) 55. { 56. free(pq->head); 57. pq->head = pq->tail = NULL; 58. } 59. else 60. { 61. QueueNode* next = pq->head->next; 62. free(pq->head); 63. pq->head = next; 64. } 65. } 66. 67. //取队头数据 68. QDataType QueueFront(Queue* pq) 69. { 70. assert(pq); 71. assert(!QueueEmpty(pq)); 72. 73. return pq->head->data; 74. } 75. 76. //取队尾数据 77. QDataType QueueRear(Queue* pq) 78. { 79. assert(pq); 80. assert(!QueueEmpty(pq)); 81. 82. return pq->tail->data; 83. } 84. 85. //判断队是否已满 86. bool QueueEmpty(Queue* pq) 87. { 88. assert(pq); 89. 90. return pq->head == NULL; 91. } 92. 93. //求队列元素个数 94. int QueueSize(Queue* pq) 95. { 96. 97. int size = 0; 98. QueueNode* cur = pq->head; 99. while (cur) 100. { 101. size++; 102. cur = cur->next; 103. } 104. return size; 105. 106. }
测试文件 040-test.c
1. #define _CRT_SECURE_NO_WARNINGS 1 2. #include"040-Queue.h" 3. void TestQueue() 4. { 5. Queue q; 6. QueueInit(&q); 7. QueuePush(&q, 1); 8. QueuePush(&q, 2); 9. 10. printf("%d ", QueueFront(&q)); 11. QueuePop(&q); 12. 13. printf("%d ", QueueFront(&q)); 14. QueuePop(&q); 15. 16. QueuePush(&q, 3); 17. QueuePush(&q, 4); 18. 19. while (!QueueEmpty(&q)) 20. { 21. printf("%d ", QueueFront(&q)); 22. QueuePop(&q); 23. } 24. 25. printf("\n"); 26. 27. QueueDestroy(&q); 28. } 29. 30. int main() 31. { 32. TestQueue(); 33. }
队列的应用
1.用两个队列实现一个栈 OJ链接
分析：栈的性质是后进先出，如先后入栈1,2,3,4，可以依次将其入到A队列中，如要4出队列，可以先将1,2,3放入B队列，返回A队列中的4。始终保持一个队列为空，一个队列不为空。
再入数据就入到不为空的队列里。
1. typedef int QDataType; 2. typedef struct QueueNode 3. { 4. struct QueueNode* next; 5. QDataType data; 6. }QueueNode; 7. 8. typedef struct Queue 9. { 10. QueueNode* head; 11. QueueNode* tail; 12. }Queue; 13. 14. //初始化 15. void QueueInit(Queue* pq); 16. 17. //销毁 18. void QueueDestroy(Queue* pq); 19. 20. //插入数据 21. void QueuePush(Queue* pq, QDataType x); 22. 23. //删除数据 24. void QueuePop(Queue* pq); 25. 26. //取队头数据 27. QDataType QueueFront(Queue* pq); 28. 29. //取队尾数据 30. QDataType QueueRear(Queue* pq); 31. 32. //判断队是否已满 33. bool QueueEmpty(Queue* pq); 34. 35. //求队列元素个数 36. int QueueSize(Queue* pq); 37. 38. //初始化 39. void QueueInit(Queue* pq) 40. { 41. pq->head = pq->tail = NULL; 42. } 43. 44. //销毁 45. void QueueDestroy(Queue* pq) 46. { 47. QueueNode* cur = pq->head; 48. while (cur) 49. { 50. QueueNode* next = cur->next; 51. free(cur); 52. cur = next; 53. } 54. pq->head = pq->tail = NULL; 55. } 56. 57. //插入数据 58. void QueuePush(Queue* pq, QDataType x) 59. { 60. assert(pq); 61. QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); 62. if (newNode == NULL) 63. { 64. printf("malloc fail\n"); 65. exit(-1); 66. } 67. 68. newNode->data = x; 69. newNode->next = NULL; 70. 71. //插入一个数据，尾指针+1，当尾指针为空时，队列为空 72. if (pq->tail == NULL) 73. { 74. pq->head = pq->tail = newNode; 75. } 76. else 77. { 78. pq->tail->next = newNode; 79. pq->tail = newNode; 80. } 81. } 82. 83. //删除数据 84. void QueuePop(Queue* pq) 85. { 86. assert(pq); 87. assert(!QueueEmpty(pq)); 88. if (pq->head->next == NULL) 89. { 90. free(pq->head); 91. pq->head = pq->tail = NULL; 92. } 93. else 94. { 95. QueueNode* next = pq->head->next; 96. free(pq->head); 97. pq->head = next; 98. } 99. } 100. 101. //取队头数据 102. QDataType QueueFront(Queue* pq) 103. { 104. assert(pq); 105. assert(!QueueEmpty(pq)); 106. 107. return pq->head->data; 108. } 109. 110. //取队尾数据 111. QDataType QueueRear(Queue* pq) 112. { 113. assert(pq); 114. assert(!QueueEmpty(pq)); 115. 116. return pq->tail->data; 117. } 118. 119. //判断队是否已满 120. bool QueueEmpty(Queue* pq) 121. { 122. assert(pq); 123. 124. return pq->head == NULL; 125. } 126. 127. //求队列元素个数 128. int QueueSize(Queue* pq) 129. { 130. 131. int size = 0; 132. QueueNode* cur = pq->head; 133. while (cur) 134. { 135. size++; 136. cur = cur->next; 137. } 138. return size; 139. 140. } 141. 142. typedef int STDataType; 143. typedef struct { 144. Queue q1; 145. Queue q2; 146. } MyStack; 147. 148. //建栈 149. MyStack* myStackCreate() { 150. 151. //不能这么写,return的是地址，除了函数st变量就销毁了，可以用malloc，在return 之后再free 152. //MyStack* st; 153. //return &st; 154. MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); 155. QueueInit(&obj->q1); 156. QueueInit(&obj->q2); 157. return obj; 158. } 159. 160. //入队 161. void myStackPush(MyStack* obj, int x) { 162. if(!QueueEmpty(&obj->q1)) 163. { 164. QueuePush(&obj->q1,x); 165. } 166. else 167. { 168. QueuePush(&obj->q2,x); 169. } 170. } 171. 172. //删除栈顶元素 173. int myStackPop(MyStack* obj) { 174. Queue* pEmpty = &obj->q1; 175. Queue* pNonoEmpty = &obj->q2; 176. if(!QueueEmpty(&obj->q1)) 177. { 178. pEmpty = &obj->q2; 179. pNonoEmpty = &obj->q1; 180. } 181. while(QueueSize(pNonoEmpty)>1) 182. { 183. QueuePush(pEmpty,QueueFront(pNonoEmpty)); 184. QueuePop(pNonoEmpty); 185. } 186. int front = QueueFront(pNonoEmpty); 187. QueuePop(pNonoEmpty); 188. return front; 189. } 190. 191. //返回栈顶元素 192. int myStackTop(MyStack* obj) { 193. if(!QueueEmpty(&obj->q1)) 194. { 195. return QueueRear(&obj->q1); 196. } 197. else 198. { 199. return QueueRear(&obj->q2); 200. } 201. } 202. 203. //判空 204. bool myStackEmpty(MyStack* obj) { 205. return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 206. } 207. 208. //释放栈 209. void myStackFree(MyStack* obj) { 210. QueueDestroy(&obj->q1); 211. QueueDestroy(&obj->q2); 212. free(obj); 213. }
分析：用两个栈实现队列，队列先进先出，如入队1，2，3，4，将其依次入到A栈，要出队，就要先出1，此时可以将2，3，4入栈到B栈，A栈中只留下1，1就可以从A栈出了。
如果再要出数据，可以从非空栈中出，
要入数据就入到空栈中，如入5 6 7，
因此可以固定从A入，从B出，如果B不为空，就从B出数据，如果B为空，就把A的数据依次入到B中。
1. typedef int STDataType; 2. struct Stack 3. { 4. STDataType* a; 5. int top;//栈顶，指向最后一个元素的下一个位置 6. int capacity;//容量，方便增容 7. }; 8. 9. typedef struct Stack Stack; 10. 11. //初始化 12. void StackInit(Stack* pst); 13. 14. //销毁 15. void StackDestroy(Stack* pst); 16. 17. //栈的性质就决定了只能在栈顶出入数据 18. //插入元素 19. void StackPush(Stack* pst, STDataType x); 20. 21. //删除元素 22. void StackPop(Stack* pst); 23. 24. //返回栈顶元素 25. STDataType StackTop(Stack* pst); 26. 27. //判断栈是否已满，空返回1，非空返回0 28. bool StackEmpty(Stack* pst); 29. 30. //求栈中元素个数 31. int StackSize(Stack* pst); 32. 33. //初始化 34. void StackInit(Stack* pst) 35. { 36. assert(pst); 37. pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); 38. pst->top = 0; 39. pst->capacity = 4; 40. } 41. 42. //销毁 43. void StackDestroy(Stack* pst) 44. { 45. assert(pst); 46. free(pst->a); 47. pst->a = NULL; 48. pst->capacity = pst->top = 0; 49. } 50. 51. //插入元素 52. void StackPush(Stack* pst, STDataType x) 53. { 54. if (pst->top == pst->capacity) 55. { 56. STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2); 57. if (tmp == NULL) 58. { 59. printf("realloc fail\n"); 60. exit(-1); 61. } 62. pst->a = tmp; 63. pst->capacity *= 2; 64. } 65. 66. pst->a[pst->top] = x; 67. pst->top++; 68. } 69. 70. //删除元素 71. void StackPop(Stack* pst) 72. { 73. assert(pst); 74. assert(!StackEmpty(pst)); 75. pst->top--; 76. } 77. 78. //返回栈顶元素 79. STDataType StackTop(Stack* pst) 80. { 81. assert(pst); 82. assert(!StackEmpty(pst)); 83. 84. return pst->a[pst->top - 1]; 85. } 86. 87. //判断栈是否已满，空返回1，非空返回0 88. bool StackEmpty(Stack* pst) 89. { 90. assert(pst); 91. return pst->top == 0; 92. } 93. 94. //求栈中元素个数 95. int StackSize(Stack* pst) 96. { 97. assert(pst); 98. return pst->top; 99. } 100. 101. typedef struct { 102. Stack s1; 103. Stack s2; 104. } MyQueue; 105. 106. //创建队列 107. MyQueue* myQueueCreate() { 108. MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); 109. StackInit(&obj->s1); 110. StackInit(&obj->s2); 111. 112. return obj; 113. } 114. 115. //入队 116. void myQueuePush(MyQueue* obj, int x) { 117. 118. StackPush(&obj->s1,x); 119. 120. } 121. 122. //返回队头元素 123. int myQueuePeek(MyQueue* obj) { 124. if(StackEmpty(&obj->s2))//s2为空，就把元素全部入到s2中 125. { 126. while(!StackEmpty(&obj->s1)) 127. { 128. StackPush(&obj->s2,StackTop(&obj->s1)); 129. StackPop(&obj->s1); 130. } 131. } 132. return StackTop(&obj->s2);//s2顶部元素就是队头元素 133. } 134. 135. //删除队头元素 136. int myQueuePop(MyQueue* obj) { 137. int ret = myQueuePeek(obj); //这里要传obj 138. StackPop(&obj->s2); 139. return ret; 140. 141. } 142. 143. //判断队空 144. bool myQueueEmpty(MyQueue* obj) { 145. return StackEmpty(&obj->s1) && StackEmpty(&obj->s2); 146. } 147. 148. //释放队列 149. void myQueueFree(MyQueue* obj) { 150. StackDestroy(&obj->s1); 151. StackDestroy(&obj->s2); 152. free(obj); 153. obj = NULL; 154. }
分析：循环队列和普通队列区别在于：
循环队列如何判空和判断满了？因为空的时候front和tail指向同一个节点，满的时候，front和tail也指向同一个节点。可以空出一个节点不存储数据，当front=tail时队空，当tail的下一个为front时，队满。
1. #define _CRT_SECURE_NO_WARNINGS 1 2. typedef struct { 3. int* a; 4. int k; 5. int front; 6. int tail; 7. }MyCircularQueue; 8. 9. //创建队列 10. MyCircularQueue* myCircularQueueCreate(int k) { 11. MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); 12. obj->a = (int*)malloc(sizeof(int) * (k + 1)); 13. obj->k = k; 14. obj->front = 0; 15. obj->tail = 0; 16. return obj; 17. } 18. 19. //判断队满 20. bool myCircularQueueIsFull(MyCircularQueue* obj) { 21. int tailNext = obj->tail + 1; 22. if (tailNext == obj->k + 1) 23. { 24. tailNext = 0; 25. } 26. return tailNext == obj->front; 27. } 28. 29. //入队 30. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 31. if (myCircularQueueIsFull(obj)) 32. { 33. return false; 34. } 35. else 36. { 37. obj->a[obj->tail] = value; 38. obj->tail++; 39. 40. obj->tail %= (obj->k + 1); 41. 42. return true; 43. } 44. 45. } 46. 47. //判断队空 48. bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 49. return obj->front == obj->tail; 50. } 51. 52. bool myCircularQueueDeQueue(MyCircularQueue* obj) { 53. if (myCircularQueueIsEmpty(obj)) 54. { 55. return false; 56. } 57. else 58. { 59. obj->front++; 60. if (obj->front == obj->k + 1) 61. { 62. obj->front = 0; 63. } 64. return true; 65. } 66. } 67. 68. //返回队头元素 69. int myCircularQueueFront(MyCircularQueue* obj) { 70. //printf("%d",myCircularQueueIsEmpty(obj)); 71. 72. if(myCircularQueueIsEmpty(obj)) 73. { 74. return -1; 75. } 76. return obj->a[obj->front]; 77. } 78. 79. //返回队尾元素 80. int myCircularQueueRear(MyCircularQueue* obj) { 81. if(myCircularQueueIsEmpty(obj)) 82. { 83. return -1; 84. } 85. int tailPrev = obj->tail - 1;//tail指向最后一个元素的下一个位置，最后一个元素的位置是tail-1 86. if (tailPrev == -1) 87. { 88. tailPrev = obj->k; 89. } 90. return obj->a[tailPrev]; 91. } 92. 93. //释放队列 94. void myCircularQueueFree(MyCircularQueue* obj) { 95. free(obj->a); 96. free(obj); 97. }
