devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

队列的模拟实现（单链链表模拟）_利用循环单链表模拟实现队列操作的出队和入队

作者：木道寻08 | 2024-08-10 21:53:33

赞

踩

利用循环单链表模拟实现队列操作的出队和入队

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出，后进后出特特点。

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 。

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

目录

队列的结构体创建 

队列的函数接口

void QueueInit(Queue* q)

void QueuePush(Queue* q, QDataType x)

void QueuePop(Queue* q)

QDataType QueueTail(Queue* q)

QDataType QueueHead(Queue* q)

int QueueSize(Queue* q)

void QueueDestroy(Queue* q)

bool QueueEmpty(Queue* q)

模拟队列的完整代码

Queue.c

Queue.c

测试代码test.c

队列的结构体创建 

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

typedef int QDataType;
typedef struct QueueNode //就这个结构体用来存放一个结点
{
    struct QueueNode* next; //定义一个指针，存放指向下一个结点的地址
    QDataType data;//存放当前结点的一个数据
}QNode;
typedef struct Queue //创建一个结构体，存放头结点和尾结点
{
    QNode* head; //头结点
    QNode* tail; //尾结点
}Queue;

这样的好处是，在后来定义变量时：Queue q;传参时可以传&q，接收时用一级指针就可以操作，因为在这里一级指针足够可以改变结构体里面的结点。

队列的函数接口

  1. //队列初始化
  2. void QueueInit(Queue* q);
  3. //插入数据
  4. void QueuePush(Queue* q, QDataType x);
  5. //删除数据
  6. void QueuePop(Queue* q);
  7. //取队尾数据
  8. QDataType QueueTail(Queue* q);
  9. //取队头数据
  10. QDataType QueueHead(Queue* q);
  11. //记录队列中数据的个数
  12. int QueueSize(Queue* q);
  13. //销毁队列
  14. void QueueDestroy(Queue* q);
  15. //判断队列里是否有数据
  16. bool QueueEmpty(Queue* q);

void QueueInit(Queue* q)

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

对Queue里面的两个结点进行初始化

void QueueInit(Queue* q)
{
    assert(q);//判断q是否为有效地址
    q->head = NULL; //头结点置空，避免被当成野指针乱用
    q->tail = NULL;//尾结点置空，避免被当成野指针乱用
}

void QueuePush(Queue* q, QDataType x)

  1. void QueuePush(Queue* q, QDataType x)
  2. {
  3. 	assert(q);
  4. 	//开辟一个结点
  5. 	QNode* tmp = (QNode*)malloc(sizeof(QNode));
  6. 	if (tmp == NULL)
  7. 	{
  8. 		printf("malloc fail\n");
  9. 		exit(-1);
  10. 	}
  11. 	tmp->data = x;
  12. 	tmp->next = NULL;
  13. 	if (QueueEmpty(q))
  14. 	{
  15. 		q->head = q->tail = tmp;
  16. 	}
  17. 	else
  18. 	{
  19. 		q->tail->next = tmp;
  20. 		q->tail = tmp;
  21. 	}
  22. }

在队尾插入数据

void QueuePush(Queue* q, QDataType x)
{
    assert(q);

     //插入数据后需要申请一块空间，来作为结点
    QNode* tmp = (QNode*)malloc(sizeof(QNode));    //开辟一个结点
    if (tmp == NULL) //判断结点是否开辟成功
    {
        printf("malloc fail\n");
        exit(-1);
    }
    tmp->data = x; //结点存放一个数据
    tmp->next = NULL;//结点指向下一个地址为空，避免被当成野指针乱用
    if (QueueEmpty(q)) //如果队列中为空时
    {
        q->head = q->tail = tmp; //头结点和尾结点都指向第一个新新结点
    }

    //如果不判断的话，头结点一直是指向NULL的，在插入第一个结点时，tail是空结点，不          能指向下一个结点
    else //当头结点不为空时
    {
        q->tail->next = tmp;//尾结点指向新结点结点
        q->tail = tmp; //尾结点的地址变成新结点的地址
    }
}

