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

【栈和队列】算法题 ---- 力扣

作者：一键难忘520 | 2024-08-02 14:19:19

赞

踩

【栈和队列】算法题 ---- 力扣

        通过前面栈和队列的学习，现在来看这些算法题目

一、有效的括号

        本题让判断括号是否有效

第一眼看可能没一点思路，但仔细分析一下；

        我们学习过栈数据结构，知道栈先进后出的原则，那我们就可以使用啊；把题目的左括号存储起来，让右括号跟左括号一一比较。

思路：

        遍历字符串，遇到左括号就括号入栈，遇到右括号就与栈顶数据进行对比，如果配对就继续；如果不配对，就返回false

画图分析：

  现在有这样的括号字符串

        遍历字符串，第一个是  {  左括号，就入栈

        ps接着遍历， [  依然是左括号，入栈

        ps接着遍历，  (  还是左括号，入栈

        ps接着遍历，  )  是右括号，与栈顶数据进行比较，括号匹配，出栈

        ps接着遍历，  ]  是右括号，与栈顶数据比较，括号匹配，出栈

        ps接着遍历，  }  是右括号，与栈顶数据进行比较，括号匹配，出栈

        ps遍历完字符串，再判断栈是否为空？如果为空，就代表所以括号都匹配了；如果栈不为空，括号就不匹配。

        此外，再遍历过程中，有依次括号不匹配就要直接返回false

力扣题代码如下：

  1. typedef char SType;
  2. typedef struct Stack {
  3.     SType* arr;
  4.     int size; // 栈顶
  5.     int num;  // 空间大小
  6. } Stack;
  7.  
  8. // 初始化
  9. void STInit(Stack* ps) {
  10.     assert(ps);
  11.     ps->arr = NULL;
  12.     ps->size = ps->num = 0;
  13. }
  14. // 判断栈是否为空
  15. bool STEmpty(Stack* ps) {
  16.     assert(ps);
  17.     return ps->size == 0;
  18. }
  19. // 入栈
  20. void STPush(Stack* ps, SType x) {
  21.     assert(ps);
  22.     // 判断空间大小是否足够
  23.     if (ps->num <= ps->size) {
  24.         int newnum = (ps->num == 0) ? 4 : 2 * ps->num;
  25.         SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack));
  26.         if (tmp == NULL) {
  27.             perror("realloc filed");
  28.             exit(1);
  29.         }
  30.         ps->arr = tmp;
  31.         ps->num = newnum;
  32.     }
  33.     ps->arr[ps->size++] = x;
  34. }
  35. // 出栈
  36. void STPop(Stack* ps) {
  37.     assert(ps);           // 不能传NULL
  38.     assert(!STEmpty(ps)); // 栈不能为空
  39.     ps->size--;
  40. }
  41. // 取栈顶数据
  42. SType STtop(Stack* ps) {
  43.     assert(ps);           // 不能传NULL
  44.     assert(!STEmpty(ps)); // 栈不能为空
  45.     return ps->arr[ps->size - 1];
  46. }
  47. // 获取栈中数据个数
  48. int STSize(Stack* ps) {
  49.     assert(ps);
  50.     return ps->size;
  51. }
  52. // 栈的销毁
  53. void STDesTroy(Stack* ps) {
  54.     assert(ps);
  55.     if (ps->arr)
  56.         free(ps->arr);
  57.     ps->arr = NULL;
  58.     ps->size = ps->num = 0;
  59. }
  60.  
  61. bool isValid(char* s) {
  62.     Stack arr;
  63.     // 初始化
  64.     STInit(&arr);
  65.     char* ps = s;
  66.     while (*ps != '\0') {
  67.         if (*ps == '(' || *ps == '[' || *ps == '{') {
  68.             // 入栈
  69.             STPush(&arr, *ps);
  70.         } else {
  71.             // 取栈顶数据
  72.             if (STEmpty(&arr)) {
  73.                 return false;
  74.             }
  75.             char ch = STtop(&arr);
  76.             if ((ch == '(' && *ps == ')') || (ch == '[' && *ps == ']') ||
  77.                 (ch == '{' && *ps == '}')) {
  78.                 STPop(&arr);
  79.             } else {
  80.                 return false;
  81.             }
  82.         }
  83.         ps++;
  84.     }
  85.     if (STEmpty(&arr)) // 栈为空
  86.     {
  87.         return true;
  88.     }
  89.     return false;
  90. }

