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

栈和队列OJ题：LeetCode--232.用栈实现队列_请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、p

作者：Gausst松鼠会 | 2024-05-25 06:31:39

赞

踩

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、p

朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--232.用栈实现队列

数 据 结 构 专 栏：数据结构

个    人   主    页 ：stackY、

LeetCode 专  栏 ：LeetCode刷题训练营

LeetCode--232.用栈实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/

目录

1.题目介绍

2.实例演示

3.解题思路

3.1创建队列

3.2入列

3.3出列

3.4获取队头元素

3.5优化代码

3.6检测队列是否为空

3.7销毁队列 

4.完整代码

1.题目介绍

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

        1. void push(int x) 将元素 x 推到队列的末尾
        2. int pop() 从队列的开头移除并返回元素
        3. int peek() 返回队列开头的元素
        4. boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

        你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

2.实例演示

3.解题思路

在做题之前我们先来进行简单的梳理逻辑，要通过两个栈来实现队列的功能，首先得清楚栈和队列都有什么区别，不熟悉的宝子可以去看看数据结构：栈和队列，队列的功能先进先出，而栈的功能是后进先出，那么有两个栈，要实现队列这种先进先出的功能就比较简单了，可以进行数据的转化，要将数据出队列，那么就需要将这个栈中的数据的前n-1个数据先插入到另外的一个栈，然后再将最后的元素出栈即可，这样就实现了队列的出列操作，那么在入列的时候我们是往哪个栈中入数据呢？所以我们的两个栈分别要有他们的功能，一个用来出数据，另外一个用来入数据，这样子就比较方便了。

3.1创建队列

使用两个栈来实现队列的功能，首先我们得写出一个栈，队列的功能是先进先出，栈的功能是后进先出，在创建队列的时候需要有两个栈，然后为队列创建一块空间，并且将两个栈都进行初始化：

实现栈：

  1. //动态栈
  2. typedef int STDataType;
  3.  
  4. typedef struct Stack
  5. {
  6. 	STDataType* a;
  7. 	int top;        //栈顶
  8. 	int capacity;  //栈的容量
  9. }Stack;
  10.  
  11.  
  12. //对栈的初始化
  13. void StackInit(Stack* pst);
  14.  
  15. //入栈
  16. void StackPush(Stack* pst, STDataType x);
  17.  
  18. //出栈
  19. void StackPop(Stack* pst);
  20.  
  21. //获取栈顶元素
  22. STDataType StackTop(Stack* pst);
  23.  
  24. //获取栈中的有效元素的个数
  25. int StackSize(Stack* pst);
  26.  
  27. //检测栈是否为空
  28. bool StackEmpty(Stack* pst);
  29.  
  30. //销毁栈
  31. void StackDestroy(Stack* pst);
  32.  
  33. //对栈的初始化
  34. void StackInit(Stack* pst)
  35. {
  36. 	assert(pst);
  37. 	pst->a = NULL;
  38. 	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
  39. 	//pst->top = -1     
  40. 	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
  41. 	pst->top = 0;
  42. 	pst->capacity = 0;
  43. }
  44.  
  45. //入栈
  46. void StackPush(Stack* pst, STDataType x)
  47. {
  48. 	assert(pst);
  49. 	//检测容量
  50. 	if (pst->top == pst->capacity)
  51. 	{
  52. 		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
  53. 		//当pst->a为NULL时执行的功能是和malloc一样
  54. 		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
  55. 		if (tmp == NULL)
  56. 		{
  57. 			perror("realloc fail");
  58. 			return;
  59. 		}
  60. 		pst->a = tmp;
  61. 		pst->capacity = NewCapacity;
  62. 	}
  63. 	//入栈
  64. 	pst->a[pst->top] = x;
  65. 	pst->top++;
  66. }
  67.  
  68. //出栈
  69. void StackPop(Stack* pst)
  70. {
  71. 	assert(pst);
  72. 	//判断栈是否为空
  73. 	assert(!StackEmpty(pst));
  74. 	//出栈
  75. 	pst->top--;
  76. }
  77.  
  78. //获取栈顶元素
  79. STDataType StackTop(Stack* pst)
  80. {
  81. 	assert(pst);
  82. 	assert(!StackEmpty(pst));
  83. 	//top指向的是栈顶的下一个位置的元素
  84. 	return pst->a[pst->top-1];
  85. }
  86.  
  87. //获取栈中的有效元素的个数
  88. int StackSize(Stack* pst)
  89. {
  90. 	assert(pst);
  91.  
  92. 	return pst->top;
  93. }
  94.  
  95. //检测栈是否为空
  96. bool StackEmpty(Stack* pst)
  97. {
  98. 	assert(pst);
  99. 	/*if (pst->top == 0)
  100. 	{
  101. 		return true;
  102. 	}
  103. 	else
  104. 	{
  105. 		return false;
  106. 	}*/
  107. 	return pst->top == 0;
  108. }
  109.  
  110. //销毁栈
  111. void StackDestroy(Stack* pst)
  112. {
  113. 	assert(pst);
  114.  
  115. 	//释放
  116. 	free(pst->a);
  117. 	pst->a = NULL;
  118. 	//重置为0
  119. 	pst->top = pst->capacity = 0;
  120. }

