当前位置:   article > 正文

【C语言】队列的实现_c语言队列实现代码

c语言队列实现代码

目录

队列的概念和结构

 队列的模拟实现:

用代码定义队列的结构

队列基本功能的实现

 初始化队列

队尾入数据

对头出数据

获取对列对头元素

获取队列对尾元素

判空

获取队列中有效元素的个数

销毁队列

完整代码

头文件

源文件


队列的概念和结构

队列的概念队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列中的数据结构遵循先进先出FIFO(First In First Out)或后进后出的原则。

入队列进行插入操作的一端称为队尾

出队列进行删除操作的一端称为队头

队列的结构

队列的代码实现

要实现队列无非也是现在我们学的两种结构:数组链式结构。

但是用链式结构来实现队列是更好的,这里刚好和栈相反。因为队列是在一端插入,另一端进行删除刚好对应的是尾插和头删,使用顺序表的头删效率就不是很高,而链式结构无论插入还是删除效率都很高。

用代码定义队列的结构

  1. typedef int QDataType;
  2. typedef struct QueueNode
  3. {
  4. struct QueueNode* next;
  5. QDataType data;
  6. }QNode;
  7. typedef struct Queue
  8. {
  9. int size;
  10. QNode* head;
  11. QNode* tail;
  12. }Queue;

这里用到了两个结构体,因为我们不仅要有链式的结构,还要标识队列的头和尾,这样方便我们进行头删和尾插,至于size则是用来记录队列中的元素个数的。

队列基本功能的实现

  1. //初始化队列
  2. void QueueInit(Queue* pq);
  3. //销毁队列
  4. void QueueDestroy(Queue* pq);
  5. //对尾入队列
  6. void QueuePush(Queue* pq, QDataType x);
  7. //对头出队列
  8. void QueuePop(Queue* pq);
  9. //获取对列头部元素
  10. QDataType QueueFront(Queue* pq);
  11. //获取队列队尾元素
  12. QDataType QueueBack(Queue* pq);
  13. //判空
  14. bool QueueEmpty(Queue* pq);
  15. //获取队列中有效元素的个数
  16. int QueueSize(Queue* pq);

 初始化队列

  1. void QueueInit(Queue* pq)
  2. {
  3. assert(pq);
  4. pq->size = 0;
  5. pq->head = pq->tail = NULL;
  6. }

 首先判断是否为空,然后把size置为0,头和尾都置成空

队尾入数据

  1. void QueuePush(Queue* pq, QDataType x)
  2. {
  3. assert(pq);
  4. QNode* newnode = (QNode*)malloc(sizeof(QNode));
  5. if (newnode == NULL)
  6. {
  7. printf("malloc fail\n");
  8. exit(-1);
  9. }
  10. newnode->data = x;
  11. newnode->next = NULL;
  12. if (pq->tail == NULL)
  13. {
  14. pq->head = pq->tail = newnode;
  15. }
  16. else
  17. {
  18. pq->tail->next = newnode;
  19. pq->tail = newnode;
  20. }
  21. pq->size++;
  22. }

首先肯定是要申请节点,然后进行插入 ,但是插入也分两种情况。

第一种情况:一个数据都没有,head和tail同时指向空

第二种情况:已经有数据了直接在tail后面链接就行了

最后别忘了将size++。

对头出数据

  1. void QueuePop(Queue* pq)
  2. {
  3. assert(pq);
  4. assert(!QueueEmpty(pq));
  5. //1.一个结点
  6. if (pq->head->next == NULL)
  7. {
  8. free(pq->head);
  9. pq->head = pq->tail = NULL;//避免野指针问题
  10. }
  11. //2.多个结点
  12. else
  13. {
  14. QNode* next = pq->head->next;
  15. free(pq->head);
  16. pq->head = next;
  17. }
  18. pq->size--;
  19. }

 这里的删除也是要判断是只有一个结点还是有多个结点的情况

只有一个结点或者删到只有一个结点

就要把头free掉并且头指针和尾都要置成空

有多个节点

创建一个指针,存放head的下一个结点,接着free掉头指针,然后更新一下头指针

还有别忘了size要减减

 下面这些就没啥好讲的了,比较简单,相信大家应该可以轻松拿捏。