二、用队列实现栈

        使用队列来实现栈，我们直到，队列是先进先出，而栈是先进后出。这里我们需要用两个队列来实现栈的相关操作

思路：

        保证两个队列中有一个为空，再两个队列之间来回导入导出数据。

        入栈：往不为空的队列里面插入数据

        出栈：找到不为空的队列，将size-1个数据导入到另一个队列，最后剩余的一个数据，就是要出栈的数据

        取栈顶元素：找到不为空的队列，取队尾元素即可

假设依次插入了1，2，3三个数据，现在要出栈

        将q1中数据size-1（2个）导入到q2中。

        现在q1当中剩余的数据就是要出栈的数据（即栈顶）。这样就满足了栈先进先出的特点。

力扣题代码如下：

  1. typedef int QType;
  2. typedef struct QueueNode // 队列节结构
  3. {
  4.     QType data;
  5.     struct QueueNode* next;
  6. } QueueNode;
  7. typedef struct Queue // 队列结构
  8. {
  9.     int size;         // 队列中的数据个数
  10.     QueueNode* phead; // 队头
  11.     QueueNode* ptial; // 队尾
  12. } Queue;
  13.  
  14. // 初始化
  15. void QueueInit(Queue* pq) {
  16.     assert(pq);
  17.     pq->phead = pq->ptial = NULL;
  18.     pq->size = 0;
  19. }
  20. // 判断队列是否为空
  21. bool QueueEmpty(Queue* pq) {
  22.     assert(pq);
  23.     return pq->size == 0;
  24. }
  25. // 入队列--从队尾插入数据
  26. void QueuePush(Queue* pq, QType x) {
  27.     assert(pq);
  28.     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  29.     newnode->data = x;
  30.     newnode->next = NULL;
  31.     if (QueueEmpty(pq)) // 队列为空
  32.     {
  33.         pq->phead = pq->ptial = newnode;
  34.     } else { // 队列不为空
  35.         pq->ptial->next = newnode;
  36.         pq->ptial = newnode;
  37.     }
  38.     pq->size++;
  39. }
  40. // 出队列--从对头删除数据
  41. void QueuePop(Queue* pq) {
  42.     assert(pq);              // 不能传NULL
  43.     //assert(!QueueEmpty(pq)); // 队列不能为空
  44.     QueueNode* del = pq->phead;
  45.     pq->phead = pq->phead->next;
  46.     if (pq->size == 1) // 队列只有一个节点
  47.     {
  48.         pq->ptial = NULL;
  49.     }
  50.     pq->size--;
  51.     free(del);
  52.     del = NULL;
  53. }
  54. // 取队头数据
  55. QType QueueFront(Queue* pq) {
  56.     assert(pq);              // 不能传NULL
  57.     //assert(!QueueEmpty(pq)); // 队列不能为空
  58.     return pq->phead->data;
  59. }
  60. // 取队尾数据
  61. QType QueueBack(Queue* pq) {
  62.     assert(pq);              // 不能传NULL
  63.     //assert(!QueueEmpty(pq)); // 队列不能为空
  64.     return pq->ptial->data;
  65. }
  66. // 获取队列数据个数
  67. int QueueSize(Queue* pq) {
  68.     assert(pq); // 不能传NULL
  69.     return pq->size;
  70. }
  71. // 销毁队列
  72. void QueueDesTroy(Queue* pq) {
  73.     assert(pq);              // 不能传NULL
  74.     //assert(!QueueEmpty(pq)); // 队列不能为空
  75.     QueueNode* pcur = pq->phead;
  76.     while (pcur) {
  77.         QueueNode* del = pcur;
  78.         pcur = pcur->next;
  79.         free(del);
  80.         del = NULL;
  81.     }
  82.     pq->phead = pq->ptial = NULL;
  83.     pq->size = 0;
  84. }
  85.  
  86. typedef struct {
  87.     Queue q1;
  88.     Queue q2;
  89. } MyStack;
  90.  
  91. MyStack* myStackCreate() {
  92.     MyStack* Qst = (MyStack*)malloc(sizeof(MyStack));
  93.     QueueInit(&Qst->q1);
  94.     QueueInit(&Qst->q2);
  95.     return Qst;
  96. }
  97.  
  98. void myStackPush(MyStack* obj, int x) {
  99.     // 往不为空的队列中插入数据
  100.     if (QueueEmpty(&obj->q1)) {
  101.         QueuePush(&obj->q2, x);
  102.     } else {
  103.         QueuePush(&obj->q1, x);
  104.     }
  105. }
  106.  
  107. int myStackPop(MyStack* obj) {
  108.     // 先找到不为空的队列
  109.     Queue* empq = &obj->q1;
  110.     Queue* noneq = &obj->q2;
  111.     if (!(QueueEmpty(&obj->q1))) // 如果q1不为空
  112.     {
  113.         empq = &obj->q2;
  114.         noneq = &obj->q1;
  115.     }
  116.     //empq --  空队列
  117.     //noneq --  非空队列
  118.     while(QueueSize(noneq) > 1) {
  119.         // 将noneq队列的数据导入到empq中去
  120.         QueuePush(empq, QueueFront(noneq));
  121.         QueuePop(noneq);
  122.     }
  123.     int ret = QueueFront(noneq);
  124.     QueuePop(noneq);
  125.     return ret;
  126. }
  127.  
  128. int myStackTop(MyStack* obj) {
  129.     if(QueueEmpty(&obj->q1))
  130.     {
  131.         return QueueBack(&obj->q2);
  132.     }else{
  133.         return QueueBack(&obj->q1);
  134.     }
  135. }
  136.  
  137. bool myStackEmpty(MyStack* obj) {
  138.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  139. }
  140.  
  141. void myStackFree(MyStack* obj) {
  142.     free(obj);
  143.     obj = NULL;
  144. }