创建队列：

  1. typedef struct {
  2.     Stack STPush;  //用来出数据的栈
  3.     Stack STPop;   //用来入数据的栈
  4. } MyQueue;
  5.  
  6.  
  7. MyQueue* myQueueCreate() {
  8.     //先为队列开辟一块空间
  9.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  10.     if(obj == NULL)
  11.     {
  12.         perror("malloc fail");
  13.         return NULL;
  14.     }
  15.     //再初始化栈
  16.     StackInit(&obj->STPush);
  17.     StackInit(&obj->STPop);
  18.     return obj;
  19. }

3.2入列

插入数据就非常简单了，直接将数据插入到我们指定的STPush这个栈中：
代码演示：

  1. void myQueuePush(MyQueue* obj, int x) {
  2.     StackPush(&obj->STPush, x);
  3. }

3.3出列

栈的出栈是先进后出，我们有两个栈，因此可以将STPush栈中的前n-1个数据先依次插入到STPop栈中，然后将剩下的最后一个元素，对于队列来说就是队头的数据进行删除即可，但是呢，当第二次删除的时候STPush中没有数据了，这时的STPop中的数据的排列刚好是队列的这种效果，所以可以直接在STPop栈中直接删除即可，所以出列操作需要分两种情况：STPop栈中有无数据

代码演示：

  1.  
  2. int myQueuePop(MyQueue* obj) {
  3.     //判断STPop是否为空
  4.     if(StackEmpty(&obj->STPop))
  5.     {
  6.         //导数据
  7.         while (StackSize(&obj->STPush) > 1)
  8. 		{
  9. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  10. 			StackPop(&obj->STPush);
  11. 		}
  12.         //保存队头元素
  13.         int top = StackTop(&obj->STPush);
  14.         //删除
  15.         StackPop(&obj->STPush);
  16.         return top;
  17.     }
  18.     else
  19.     {
  20.         int top = StackTop(&obj->STPop);
  21. 		StackPop(&obj->STPop);
  22. 		return top;
  23.     }
  24. }

3.4获取队头元素

 获取队头元素这里就比较有点麻烦了，先要知道队头元素在哪个栈中，由于我们刚开始设定的缘故，队头的数据是在STPop这个栈中的，这时就需要分两种情况，如果STPop为空，这时就要将STPush中的数据全部插入到STPop中，插入过来之后STPop中的栈顶的数据就是对头的数据，如果STPop不为空，就不需要进行导数据，STPop中的栈顶元素也就是对头的数据：

代码演示： 

  1. int myQueuePeek(MyQueue* obj) {
  2.     //判断STPop是否为空
  3.     if(StackEmpty(&obj->STPop))
  4.     {
  5.         //全部导过去
  6.         while (!StackEmpty(&obj->STPush))
  7. 		{
  8. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  9. 			StackPop(&obj->STPush);
  10. 		}
  11.     }
  12.     //再取栈顶元素
  13.     return StackTop(&obj->STPop);
  14. }

3.5优化代码

如果将出列和获取队头元素这两个函数合在一起看的话还是有许多相似之处，因此我们可以进行改造，在出列时可以直接复用获取队头元素这个函数，这时表现出来的结果就是将STPush中的所有元素都挪动到STPop中，然后再进行删除即可：

