devbox
一键难忘520
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】栈和队列（链表模拟队列）_链表 队列 和栈

作者：一键难忘520 | 2024-08-19 09:20:40

赞

踩

链表 队列 和栈

 

学习本章节必须具备 单链表的前置知识，

建议提前学习：点击链接学习：单链表各种功能函数 细节 详解

本章节是学习用 单链表模拟队列

1. 单链表实现队列 思路如下

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先 进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一 端称为队头

1.1 使用 数组 还是 链表 模拟 队列 结构？

因为需要 模拟队列 先进先出的 特性：队头 只能出，队尾 只能进

若 使用 数组模拟，每次 pop 队头操作，就需要 全部元素向前面移动，时间复杂度为 O(n)

综上，因为需要 考虑位置变化，选择 链表 实现 队列 较优

1.2. 需要使用 什么类型的 链表模拟队列？

单向

带头 / 不带头 都可以 ：因为哨兵位主要用于 双向链表 找尾 ，为了方便删除，这里差别不大

不循环

我们下面实现的 是 单向不带头不循环链表

实际上，单向或双向，循环或不循环，带头或不带头 完全取决于 你自己要实现一个功能的需求，不是说 一定要固定使用 哪一个套 ，需要灵活选择使用

1.3. 单向链表 实现队列 的链表节点结构体创建：

  1. typedef int QDataType;
  2. typedef struct QueueNode
  3. {
  4. 	QDataType value;            // 节点数据
  5. 	struct QueueNode* next;     // 指向下一个节点
  6. }QNode;
1.4. 考虑效率，创建 头尾指针结构体

因为 队列需要：队头 push，队尾 pop

涉及到对 链表 的 尾部操作必须意识到：需要先进行 找尾操作，时间复杂度为 O(n)

方案：因为涉及头尾频繁操作：可以 直接 同时定义 头指针 phead 和 尾指针 ptail

技巧：同类型的变量可以封装成一个结构体

因为 phead 和 ptail 是可以不断变化的，每个相关函数都需要同时传递 phead 和 ptail 两个变量

则可以将多个同类型的变量 封装成 一个结构体，方便操作

这样，传递变量时 直接传递一个 结构体的指针就行了

  1. typedef struct Queue
  2. {
  3.     QNode* phead;
  4.     QNode* ptail;
  5. }Queue;
  1. // 区别：减少了传递变量的数量，利于协助开发
  2. // void QueuePush(QNode* phead, QNode* ptail);
  3. void QueuePush(Queue* pq);
  4. // void QueuePop(QNode* phead, QNode* ptail);
  5. void QueuePop(Queue* pq);

1.5. Push / Pop ：入队 和 出队操作

Push 在队尾入队，Pop 在队头出队

  1. void QueuePop(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	// pop 的删除操作 需要分类讨论：链表节点个数为 0、为 1、为 两个以上
  5.     
  6. 	// 为 0 ：直接判空，退出操作：phead == ptail == NULL
  7. 	assert(pq->phead);    // 头节点为空 就一定代表为空了
  8.     
  9. 	// 为 1：phead == ptail  但是 phead != NULL 的情况：即一定指向一个节点
  10. 	if (pq->phead == pq->ptail && pq->phead != NULL) {
  11. 		free(pq->phead);
  12. 		pq->phead = pq->ptail = NULL;
  13. 	}
  14. 	else // 为 两个以上：先记录第二个节点，free 掉头节点，更新头节点
  15. 	{
  16. 		QNode* tmp = pq->phead->next;
  17. 		free(pq->phead);
  18. 		pq->phead = tmp;
  19. 	}
  20. }

为什么 ” 头节点为空 或 尾节点为空 就一定代表链表为空了 “？

