• 【数据结构】— 『队列』的实现以及LeetCode队列练习题

     ꧁   各位大佬们好！很荣幸能够得到您的访问，让我们一起在编程道路上任重道远！꧂

    ☙ 博客专栏：【数据结构初阶】❧

    ⛅ 本篇内容简介：数据结构初阶中的队列的实现以及LeetCode练习！

    ⭐ 了解作者：励志成为一名编程大牛的学子，目前是大二的编程小白。

    ✍励志术语：编程道路的乏味，让我们一起学习变得有趣！

    文章目录

    🌔 队列的概念及结构

    🌗 队列的实现

    🌒 队列的链式结构

     🌒 队列的初始化

     🌒 队尾入数据

     🌒 队头出数据

    🌒 获取队头的数据

    🌒 获取队尾的数据

    🌒 获取队列有效元素个数

    🌒 判断队列是否为空

    🌒 队列的销毁

    🌒 测试队列接口功能

     🌔 队列源代码

    🌗 Queue.c文件

    🌗 Queue.h文件

    🌗 test.c文件

    🌔 225.用队列实现栈

    🌗 题解思路

     🌗 题解代码

    🌔 232.用栈实现队列

     🌗 题解思路

    🌗 题解代码

    🌗 结束语

    🌔 队列的概念及结构

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

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

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

    🌗 队列的实现

    队列可以是数组或者链表的结构实现，但是使用链表的结构实现更优一点。因为如果使用数组的结构，出队列在数组头上的数据，效率会比较低。在这里我们使用链表来实现队列。（数组不适合数组头频繁删除或者数组中插入数据）。

    🌒 队列的链式结构

    1. //队列的链式结构
    2. typedef int QDataType;
    3.  
    4. typedef struct QListNode
    5. {
    6. 	struct QListNode* next;
    7. 	QDataType Data;
    8. }QNode;
    9.  
    10. //队列的结构
    11. typedef struct Queue
    12. {
    13. 	QNode* front;
    14. 	QNode* back;
    15. 	int size;//记录队列节点的个数
    16. }Queue;

     🌒 队列的初始化

    初始化队列就是要使头指针与尾指针都置为空，将size也置为空。

    1. void QueueInit(Queue* pq)
    2. {
    3. 	//断言队列不能为空
    4. 	assert(pq);
    5. 	pq->front = pq->back = NULL;
    6. 	pq->size = 0;
    7. }

     🌒 队尾入数据

    首先我们要先创造新的要插入的节点，1.如果是第一个插入数据，将头指针与尾指针都指向newnode；2.平常的尾插，先将newnode尾插到back指针后，再将back指针指向尾节点。

    1. void QueuePush(Queue* pq, QDataType x)
    2. {
    3. 	assert(pq);
    4. 	//先创造节点，再进行链接
    5. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    6. 	if (newnode == NULL)
    7. 	{
    8. 		perror("malloc fail");
    9. 		exit(-1);
    10. 	}
    11. 	//初始化节点
    12. 	newnode->Data = x;
    13. 	newnode->next = NULL;
    14.  
    15. 	//链接，考虑尾节点是空，还是非空
    16. 	if (pq->back == NULL)
    17. 	{
    18. 		pq->front = pq->back = newnode;
    19. 	}
    20. 	else
    21. 	{
    22. 		pq->back->next = newnode;
    23. 		pq->back = newnode;
    24. 	}
    25. 	pq->size++;//队列节点++
    26. }

     🌒 队头出数据

    队头出数据时，当队头为空时就不能再出数据了，需要进行判空处理。

    1. 当队列只剩余一个数据时，如果直接free，会造成back的野指针问题，所以我们需要单独判断这种情况。

    2. 我们需要记录要删除的节点，再将front指向下一个，最后置空。

    1. void QueuePop(Queue* pq)
    2. {
    3. 	assert(pq);
    4. 	//判断只剩一个数据时
    5. 	if (pq->front == NULL)
    6. 	{
    7. 		free(pq->front);
    8. 		pq->front = pq->back = NULL;
    9. 	}
    10. 	else
    11. 	{
    12. 		QNode* del = pq->front;
    13. 		pq->front = pq->front->next;
    14. 		free(del);
    15. 		del = NULL;
    16. 	}
    17. 	pq->size--;//出数据需要--size
    18. }

    🌒 获取队头的数据

    1. //获取队头的数据
    2. QDataType QueueFront(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	assert(!QueueEmpty(pq));
    6.  
    7. 	return pq->front->Data;
    8. }

    🌒 获取队尾的数据

    1. //获取队尾的数据
    2. QDataType QueueBack(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	assert(!QueueEmpty(pq));
    6.  
    7. 	return pq->back->Data;
    8.  
    9. }

    🌒 获取队列有效元素个数

    因为我们在队列的结构体中加上了size记录元素个数，所以我们在这里可以直接返回。

    1. //获取队列中有效元素的个数
    2. int QueueSize(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	return pq->size;
    6. }

    🌒 判断队列是否为空

    如果队列为空返回非0值，如果是非空返回0。

    1. //队列的判空
    2. bool QueueEmpty(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	return pq->front == NULL && pq->back == NULL;
    6. }

    🌒 队列的销毁

    因为我们这里使用链表实现，所以我们要将链表的节点，一个一个释放。

    1. //队列的销毁
    2. void QueueDestroy(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	QNode* cur = pq->front;
    6. 	while (cur != NULL)
    7. 	{
    8. 		QNode* del = cur;
    9. 		cur = cur->next;
    10. 		free(del);
    11. 	}
    12. 	pq->front = pq->back = NULL;
    13. }

    🌒 测试队列接口功能

    1. int main()
    2. {
    3. 	Queue q;
    4. 	QueueInit(&q);
    5.  
    6. 	//队尾插入数据
    7. 	QueuePush(&q, 1);
    8. 	QueuePush(&q, 2);
    9. 	QueuePush(&q, 3);
    10. 	QueuePush(&q, 4);
    11. 	QueuePush(&q, 5);
    12.  
    13. 	while (!QueueEmpty(&q))
    14. 	{
    15. 		//获取队头的数据
    16. 		printf("%d ", QueueFront(&q));
    17. 		QueuePop(&q);
    18. 	}
    19. 	printf("\n");
    20. 	
    21. 	QueueDestroy(&q);
    22.  
    23. 	return 0;
    24. }

     🌔 队列源代码

    🌗 Queue.c文件

    1. #include"Queue.h"
    2.  
    3. void QueueInit(Queue* pq)
    4. {
    5. 	//断言队列不能为空
    6. 	assert(pq);
    7. 	pq->front = pq->back = NULL;
    8. 	pq->size = 0;
    9. }
    10.  
    11. void QueuePush(Queue* pq, QDataType x)
    12. {
    13. 	assert(pq);
    14. 	//先创造节点，再进行链接
    15. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    16. 	if (newnode == NULL)
    17. 	{
    18. 		perror("malloc fail");
    19. 		exit(-1);
    20. 	}
    21. 	//初始化节点
    22. 	newnode->Data = x;
    23. 	newnode->next = NULL;
    24.  
    25. 	//链接，考虑尾节点是空，还是非空
    26. 	if (pq->back == NULL)
    27. 	{
    28. 		pq->front = pq->back = newnode;
    29. 	}
    30. 	else
    31. 	{
    32. 		pq->back->next = newnode;
    33. 		pq->back = newnode;
    34. 	}
    35. 	pq->size++;//队列节点++
    36. }
    37.  
    38. void QueuePop(Queue* pq)
    39. {
    40. 	assert(pq);
    41. 	assert(!QueueEmpty(pq));
    42. 	//判断只剩一个数据时
    43. 	if (pq->front == NULL)
    44. 	{
    45. 		free(pq->front);
    46. 		pq->front = pq->back = NULL;
    47. 	}
    48. 	else
    49. 	{
    50. 		QNode* del = pq->front;
    51. 		pq->front = pq->front->next;
    52. 		free(del);
    53. 		del = NULL;
    54. 	}
    55. 	pq->size--;//出数据需要--size
    56. }
    57.  
    58. //获取队头的数据
    59. QDataType QueueFront(Queue* pq)
    60. {
    61. 	assert(pq);
    62. 	assert(!QueueEmpty(pq));
    63.  
    64. 	return pq->front->Data;
    65. }
    66.  
    67. //获取队尾的数据
    68. QDataType QueueBack(Queue* pq)
    69. {
    70. 	assert(pq);
    71. 	assert(!QueueEmpty(pq));
    72.  
    73. 	return pq->back->Data;
    74.  
    75. }
    76.  
    77. //获取队列中有效元素的个数
    78. int QueueSize(Queue* pq)
    79. {
    80. 	assert(pq);
    81. 	return pq->size;
    82. }
    83.  
    84. //队列的判空
    85. bool QueueEmpty(Queue* pq)
    86. {
    87. 	assert(pq);
    88. 	return pq->front == NULL && pq->back == NULL;
    89. }
    90.  
    91. //队列的销毁
    92. void QueueDestroy(Queue* pq)
    93. {
    94. 	assert(pq);
    95. 	QNode* cur = pq->front;
    96. 	while (cur != NULL)
    97. 	{
    98. 		QNode* del = cur;
    99. 		cur = cur->next;
    100. 		free(del);
    101. 	}
    102. 	pq->front = pq->back = NULL;
    103. }

    🌗 Queue.h文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #pragma once
    3.  
    4. #include<stdio.h>
    5. #include<assert.h>
    6. #include<stdlib.h>
    7. #include<stdbool.h>
    8.  
    9. //队列的链式结构
    10. typedef int QDataType;
    11.  
    12. typedef struct QListNode
    13. {
    14. 	struct QListNode* next;
    15. 	QDataType Data;
    16. }QNode;
    17.  
    18. //队列的结构
    19. typedef struct Queue
    20. {
    21. 	QNode* front;
    22. 	QNode* back;
    23. 	int size;//记录队列节点的个数
    24. }Queue;
    25.  
    26. //初始化队列
    27. void QueueInit(Queue* pq);
    28.  
    29. //队尾入数据
    30. void QueuePush(Queue* pq, QDataType x);
    31.  
    32. //队尾出数据
    33. void QueuePop(Queue* pq);
    34.  
    35. //获取队头的数据
    36. QDataType QueueFront(Queue* pq);
    37.  
    38. //获取队尾的数据
    39. QDataType QueueBack(Queue* pq);
    40.  
    41. //获取队列中有效元素的个数
    42. int QueueSize(Queue* pq);
    43.  
    44. //队列的判空
    45. bool QueueEmpty(Queue* pq);
    46.  
    47. //队列的销毁
    48. void QueueDestroy(Queue* pq);

    🌗 test.c文件

    1. #include"Queue.h"
    2.  
    3. int main()
    4. {
    5. 	Queue q;
    6. 	QueueInit(&q);
    7.  
    8. 	//队尾插入数据
    9. 	QueuePush(&q, 1);
    10. 	QueuePush(&q, 2);
    11. 	QueuePush(&q, 3);
    12. 	QueuePush(&q, 4);
    13. 	QueuePush(&q, 5);
    14.  
    15. 	while (!QueueEmpty(&q))
    16. 	{
    17. 		//获取队头的数据
    18. 		printf("%d ", QueueFront(&q));
    19. 		QueuePop(&q);
    20. 	}
    21. 	printf("\n");
    22. 	
    23. 	QueueDestroy(&q);
    24.  
    25. 	return 0;
    26. }

    🌔 225.用队列实现栈

    LeeCode题目链接：使用两个栈实现队列。OJ

    题目描述：

    🌗 题解思路

    实现栈的结构：在此之前我们需要队列的结构，不过还好我们在前面实现过一个队列了，这里我们直接用。这里我们定义两个队列，一个q1，一个q2。

     

    创造栈：这里我们不能像创造队列一样，

    Queue q；

    return &q;

    因为局部变量出了作用域就销毁，所以我们需要malloc一个栈，并且初始化，再返回。

     

    入栈：哪个队列不为空，就往哪个队列入数据。

     

    出栈：假设一个队列为空，一个队列不为空，将不为空队列的数据导入为空队列中，至原来不为空的队列还剩一个数据。再记录最后一个数据，并且返回。

     

    获取栈顶数据：哪个队列不为空，就获取哪个队列中的队尾的数据。

     

    判断栈是否为空：当两个队列都为空时，栈就为空。

     

    栈的销毁：因为在栈中，有两个队列，所以先销毁两个队列，再释放栈。

     

     🌗 题解代码

    1. // 两个队列
    2. typedef struct {
    3.     Queue q1;
    4.     Queue q2;
    5. } MyStack;
    6.  
    7.  
    8. MyStack* myStackCreate() {
    9.     // 需要malloc obj
    10.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    11.  
    12.     //初始化
    13.     QueueInit(&obj->q1);
    14.     QueueInit(&obj->q2);
    15.  
    16.     return obj;
    17. }
    18.  
    19. void myStackPush(MyStack* obj, int x) {
    20.     //两个不为空就push哪个
    21.     if(!QueueEmpty(&obj->q1))
    22.     {
    23.         //入数据
    24.         QueuePush(&obj->q1,x);
    25.     }
    26.     else{
    27.         QueuePush(&obj->q2,x);
    28.     }
    29. }
    30.  
    31. int myStackPop(MyStack* obj) {  //要返回栈顶的数据
    32.     //Pop不为空队列  假设q1为空
    33.     MyStack* empty=&obj->q1;
    34.     MyStack* nonempty=&obj->q2;
    35.  
    36.     if(!QueueEmpty(&obj->q1))
    37.     {
    38.         empty=&obj->q2;
    39.         nonempty=&obj->q1;
    40.     }
    41.  
    42.     //倒数据  还剩下一个数据
    43.     while(QueueSize(nonempty)>1)
    44.     {
    45.         //不为空队列的头数据
    46.         QueuePush(empty,QueueFront(nonempty));
    47.         QueuePop(nonempty);
    48.     }
    49.  
    50.     //返回栈顶元素
    51.     int top=QueueFront(nonempty);
    52.     QueuePop(nonempty);
    53.  
    54.     return top;
    55. }
    56.  
    57. int myStackTop(MyStack* obj) {
    58.     //获取不为空的队列的尾数据
    59.      if(!QueueEmpty(&obj->q1))
    60.     {
    61.        return QueueBack(&obj->q1);
    62.     }
    63.     else{
    64.        return QueueBack(&obj->q2);
    65.     }
    66. }
    67.  
    68. bool myStackEmpty(MyStack* obj) {
    69.     //两个队列都为空
    70.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    71. }
    72.  
    73. void myStackFree(MyStack* obj) {
    74.     //先销毁队列，再free栈
    75.     QueueDestroy(&obj->q1);
    76.     QueueDestroy(&obj->q2);
    77.  
    78.     free(obj);
    79. }

    🌔 232.用栈实现队列

    LeetCode题目链接：用两个栈实现队列。OJ

    题目描述：

     🌗 题解思路

    队列结构：还是一样需要栈的所有接口实现，在这里我们定义两个栈，

    一个栈叫Push栈：专门用来队列的插入数据。

    另一个栈叫Pop栈：专门用来实现出队列的操作。

     

    创造队列：还是一样需要malloc一个队列，并且初始化，最后返回。

     

    入队列：直接往Push栈里面插入数据。 

     

    出队列：判断需不需要将数据从Push栈中全部导入Pop栈中，如果Pop栈中没有数据，就说明需要倒数据。因为是栈的性质，所以队头的数据就是栈顶的数据，就是倒过去之后栈顶的数据。（需要Pop操作）

     

    获取队头的数据：也是一样判断是否需要倒数据，再记录Pop栈顶的数据，返回。（不需要Pop操作）

     

    队列的判空：两个栈都为空时，队列就为空。 

     

    队列的销毁：先销毁两个栈，再释放队列。

     

    🌗 题解代码

    1. typedef struct {
    2.     //一个栈用来Push，一个栈用来Pop
    3.     Stack PushST;
    4.     Stack PopST;
    5. } MyQueue;
    6.  
    7.  
    8. MyQueue* myQueueCreate() {
    9.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    10.  
    11.     //进行初始化
    12.     StackInit(&obj->PushST);
    13.     StackInit(&obj->PopST);
    14.  
    15.     return obj;
    16. }
    17.  
    18. void myQueuePush(MyQueue* obj, int x) {
    19.     //直接往PushST的栈入数据
    20.     StackPush(&obj->PushST,x);
    21. }
    22.  
    23. void PushST_To_PopST(MyQueue* obj)
    24. {
    25.     if(StackEmpty(&obj->PopST))
    26.     {
    27.         while(!StackEmpty(&obj->PushST))
    28.         {
    29.             //倒PushST栈顶的数据
    30.             StackPush(&obj->PopST,StackTop(&obj->PushST));
    31.             //删除这个数据
    32.             StackPop(&obj->PushST);
    33.         }
    34.     }
    35. }
    36.  
    37. int myQueuePop(MyQueue* obj) {
    38.     //考虑是否倒数据
    39.     PushST_To_PopST(obj);
    40.  
    41.     //返回队列开头的数据
    42.     int front=StackTop(&obj->PopST);
    43.     StackPop(&obj->PopST);
    44.  
    45.     return front;
    46. }
    47.  
    48. int myQueuePeek(MyQueue* obj) {
    49.     //直接返回队列头的数据
    50.     PushST_To_PopST(obj);
    51.  
    52.     int front=StackTop(&obj->PopST);
    53.     return front;
    54. }
    55.  
    56. bool myQueueEmpty(MyQueue* obj) {
    57.     return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
    58. }
    59.  
    60. void myQueueFree(MyQueue* obj) {
    61.     StackDestroy(&obj->PushST);
    62.     StackDestroy(&obj->PopST);
    63.  
    64.     free(obj);
    65. }

    🌗 结束语

    🎈 相隔千里，不能陪各位大佬在中秋节一起赏月，但是我们还能看到同一个月亮。中秋节祝各位大佬中秋快乐。

    【写在最后·想告诉你】

    在互联网这个行业里

    任何时候都要学好技术

    永远都是 技术为王

  • 相关阅读:
    [附源码]java毕业设计健身房管理系统论文2022
    Java学习中Spring到底是什么？该如何学习？
    【AI学习笔记】jupyter notebook 默认路径修改（超简介，超详细）
    Oracle-expdp方式升级19c问题合集
    SpringCloud微服务（十二）——Seata分布式事务
    @Redis--主从复制
    centos离线安装包(https部署下需要mod_ssl)
    Unity的UnityStats： 属性详解与实用案例
    nodejs微信小程序-利康药房管理系统的设计与实现- 安卓-python-PHP-计算机毕业设计
    工控自动化方案：和利时LE系列PLC数采通讯
  • 原文地址：https://blog.csdn.net/qq_63938813/article/details/126788918