二.队列的概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头
入队列是进行尾插,出队列是进行头删。如果还用顺序表式结构头删的时候代价太大,所以这里用节点式结构来实现队列。
队列的模拟实现
queue.h
queue.h中包含队列的基本功能:入列、出列、获取队首数据、获取队尾数据、获取队列中有效数据个数。
queue.c
1. void IntiQueue(Queue* queue)//初始化队列 2. { 3. assert(queue); 4. queue->phead = NULL; 5. queue->ptail = NULL; 6. queue->size = 0; 7. } 8. void PushQueue(Queue* queue, DateType n)//入列,尾插 9. { 10. assert(queue); 11. Node* newnode = (Node*)malloc(sizeof(Node));//创建新节点 12. assert(newnode); 13. newnode->date = n; 14. newnode->next = NULL; 15. 16. if (queue->ptail == NULL)//队列为空,相当于头插 17. { 18. assert(queue->phead==NULL); 19. 20. queue->phead = newnode;//头插 21. queue->ptail = newnode;//迭代ptail,利于下次尾插入列 22. } 23. else//队列不为空,正常尾插 24. { 25. queue->ptail->next = newnode;//尾插 26. queue->ptail = newnode;//迭代ptail 27. } 28. queue->size++;//有效数据加一 29. } 30. void PopQueue(Queue* queue)//头删出列 31. { 32. assert(queue); 33. assert(!QueueEmpty(queue));//保证队列不为空 34. 35. if (queue->phead->next == NULL)//一个节点,直接删 36. { 37. queue->phead = NULL; 38. queue->ptail = NULL; 39. } 40. else//多个节点 41. { 42. Node* next = queue->phead->next;//先保存头节点的下一个节点地址 43. free(queue->phead);//释放头节点空间 44. queue->phead = next;//将头节点设为next 45. } 46. queue->size--;//有效数据减一 47. } 48. bool QueueEmpty(Queue* queue)//判断队列是否为空 49. { 50. assert(queue); 51. return queue->size == 0;//有效数据为0,队列为空,返回true 52. } 53. DateType QueueFront(Queue* queue)//获取队列头元素 54. { 55. assert(queue); 56. assert(!QueueEmpty(queue));//队列非空 57. 58. return queue->phead->date;//直接返回 59. } 60. DateType QueueBank(Queue* queue)//获取队列尾元素 61. { 62. assert(queue); 63. assert(!QueueEmpty(queue));//队列非空 64. 65. return queue->ptail->date;//直接返回 66. } 67. int QueueSize(Queue* queue)//获取有效数据个数 68. { 69. assert(queue); 70. return queue->size;//直接返回 71. } 72. void DestoryQueue(Queue* queue)//销毁队列 73. { 74. assert(queue); 75. Node* cur = queue->phead; 76. while (cur)//循环销毁每一个节点 77. { 78. Node* next = cur->next; 79. free(cur); 80. cur = next; 81. } 82. queue->phead = NULL;//置空,防止野指针 83. queue->ptail = NULL;//置空,防止野指针 84. queue->size = 0; 85. }
总结:栈和队列只不过是顺序表与链表的子结构,关键在于实际问题中选取合适的数据结构,以及可以灵活应用数据结构解决问题。