获取对列对头元素

  1. QDataType QueueFront(Queue* pq)
  2. {
  3. assert(pq);
  4. assert(!QueueEmpty(pq));
  5. return pq->head->data;
  6. }

获取队列对尾元素

  1. QDataType QueueBack(Queue* pq)
  2. {
  3. assert(pq);
  4. assert(!QueueEmpty(pq));
  5. return pq->tail->data;
  6. }

判空

  1. bool QueueEmpty(Queue* pq)
  2. {
  3. assert(pq);
  4. return pq->head == NULL;
  5. }

获取队列中有效元素的个数

  1. int QueueSize(Queue* pq)
  2. {
  3. assert(pq);
  4. return pq->size;
  5. }

这里你也可以遍历一遍这个队列进行计数,不过效率比较低。

销毁队列

  1. void QueueDestroy(Queue* pq)
  2. {
  3. assert(pq);
  4. QNode* cur = pq->head;
  5. while (cur)
  6. {
  7. QNode* next = cur->next;
  8. free(cur);
  9. cur = next;
  10. }
  11. pq->head = pq->tail = NULL;
  12. }

完整代码

queue.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <assert.h>
  4. #include <stdlib.h>
  5. #include <stdbool.h>
  6. typedef int QDataType;
  7. typedef struct QueueNode
  8. {
  9. struct QueueNode* next;
  10. QDataType data;
  11. }QNode;
  12. typedef struct Queue
  13. {
  14. int size;
  15. QNode* head;
  16. QNode* tail;
  17. }Queue;
  18. //初始化队列
  19. void QueueInit(Queue* pq);
  20. //销毁队列
  21. void QueueDestroy(Queue* pq);
  22. //对尾入队列
  23. void QueuePush(Queue* pq, QDataType x);
  24. //对头出队列
  25. void QueuePop(Queue* pq);
  26. //获取对列头部元素
  27. QDataType QueueFront(Queue* pq);
  28. //获取队列队尾元素
  29. QDataType QueueBack(Queue* pq);
  30. //判空
  31. bool QueueEmpty(Queue* pq);
  32. //获取队列中有效元素的个数
  33. int QueueSize(Queue* pq);

queue.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "Queue.h"
  3. void QueueInit(Queue* pq)
  4. {
  5. assert(pq);
  6. pq->size = 0;
  7. pq->head = pq->tail = NULL;
  8. }
  9. void QueueDestroy(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. if (newnode == NULL)
  26. {
  27. printf("malloc fail\n");
  28. exit(-1);
  29. }
  30. newnode->data = x;
  31. newnode->next = NULL;
  32. if (pq->tail == NULL)
  33. {
  34. pq->head = pq->tail = newnode;
  35. }
  36. else
  37. {
  38. pq->tail->next = newnode;
  39. pq->tail = newnode;
  40. }
  41. pq->size++;
  42. }
  43. void QueuePop(Queue* pq)
  44. {
  45. assert(pq);
  46. assert(!QueueEmpty(pq));
  47. //1.一个节点
  48. if (pq->head->next == NULL)
  49. {
  50. free(pq->head);
  51. pq->head = pq->tail = NULL;//避免野指针问题
  52. }
  53. //2.多个节点
  54. else
  55. {
  56. QNode* next = pq->head->next;
  57. free(pq->head);
  58. pq->head = next;
  59. }
  60. pq->size--;
  61. }
  62. QDataType QueueFront(Queue* pq)
  63. {
  64. assert(pq);
  65. assert(!QueueEmpty(pq));
  66. return pq->head->data;
  67. }
  68. QDataType QueueBack(Queue* pq)
  69. {
  70. assert(pq);
  71. assert(!QueueEmpty(pq));
  72. return pq->tail->data;
  73. }
  74. bool QueueEmpty(Queue* pq)
  75. {
  76. assert(pq);
  77. return pq->head == NULL;
  78. }
  79. int QueueSize(Queue* pq)
  80. {
  81. assert(pq);
  82. return pq->size;
  83. }

 觉得内容有用的话,就给博主三连吧!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/918175
推荐阅读
相关标签
  

闽ICP备14008679号