三、用栈实现队列

        上一个题让我们用队列来实现栈，这个用两个栈来实现队列。

定义两个栈

思路：

        往PushST中插入数据，再将数据导入到PopST中，出栈即可；

        入队列：往PushST中插入数据

        出队列：判断栈PopST是否为空？如果PopST栈为空，就将栈PushST中数据导入到栈PopST中去，再让栈PopST出栈操作；如果不为空，直接让栈PopST出栈操作即可。

        取队头数据：和出队列操作一样，只是不需要出栈操作，只取数据

分析：

        假设依次插入了1，2，3三个数据，现在出栈一次，再插入一个数据4，最后取队头数据，依次出栈。

        出栈一次，PopST为空，就将PushST中数据导入到PopST中去。

依次导入

        出栈；

再插入数据4

取队头数据：

最后依次出队列

现在，PopST栈为空，就要先将PushST中数据先导入到PopST中。

再出队列

力扣题代码如下：

  1. typedef int SType;
  2. typedef struct Stack
  3. {
  4. 	SType* arr;
  5. 	int size;  //栈顶
  6. 	int num;   //空间大小
  7. }Stack;
  8. //初始化
  9. void STInit(Stack* ps)
  10. {
  11. 	assert(ps);
  12. 	ps->arr = NULL;
  13. 	ps->size = ps->num = 0;
  14. }
  15. //判断栈是否为空
  16. bool STEmpty(Stack* ps)
  17. {
  18. 	assert(ps);
  19. 	return ps->size == 0;
  20. }
  21. //入栈
  22. void STPush(Stack* ps, SType x)
  23. {
  24. 	assert(ps);
  25. 	//判断空间大小是否足够
  26. 	if (ps->num <= ps->size)
  27. 	{
  28. 		int newnum = (ps->num == 0) ? 4 : ps->num * 2;
  29. 		SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack));
  30. 		if (tmp == NULL)
  31. 		{
  32. 			perror("realloc filed");
  33. 			exit(1);
  34. 		}
  35. 		ps->arr = tmp;
  36. 		ps->num = newnum;
  37. 	}
  38. 	ps->arr[ps->size++] = x;
  39. }
  40. //出栈
  41. void STPop(Stack* ps)
  42. {
  43. 	assert(ps); //不能传NULL
  44. 	assert(!STEmpty(ps));  //栈不能为空
  45. 	ps->size--;
  46. }
  47. //取栈顶数据
  48. SType STtop(Stack* ps)
  49. {
  50. 	return ps->arr[ps->size - 1];
  51. }
  52. //获取栈中数据个数
  53. int STSize(Stack* ps)
  54. {
  55. 	assert(ps);
  56. 	return ps->size;
  57. }
  58. //栈的销毁
  59. void STDesTroy(Stack* ps)
  60. {
  61. 	assert(ps);
  62. 	if (ps->arr)
  63. 		free(ps->arr);
  64. 	ps->arr = NULL;
  65. 	ps->size = ps->num = 0;
  66. }
  67.  
  68.  
  69. typedef struct {
  70.     Stack s1;
  71.     Stack s2;
  72. } MyQueue;
  73.  
  74. //初始化
  75. MyQueue* myQueueCreate() {
  76.     MyQueue* Queue=(MyQueue*)malloc(sizeof(MyQueue));
  77.     STInit(&Queue->s1);
  78.     STInit(&Queue->s2);
  79.     return Queue;
  80. }
  81. //插入数据
  82. void myQueuePush(MyQueue* obj, int x) {
  83.     assert(obj);
  84.     STPush(&obj->s1, x);
  85. }
  86.  
  87. int myQueuePop(MyQueue* obj) {
  88.     assert(obj);
  89.     if(STEmpty(&obj->s2))
  90.     {
  91.         //把s1中数据导入到s2
  92.         while(!STEmpty(&obj->s1))
  93.         {
  94.             STPush(&obj->s2,STtop(&obj->s1));
  95.             STPop(&obj->s1);
  96.         }
  97.     }
  98.     int ret=STtop(&obj->s2);
  99.     STPop(&obj->s2);
  100.     return ret;
  101. }
  102.  
  103. int myQueuePeek(MyQueue* obj) {
  104.     if(STEmpty(&obj->s2))
  105.     {
  106.         //把s1中数据导入到s2
  107.         while(!STEmpty(&obj->s1))
  108.         {
  109.             STPush(&obj->s2,STtop(&obj->s1));
  110.             STPop(&obj->s1);
  111.         }
  112.     }
  113.     return STtop(&obj->s2);
  114. }
  115.  
  116. bool myQueueEmpty(MyQueue* obj) {
  117.     return (STEmpty(&obj->s1)) && (STEmpty(&obj->s2));
  118. }
  119.  
  120. void myQueueFree(MyQueue* obj) {
  121.     if(obj)
  122.         free(obj);
  123.     obj=NULL;
  124. }