代码演示：

  1. int myQueuePop(MyQueue* obj) {
  2.     /*
  3.     //判断STPop是否为空
  4.     if(StackEmpty(&obj->STPop))
  5.     {
  6.         //导数据
  7.         while (StackSize(&obj->STPush) > 1)
  8. 		{
  9. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  10. 			StackPop(&obj->STPush);
  11. 		}
  12.         //保存队头元素
  13.         int top = StackTop(&obj->STPush);
  14.         //删除
  15.         StackPop(&obj->STPush);
  16.         return top;
  17.     }
  18.     else
  19.     {
  20.         int top = StackTop(&obj->STPop);
  21. 		StackPop(&obj->STPop);
  22. 		return top;
  23.     }
  24.     */
  25.  
  26.     //复用
  27.     int front = myQueuePeek(obj);
  28.     //删除
  29.     StackPop(&obj->STPop);
  30.     return front;
  31. }
  32.  
  33. int myQueuePeek(MyQueue* obj) {
  34.     //判断STPop是否为空
  35.     if(StackEmpty(&obj->STPop))
  36.     {
  37.         //全部导过去
  38.         while (!StackEmpty(&obj->STPush))
  39. 		{
  40. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  41. 			StackPop(&obj->STPush);
  42. 		}
  43.     }
  44.     //再取栈顶元素
  45.     return StackTop(&obj->STPop);
  46. }

3.6检测队列是否为空

队列若为空就表示两个栈都为空，若一个栈不为空，则队列就不为空：

代码演示：

  1. bool myQueueEmpty(MyQueue* obj) {
  2.     return StackEmpty(&obj->STPush)
  3. 		&& StackEmpty(&obj->STPop);
  4. }

3.7销毁队列 

要销毁队列先要销毁两个栈，然后再将队列释放：

代码演示：

  1. void myQueueFree(MyQueue* obj) {
  2.     //先释放栈
  3.     StackDestroy(&obj->STPush);
  4.     StackDestroy(&obj->STPop);
  5.     //再释放队列
  6.     free(obj);
  7. }