void QueuePop(Queue* q)

  1. void QueuePop(Queue* q)
  2. {
  3. 	assert(q);
  4. 	assert(!QueueEmpty(q));
  5. 	QNode* next = q->head->next;
  6. 	free(q->head);
  7. 	q->head = next;
  8. 	if (q->head == NULL)
  9. 	{
  10. 		q->tail = NULL;
  11. 	}
  12. }

删除队列中头结点的数据

void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));//判断队列是否为空，不为空的话，就继续
    QNode* next = q->head->next; //提前记录好第一个结点的下一个结点的位置
    free(q->head);//释放第一个结点的空间
    q->head = next;//头结点地址变成next,即原链表第二个结点的地址，这样就删除了头结点     了，在这里不用分情况，即使next为NULL，pop后head和tail都为NULL了,相当于队列中没     有节点了

    if (q->head == NULL)//如果头结点为空了（不断头删），说明没有数据了，尾结点指向的      空间被释放了，但是尾结点还记录原来的地址，这时候尾结点变成野指针了
    {
        q->tail = NULL;//这时候尾结点要置空
    }

如果么有这个if语句，如图：


}

 

QDataType QueueTail(Queue* q)

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

返回队尾的数据

QDataType QueueTail(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->tail->data; //q指向队尾的结点的数据
}

QDataType QueueHead(Queue* q)

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

返回队头的数据

QDataType QueueHead(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->head->data;//q指向队头的结点的数据
}

int QueueSize(Queue* q)

  1. int QueueSize(Queue* q)
  2. {
  3. 	assert(q);
  4. 	QNode* cur = q->head;
  5. 	int size = 0;
  6. 	while (cur)
  7. 	{
  8. 		cur = cur->next;
  9. 		size++;
  10. 	}
  11. 	return size;
  12. }

记录队列中结点的个数

int QueueSize(Queue* q)
{
    assert(q);
    QNode* cur = q->head;//cur记录头结点，在遍历的过程中，cur在改变，而头结点就不会                                               被误改了
    int size = 0; //记录结点个数
    while (cur) //当cur为空时就结束循环，这时候，队列中不为空的结点都已经被遍历一遍了
    {
        cur = cur->next; //cur不断指向下一个
        size++; //每次经过一个结点，个数加1
    }
    return size;//返回结点个数
}

void QueueDestroy(Queue* q)

  1. void QueueDestroy(Queue* q)
  2. {
  3. 	assert(q);
  4. 	QNode* cur = q->head;
  5. 	while (cur)
  6. 	{
  7. 		QNode* next = cur->next;
  8. 		free(cur);
  9. 		cur = next;
  10. 	}
  11. 	//空间释放完之后，头结点和尾结点还记着原来的地址，在这里需要置空
  12. 	q->tail = q->head = NULL;
  13. }

对在堆区上开辟的队列空间的销毁

void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* cur = q->head; //cur记录头结点，用来遍历结点
    while (cur)//当cur为空时就结束循环，这时候，队列中不为空的结点都已经被遍历一遍了
    {
        QNode* next = cur->next; //next提前记录下一个结点，防止当前结点销毁后，下一个结                                                     点的地址就找不到了
        free(cur);//释放当前结点
        cur = next;//cur变成提前记录好的next
    }
    //空间释放完之后，头结点和尾结点还记着原来的地址，在这里需要置空
    q->tail = q->head = NULL;
}

bool QueueEmpty(Queue* q)

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

判断队列中是否为空

bool QueueEmpty(Queue* q)
{
    assert(q);
    return  q->head==NULL; //如果头结点为空就返回真（true），否则返回假（false）

    //因为头结点指向空时意味着，尾结点也指向空，这时候队列就为空了
}

模拟队列的完整代码

Queue.c

  1. #define  _CRT_SECURE_NO_WARNINGS 1
  2. #pragma once
  3. #include<stdio.h>
  4. #include<stdbool.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7.  
  8. typedef int QDataType;
  9. typedef struct QueueNode
  10. {
  11. 	struct QueueNode* next;
  12. 	QDataType data;
  13. }QNode;
  14. typedef struct Queue
  15. {
  16. 	QNode* head;
  17. 	QNode* tail;
  18. }Queue;
  19.  
  20. //队列初始化
  21. void QueueInit(Queue* q);
  22. //插入数据
  23. void QueuePush(Queue* q, QDataType x);
  24. //删除数据
  25. void QueuePop(Queue* q);
  26. //取队尾数据
  27. QDataType QueueTail(Queue* q);
  28. //取队头数据
  29. QDataType QueueHead(Queue* q);
  30. //记录队列中数据的个数
  31. int QueueSize(Queue* q);
  32. //销毁队列
  33. void QueueDestroy(Queue* q);
  34. //判断队列里是否有数据
  35. bool QueueEmpty(Queue* q);