1.6. 观察上面代码：有需要 判断链表节点数量的 需求，为了简化代码与优化过程，可以 直接定义一个 size ，放进结构体中，时刻记录 链表节点数量

  1. // 结构体更改：
  2. typedef struct Queue
  3. {
  4. 	QNode* phead;
  5. 	QNode* ptail;
  6. 	int size;
  7. }Queue;
  8.  
  9. // 加入 size 后 的 Push 和 Pop 函数
  10. void QueuePop(Queue* pq)
  11. {
  12.     assert(pq);
  13.     assert(pq->phead);
  14.  
  15.     if (pq->size == 1) {
  16.         free(pq->phead);
  17.         pq->phead = pq->ptail = NULL;
  18.     }
  19.     else if (pq->size >= 2)
  20.     {
  21.         QNode* next = pq->phead->next;  // 保留下一个
  22.         free(pq->phead);
  23.         pq->phead = next;
  24.     }
  25.     pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
  26. }
  27.  
  28.  
  29. void QueuePush(Queue* pq, QDataType x)
  30. {
  31.     assert(pq);
  32.     // push 前先创建一个新节点
  33.     QNode* newNode = (QNode*)malloc(sizeof(QNode));
  34.     if (newNode == NULL) {
  35.         perror("malloc fail");
  36.         return;
  37.     }
  38.     newNode->value = x;
  39.     newNode->next = NULL;
  40.  
  41.     
  42.     if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空
  43.     {
  44.         pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接
  45.         pq->ptail = newNode; // 重新更新尾节点
  46.     }
  47.     else  // 若链表为空，则 phead 和 ptail 都要 处理
  48.     {
  49.         pq->phead = pq->ptail = newNode;
  50.     }
  51.     pq->size++;   // 数量++
  52. }

2. 综上所述，最终代码：

Queue.c

  1. #include"Queue.h"
  2.  
  3. // Push 入队，Pop 出队
  4. void QueuePop(Queue* pq)
  5. {
  6. 	assert(pq);
  7. 	assert(pq->phead);
  8.  
  9. 	if (pq->size == 1) {
  10. 		free(pq->phead);
  11. 		pq->phead = pq->ptail = NULL;
  12. 	}
  13. 	else if (pq->size >= 2)
  14. 	{
  15. 		QNode* next = pq->phead->next;  // 保留下一个
  16. 		free(pq->phead);
  17. 		pq->phead = next;
  18. 	}
  19. 	pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
  20. }
  21.  
  22. void QueuePush(Queue* pq, QDataType x)
  23. {
  24. 	assert(pq);
  25. 	// push 前先创建一个新节点
  26. 	QNode* newNode = (QNode*)malloc(sizeof(QNode));
  27. 	if (newNode == NULL) {
  28. 		perror("malloc fail");
  29. 		return;
  30. 	}
  31. 	newNode->value = x;
  32. 	newNode->next = NULL;
  33.  
  34. 	if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空
  35. 	{
  36. 		pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接
  37. 		pq->ptail = newNode; // 重新更新尾节点
  38. 	}
  39. 	else  // 若链表为空，则 phead 和 ptail 都要 处理
  40. 	{
  41. 		pq->phead = pq->ptail = newNode;
  42. 	}
  43. 	pq->size++;   // 数量++
  44. }
  45.  
  46. // 初始化
  47. void  QueueInit(Queue* pq)
  48. {
  49. 	assert(pq);
  50. 	pq->phead = pq->ptail = NULL;
  51. 	pq->size = 0;
  52. }
  53.  
  54. // 销毁链表：就是 单链表的 销毁操作
  55. void QueueDestory(Queue* pq)
  56. {
  57. 	assert(pq);
  58. 	QNode* cur = pq->phead;
  59. 	while (cur) {
  60. 		QNode* next = cur->next;
  61. 		free(cur);
  62. 		cur = next;
  63. 	}
  64. 	pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULL
  65. 	pq->size = 0;
  66. }
  67.  
  68. // Front 返回队头元素
  69. QDataType QueueFront(Queue* pq)
  70. {
  71. 	assert(pq);
  72. 	assert(pq->phead); // 若链表为空 自然没有头节点;
  73. 	return pq->phead->value;
  74. }
  75.  
  76. // Back 返回队尾元素
  77. QDataType QueueBack(Queue* pq)
  78. {
  79. 	assert(pq);
  80. 	assert(pq->ptail); // 若链表为空 自然没有尾节点;
  81. 	return pq->ptail->value;
  82. }
  83.  
  84. // Empty 判断是否为空
  85. bool QueueEmpty(Queue* pq)
  86. {
  87. 	assert(pq);
  88. 	return pq->size == 0;
  89. }
  90.  
  91. // Size 返回节点数量
  92. int QueueSize(Queue* pq)
  93. {
  94. 	assert(pq);
  95. 	return pq->size;
  96. }