4.完整代码

  1.  
  2. //动态栈
  3. typedef int STDataType;
  4.  
  5. typedef struct Stack
  6. {
  7. 	STDataType* a;
  8. 	int top;        //栈顶
  9. 	int capacity;  //栈的容量
  10. }Stack;
  11.  
  12.  
  13. //对栈的初始化
  14. void StackInit(Stack* pst);
  15.  
  16. //入栈
  17. void StackPush(Stack* pst, STDataType x);
  18.  
  19. //出栈
  20. void StackPop(Stack* pst);
  21.  
  22. //获取栈顶元素
  23. STDataType StackTop(Stack* pst);
  24.  
  25. //获取栈中的有效元素的个数
  26. int StackSize(Stack* pst);
  27.  
  28. //检测栈是否为空
  29. bool StackEmpty(Stack* pst);
  30.  
  31. //销毁栈
  32. void StackDestroy(Stack* pst);
  33.  
  34. //对栈的初始化
  35. void StackInit(Stack* pst)
  36. {
  37. 	assert(pst);
  38. 	pst->a = NULL;
  39. 	//top为-1时，插入一个数据之后top指向的是刚刚插入数据的位置
  40. 	//pst->top = -1     
  41. 	//top为0时，插入一个数据之后top指向的是刚刚插入数据后面的位置
  42. 	pst->top = 0;
  43. 	pst->capacity = 0;
  44. }
  45.  
  46. //入栈
  47. void StackPush(Stack* pst, STDataType x)
  48. {
  49. 	assert(pst);
  50. 	//检测容量
  51. 	if (pst->top == pst->capacity)
  52. 	{
  53. 		int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
  54. 		//当pst->a为NULL时执行的功能是和malloc一样
  55. 		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * NewCapacity);
  56. 		if (tmp == NULL)
  57. 		{
  58. 			perror("realloc fail");
  59. 			return;
  60. 		}
  61. 		pst->a = tmp;
  62. 		pst->capacity = NewCapacity;
  63. 	}
  64. 	//入栈
  65. 	pst->a[pst->top] = x;
  66. 	pst->top++;
  67. }
  68.  
  69. //出栈
  70. void StackPop(Stack* pst)
  71. {
  72. 	assert(pst);
  73. 	//判断栈是否为空
  74. 	assert(!StackEmpty(pst));
  75. 	//出栈
  76. 	pst->top--;
  77. }
  78.  
  79. //获取栈顶元素
  80. STDataType StackTop(Stack* pst)
  81. {
  82. 	assert(pst);
  83. 	assert(!StackEmpty(pst));
  84. 	//top指向的是栈顶的下一个位置的元素
  85. 	return pst->a[pst->top-1];
  86. }
  87.  
  88. //获取栈中的有效元素的个数
  89. int StackSize(Stack* pst)
  90. {
  91. 	assert(pst);
  92.  
  93. 	return pst->top;
  94. }
  95.  
  96. //检测栈是否为空
  97. bool StackEmpty(Stack* pst)
  98. {
  99. 	assert(pst);
  100. 	/*if (pst->top == 0)
  101. 	{
  102. 		return true;
  103. 	}
  104. 	else
  105. 	{
  106. 		return false;
  107. 	}*/
  108. 	return pst->top == 0;
  109. }
  110.  
  111. //销毁栈
  112. void StackDestroy(Stack* pst)
  113. {
  114. 	assert(pst);
  115.  
  116. 	//释放
  117. 	free(pst->a);
  118. 	pst->a = NULL;
  119. 	//重置为0
  120. 	pst->top = pst->capacity = 0;
  121. }
  122.  
  123.  
  124. typedef struct {
  125.     Stack STPush;  //用来出数据的栈
  126.     Stack STPop;   //用来入数据的栈
  127. } MyQueue;
  128.  
  129.  
  130. MyQueue* myQueueCreate() {
  131.     //先为队列开辟一块空间
  132.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  133.     if(obj == NULL)
  134.     {
  135.         perror("malloc fail");
  136.         return NULL;
  137.     }
  138.     //再初始化栈
  139.     StackInit(&obj->STPush);
  140.     StackInit(&obj->STPop);
  141.     return obj;
  142. }
  143.  
  144. void myQueuePush(MyQueue* obj, int x) {
  145.     StackPush(&obj->STPush, x);
  146. }
  147.  
  148. int myQueuePop(MyQueue* obj) {
  149.     /*
  150.     //判断STPop是否为空
  151.     if(StackEmpty(&obj->STPop))
  152.     {
  153.         //导数据
  154.         while (StackSize(&obj->STPush) > 1)
  155. 		{
  156. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  157. 			StackPop(&obj->STPush);
  158. 		}
  159.         //保存队头元素
  160.         int top = StackTop(&obj->STPush);
  161.         //删除
  162.         StackPop(&obj->STPush);
  163.         return top;
  164.     }
  165.     else
  166.     {
  167.         int top = StackTop(&obj->STPop);
  168. 		StackPop(&obj->STPop);
  169. 		return top;
  170.     }
  171.     */
  172.  
  173.     //复用
  174.     int front = myQueuePeek(obj);
  175.     //删除
  176.     StackPop(&obj->STPop);
  177.     return front;
  178. }
  179.  
  180. int myQueuePeek(MyQueue* obj) {
  181.     //判断STPop是否为空
  182.     if(StackEmpty(&obj->STPop))
  183.     {
  184.         //全部导过去
  185.         while (!StackEmpty(&obj->STPush))
  186. 		{
  187. 			StackPush(&obj->STPop, StackTop(&obj->STPush));
  188. 			StackPop(&obj->STPush);
  189. 		}
  190.     }
  191.     //再取栈顶元素
  192.     return StackTop(&obj->STPop);
  193. }
  194.  
  195. bool myQueueEmpty(MyQueue* obj) {
  196.     return StackEmpty(&obj->STPush)
  197. 		&& StackEmpty(&obj->STPop);
  198. }
  199.  
  200. void myQueueFree(MyQueue* obj) {
  201.     //先释放栈
  202.     StackDestroy(&obj->STPush);
  203.     StackDestroy(&obj->STPop);
  204.     //再释放队列
  205.     free(obj);
  206. }
  207.  
  208. /**
  209.  * Your MyQueue struct will be instantiated and called as such:
  210.  * MyQueue* obj = myQueueCreate();
  211.  * myQueuePush(obj, x);
  212.  
  213.  * int param_2 = myQueuePop(obj);
  214.  
  215.  * int param_3 = myQueuePeek(obj);
  216.  
  217.  * bool param_4 = myQueueEmpty(obj);
  218.  
  219.  * myQueueFree(obj);
  220. */

今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！ 

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

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

  

闽ICP备14008679号