Queue.c

  1. #define  _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3.  
  4. void QueueInit(Queue* q)
  5. {
  6. 	assert(q);
  7. 	q->head = NULL;
  8. 	q->tail = NULL;
  9. }
  10.  
  11. void QueuePush(Queue* q, QDataType x)
  12. {
  13. 	assert(q);
  14. 	//开辟一个结点
  15. 	QNode* tmp = (QNode*)malloc(sizeof(QNode));
  16. 	if (tmp == NULL)
  17. 	{
  18. 		printf("malloc fail\n");
  19. 		exit(-1);
  20. 	}
  21. 	tmp->data = x;
  22. 	tmp->next = NULL;
  23. 	if (QueueEmpty(q))
  24. 	{
  25. 		q->head = q->tail = tmp;
  26. 	}
  27. 	else
  28. 	{
  29. 		q->tail->next = tmp;
  30. 		q->tail = tmp;
  31. 	}
  32. }
  33.  
  34. void QueuePop(Queue* q)
  35. {
  36. 	assert(q);
  37. 	assert(!QueueEmpty(q));
  38. 	QNode* next = q->head->next;
  39. 	free(q->head);
  40. 	q->head = next;
  41. 	if (q->head == NULL)
  42. 	{
  43. 		q->tail = NULL;
  44. 	}
  45. }
  46.  
  47. QDataType QueueTail(Queue* q)
  48. {
  49. 	assert(q);
  50. 	assert(!QueueEmpty(q));
  51. 	return q->tail->data;
  52. }
  53.  
  54. QDataType QueueHead(Queue* q)
  55. {
  56. 	assert(q);
  57. 	assert(!QueueEmpty(q));
  58. 	return q->head->data;
  59. }
  60.  
  61. int QueueSize(Queue* q)
  62. {
  63. 	assert(q);
  64. 	QNode* cur = q->head;
  65. 	int size = 0;
  66. 	while (cur)
  67. 	{
  68. 		cur = cur->next;
  69. 		size++;
  70. 	}
  71. 	return size;
  72. }
  73.  
  74. void QueueDestroy(Queue* q)
  75. {
  76. 	assert(q);
  77. 	QNode* cur = q->head;
  78. 	while (cur)
  79. 	{
  80. 		QNode* next = cur->next;
  81. 		free(cur);
  82. 		cur = next;
  83. 	}
  84. 	//空间释放完之后，头结点和尾结点还记着原来的地址，在这里需要置空
  85. 	q->tail = q->head = NULL;
  86. }
  87.  
  88. bool QueueEmpty(Queue* q)
  89. {
  90. 	assert(q);
  91. 	return  q->head==NULL;
  92. }

测试代码test.c

  1. #define  _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3.  
  4. void QueueTest1()
  5. {
  6. 	Queue q;
  7. 	QueueInit(&q);
  8. 	QueuePush(&q, 1);
  9. 	QueuePush(&q, 2);
  10. 	QueuePush(&q, 3);
  11. 	QueuePush(&q, 4);
  12.  
  13. 	QDataType tmp = QueueHead(&q);
  14. 	printf("%d\n", tmp);
  15.  
  16.      tmp = QueueTail(&q);
  17. 	printf("%d\n", tmp);
  18.  
  19. 	QueuePop(&q);
  20. 	tmp = QueueSize(&q);
  21. 	tmp = QueueHead(&q);
  22. 	printf("%d\n", tmp);
  23.  
  24. 	QueuePush(&q, 4);
  25. 	QueuePush(&q, 4);
  26. 	QueuePop(&q);
  27. 	tmp = QueueSize(&q);
  28. 	printf("%d\n", tmp);
  29.  
  30. }
  31. int main()
  32. {
  33. 	QueueTest1();
  34. 	return 0;
  35. }

测试结果：

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号