Queue.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5. #include<assert.h>
  6.  
  7.  
  8. typedef int QDataType;
  9. typedef struct QueueNode
  10. {
  11. 	QDataType value;
  12. 	struct QueueNode* next;
  13. }QNode;
  14.  
  15. typedef struct Queue
  16. {
  17. 	QNode* phead;
  18. 	QNode* ptail;
  19. 	int size;
  20. }Queue;
  21.  
  22.  
  23. // 初始化
  24. void  QueueInit(Queue* pq);   
  25.  
  26. // Push 入队，Pop 出队
  27. void QueuePush(Queue* pq, QDataType x);
  28. void QueuePop(Queue* pq);
  29.  
  30. // Front 队头元素，Back 队尾元素
  31. QDataType QueueFront(Queue* pq);
  32. QDataType QueueBack(Queue* pq);
  33.  
  34. // Empty 判断是否为空，Size 返回节点数量
  35. bool QueueEmpty(Queue* pq);
  36. int QueueSize(Queue* pq);
  37.  
  38. // 销毁链表
  39. void QueueDestory(Queue* pq);

Main.c

  1. #include"Queue.h"
  2.  
  3. int main()
  4. {
  5. 	Queue q;   // 创建队列结构体
  6. 	QueueInit(&q); // 初始化：用于初始化链表的头尾节点：phead  /  ptail
  7.  
  8. 	for (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5
  9. 		QueuePush(&q, i); 
  10. 	}
  11. 	
  12. 	// 一个个读取队列元素
  13. 	while (!QueueEmpty(&q))
  14. 	{
  15. 		printf("%d ", QueueFront(&q));
  16. 		QueuePop(&q);
  17. 	}
  18.  
  19. 	QueueDestory(&q);
  20. 	return 0;
  21. }

3. LeetCode：225.队列实现栈

使用两个队列实现栈

核心思路：

保持一个队列存数据，一个队列为空
push 入数据，入到不为空的队列
pop 出数据，将 非空队列中 前 n-1 个数据 导入 空队列