四、设计循环队列

        设计循环队列，这里使用数组来设计

这里会设计到的一些问题：

        插入数据，如何判断空间是否满了？       

这里多申请一个空间，便于判断空间是否满了

        删除数据，如何去删？

这里，删除front指向的数据，就是队头数据

详细代码如下：

  1.  
  2. typedef struct {
  3.     int* arr;
  4.     int front;
  5.     int rear;
  6.     int num;
  7. } MyCircularQueue;
  8.  
  9. MyCircularQueue* myCircularQueueCreate(int k) {
  10.     MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  11.     pq->arr = malloc((k + 1) * sizeof(int));
  12.     pq->front = pq->rear = 0;
  13.     pq->num = k;
  14.     return pq;
  15. }
  16.  
  17. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  18.  
  19.     return (obj->rear == obj->front);
  20. }
  21.  
  22. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  23.     return (obj->rear + 1) % (obj->num + 1) == obj->front;
  24. }
  25.  
  26. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  27.  
  28.     if (myCircularQueueIsFull(obj)) // 队列满了
  29.     {
  30.         return false;
  31.     }
  32.     // 插入数据
  33.     obj->arr[obj->rear++] = value;
  34.     obj->rear %= (obj->num + 1);
  35.     return true;
  36. }
  37.  
  38. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  39.     if (myCircularQueueIsEmpty(obj)) {
  40.         return false;
  41.     }
  42.     obj->front++;
  43.     obj->front %= (obj->num + 1);
  44.     return true;
  45. }
  46.  
  47. int myCircularQueueFront(MyCircularQueue* obj) {
  48.     if (myCircularQueueIsEmpty(obj))
  49.         return -1;
  50.     return obj->arr[obj->front];
  51. }
  52.  
  53. int myCircularQueueRear(MyCircularQueue* obj) {
  54.     if (myCircularQueueIsEmpty(obj))
  55.         return -1;
  56.     int ret=obj->rear-1;
  57.     if(obj->rear==0)
  58.     {
  59.         ret=obj->num;
  60.     }
  61.     return obj->arr[ret];
  62. }
  63.  
  64. void myCircularQueueFree(MyCircularQueue* obj) {
  65.     free(obj->arr);
  66.     free(obj);
  67.     obj = NULL;
  68. }

感谢各位大佬支持并指出问题，

                        如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

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

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

  

闽ICP备14008679号