代码实现

  1. // 以下均是 链式队列的 相关函数，复制粘贴过来罢了
  2. ///
  3. typedef int QDataType;
  4. typedef struct QueueNode
  5. {
  6. 	QDataType value;
  7. 	struct QueueNode* next;
  8. }QNode;
  9.  
  10. typedef struct Queue
  11. {
  12. 	QNode* phead;
  13. 	QNode* ptail;
  14. 	int size;
  15. }Queue;
  16.  
  17. void QueuePop(Queue* pq)
  18. {
  19. 	assert(pq);
  20. 	assert(pq->phead);
  21.  
  22. 	if (pq->size == 1) {
  23. 		free(pq->phead);
  24. 		pq->phead = pq->ptail = NULL;
  25. 	}
  26. 	else if (pq->size >= 2)
  27. 	{
  28. 		QNode* next = pq->phead->next;  // 保留下一个
  29. 		free(pq->phead);
  30. 		pq->phead = next;
  31. 	}
  32. 	pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
  33. }
  34.  
  35. void QueuePush(Queue* pq, QDataType x)
  36. {
  37. 	assert(pq);
  38. 	// push 前先创建一个新节点
  39. 	QNode* newNode = (QNode*)malloc(sizeof(QNode));
  40. 	if (newNode == NULL) {
  41. 		perror("malloc fail");
  42. 		return;
  43. 	}
  44. 	newNode->value = x;
  45. 	newNode->next = NULL;
  46.  
  47. 	if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空
  48. 	{
  49. 		pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接
  50. 		pq->ptail = newNode; // 重新更新尾节点
  51. 	}
  52. 	else  // 若链表为空，则 phead 和 ptail 都要 处理
  53. 	{
  54. 		pq->phead = pq->ptail = newNode;
  55. 	}
  56. 	pq->size++;   // 数量++
  57. }
  58.  
  59. // 初始化
  60. void  QueueInit(Queue* pq)
  61. {
  62. 	assert(pq);
  63. 	pq->phead = pq->ptail = NULL;
  64. 	pq->size = 0;
  65. }
  66.  
  67. // 销毁链表：就是 单链表的 销毁操作
  68. void QueueDestory(Queue* pq)
  69. {
  70. 	assert(pq);
  71. 	QNode* cur = pq->phead;
  72. 	while (cur) {
  73. 		QNode* next = cur->next;
  74. 		free(cur);
  75. 		cur = next;
  76. 	}
  77. 	pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULL
  78. 	pq->size = 0;
  79. }
  80.  
  81. // Front 返回队头元素
  82. QDataType QueueFront(Queue* pq)
  83. {
  84. 	assert(pq);
  85. 	assert(pq->phead); // 若链表为空 自然没有头节点;
  86. 	return pq->phead->value;
  87. }
  88.  
  89. // Back 返回队尾元素
  90. QDataType QueueBack(Queue* pq)
  91. {
  92. 	assert(pq);
  93. 	assert(pq->ptail); // 若链表为空 自然没有尾节点;
  94. 	return pq->ptail->value;
  95. }
  96.  
  97. // Empty 判断是否为空
  98. bool QueueEmpty(Queue* pq)
  99. {
  100. 	assert(pq);
  101. 	return pq->size == 0;
  102. }
  103.  
  104. // Size 返回节点数量
  105. int QueueSize(Queue* pq)
  106. {
  107. 	assert(pq);
  108. 	return pq->size;
  109. }
  110. // 以上均是 链式队列的 相关函数，复制粘贴过来罢了
  111. ///
  112.  
  113.  
  114.  
  115. ///
  116. // 下面是题目主体
  117. typedef struct {
  118.     Queue q1, q2; // 创建两个队列
  119. } MyStack;
  120.  
  121.  
  122. MyStack* myStackCreate() {
  123.     MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); // 创建一个栈
  124.     QueueInit(&(pst->q1));
  125.     QueueInit(&(pst->q2));
  126.     return pst;
  127. }
  128.  
  129. void myStackPush(MyStack* obj, int x) {
  130.     // push 到 不为空的 队列
  131.     if(QueueEmpty(&(obj->q1))) {
  132.         QueuePush(&(obj->q2), x);
  133.     }
  134.     else {
  135.         QueuePush(&(obj->q1), x);
  136.     }
  137. }
  138.  
  139. int myStackPop(MyStack* obj) {
  140.     // 找到非空的 队列，将 size-1 个元素放进 另一个空队列，同时最后一个元素pop掉
  141.     // 有两种情况：q1 为空，q2 不为空, q2 为空，q1 不为空
  142.     // 可以先假设，后调整
  143.     // 先假设 队列1 为空，队列2 不为空，后面判断后调整
  144.     Queue* pEmptyQ = &(obj->q1);
  145.     Queue* pNonEmptyQ = &(obj->q2);
  146.     if(!QueueEmpty(&(obj->q1))){
  147.         pEmptyQ = &(obj->q2);
  148.         pNonEmptyQ = &(obj->q1);
  149.     }
  150.  
  151.     // 将不为空队列 的前 n-1 个元素放进 空队列中
  152.     while(QueueSize(pNonEmptyQ) > 1) {
  153.         int x = QueueFront(pNonEmptyQ);
  154.         QueuePush(pEmptyQ, x);
  155.         QueuePop(pNonEmptyQ);
  156.     }
  157.     int t = QueueFront(pNonEmptyQ);
  158.     QueuePop(pNonEmptyQ);
  159.     return t;
  160. }
  161.  
  162. int myStackTop(MyStack* obj) {
  163.     if(QueueEmpty(&(obj->q1))) {
  164.         return QueueBack(&(obj->q2));
  165.     }
  166.     else {
  167.         return QueueBack(&(obj->q1));
  168.     }
  169. }
  170.  
  171. bool myStackEmpty(MyStack* obj) {
  172.     return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2)); // 两个都为空才是栈空
  173. }
  174.  
  175. void myStackFree(MyStack* obj) {
  176.     if(QueueEmpty(&(obj->q1))) {
  177.         QueueDestory(&(obj->q2));
  178.     }
  179.     else if(QueueEmpty(&(obj->q2))) {
  180.         QueueDestory(&(obj->q1));
  181.     }
  182. }

4. LeetCode：223.栈实现队列

使用 两个栈 模拟队列

思路

定义一个 pushStack ：专门用来接收 push入队列的 数据
定义一个 popStack ：专门用来 pop 队列数据
当 popStack 为空时，此时需要 pop 操作，则将 pushStack 的数据全部 放进 popStack ，补充数据（注意是全部）；若popStack 不为空，则进行 pop 操作即可
当 需要 push 操作，直接往 pushStack 中放数据即可

演示： push 2 次，pop 1 次，push 3 次， pop 3 次

【若文章有什么错误，欢迎评论区讨论或私信指出】 

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

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

  

闽ICP备14008679号